### PUZZLE #3: THE REBATE GAME (SOLUTION)

An antiques shop owner, in order to drum up more business, offers the following "rebate scheme" for anyone who makes a purchase:

(1) The purchase, costing a whole number of dollars, is first bought and paid for.

(2) With the real money exchange out of the way, the owner presents to the customer a bowl of plastic "coins," all marked in the same denominations as real money.

(3) The customer is told that she will be asked to select a coin randomly from the bowl, record the result, and replace the coin in the bowl. This procedure will be repeated until the sum of the results is enough to cover the cost of the purchased item(s). But first (and this is where the rebate part of the game comes in) she is told that she will be refunded the amount shown on either the first coin drawn or the last, and that she must declare beforehand which it will be.

The problem is to decide whether a "first coin" or a "last coin" strategy is most likely to maximize the rebate (or whether there is any difference at all in the two strategies).

The short answer is that the "last coin" strategy is the better of the two. This is a qualitative answer; a sharper more quantitative one is an exact specification of how much better. We sketch a solution below.

Let N be the amount of the purchase, and let the finite sequence (a_1,...,a_k) denote the final result of the repeated drawings (so each a_i is a whole number representating a real monitary denomination, a_1+...+a_{k-1} < N, and a_1+...+a_k >= N). Since the random drawings include replacement, the probability of any given final result is determined using the distribution of coins in the bowl, together with the multiplicative principle governing independent trials.

A fundamental maxim when trying to solve a large general problem is to work some special cases first and see if some pattern emerges. In keeping with this, let's assume that there are only two coins in the bowl, marked 1 and 2 respectively. Then the probability of receiving 2 dollars using the "first coin" (FC) strategy is obviously 1/2, so our task is to determine that probability when the "last coin" (LC) strategy is pursued. If N happens to be just 1, then there is only one drawing and no problem. So suppose N=2. Then there are just three final results: (2), of length 1; and (1,1) and (1,2), both of length 2. The first final result has probability 1/2 of occurrence; the probabilities for the second two are 1/4 each. So if the LC strategy is pursued, the probability of getting two dollars back is 3/4. Already this strongly suggests the qualitative claim above, but let's now try to understand why you will always get a probability higher than 1/2 using the LC strategy. In the case N=3, we have the five possible final results (2,1), (2,2), (1,1,1), (1,1,2), and (1,2); so the LC probability is 5/8. Is there a hypothesis emerging? Let's try N=4. The eight final results are (2,1,1), (2,1,2), (2,2), (1,1,1,1), (1,1,1,2), (1,1,2), (1,2,1), and (1,2,2); the LC probability is now 11/16. Try a few more cases yourself.

Note that if (a_1,...,a_k) is a final result for price N, then its sum is either N or N+1. If it's N, then (a_1,...,a_k,1) and (a_1,...,a_k,2) are final results for price N+1; if it's N+1, then a_k must be 2 and (a_1,...,a_k) is a final result for N+1. All final results for N+1 are obtained from final results for N in this way, and a tree diagram illustrates this well: branching happens below (a_1,...,a_k) just when the sum is N. Thus as N increases, the number of final results for N ending in 2 tends to grow faster than the number of final results ending in 1. (The total number of final results increases according to the standard Fibonacci sequence, by the way.) This is a vague statement, needing substantiation via induction on N, and we give only the final answer: Given the price N, the probability that a final result (a_1,...,a_k) for N ends in a 2 is 2/3 + ((-1)^N/(3*(2^N))). This is always bigger than 1/2, and tends to 2/3 as N gets large.