Fattest Stack

[Ghost Post]

The Fattest Stack puzzle is interesting to me and I have subjected it to further mathematical analysis that may be of interest to members.

To quickly review, a contestant in a game is confronted with a number of different boxes each containing an undisclosed amount of money. The contestant successively, asks to have the contents of a box revealed and he has the right to say, “stop” at any time. If he says, “stop” when the contents of the largest amount of money is being revealed he wins the contents of the box; if, however, he bypasses the box with the largest amount without saying, “stop” OR if he says, “stop” when a box other than the one with the largest amount is being revealed, he loses the game and receives no money at all. As always, the object of the game is to figure out the best strategy for winning.

In the puzzle as it was presented, the contestant was confronted with 4 boxes. One strategy is to yell, “stop” on the very first box. In that case your probability of winning is, clearly, 25%. A better strategy is to merely note the amount in the first box whose contents are revealed and, then, to yell, “stop” on the next box, if any, that has a greater amount in it. Using this strategy, you improve your probability of winning to 11/24, or 46%. This probability can be demonstrated in several ways, but to set up for describing the general case, later, I will do so, first, logically, and then in a relatively more rigorous manner that is required for more complex examples. Let’s break down the box selection process into two distinct components: the “pre-choice” segment and the “choice” segment. The first strategy (success prob. = 25%) had a “pre-choice” segment of 0; the second strategy (success prob. = 11/24) had a “pre-choice” segment of 1. Here’s how to compute the 11/24:

There are 4 possible boxes to select during the “pre-choice” period: the largest, the 2nd largest, the 3rd largest, and the 4th largest. Clearly, if you pick the

1st largest you will always lose because you would have passed the largest before saying, “stop” (0 out of 1)
2nd largest you will always win because only the largest is larger and you will say stop when you come to it (1 out of 1)
3rd largest you will win ½ the time since there are 2 larger boxes with equal probability of being selected before the other (½ out of 1)
4th largest you will win 1/3 the time since there are 3 larger boxes with equal probability of being selected before the other (1/3 out of 1)

Summing up, there are 1+1/2 + 1/3 ways of winning out of 4. Multiplying by 6 to clear the fractions, there are 6 + 3 + 2 (11) ways of winning out of 24.

The more rigorous explanation, below, while somewhat tedious, is well worth the effort based on the understanding one gains about the nature of such processes.

Step 1: compute the number of different possible “pre-choice” combinations. Mathematically, this is defined as the number of combinations of 4 things taken 1 at a time. The general formula for the number of combinations on n things taken k at a time is given by the formula, n!/(k!*(n-k)!), where the symbol, “!” means factorial. Factorial is defined as multiplying an integer by all the integers lower than it. Therefore, 4! = 4x3x2x1 = 24. In the case of 4 things taken 1 at a time, therefore, it is 4!/(1!*3!) = 4. To simplify the notation, let’s merely define the combination of n things taken k at a time as C(n,k). (To look ahead to a more involved situation, if there were 6 boxes, 2 of which were “pre-choice” the number of “pre-choice” combinations would be C(6,2) = 6!/(2!*4!) =15.)

Step 2: now here comes the step that is not really necessary when the pre choice segment consists of 1 box but becomes invaluable when the pre-choice segment is greater than 1. Specifically, an alternative way of computing C(n,k) is to compute the following:

C(n-1,k-1) + C(n-2,k-1) + C(n-3, k-1) ….C(n-j,k-1) and continuing this process until n-j=k-1.

For the case of n=4 and k=1, (i.e., C(4,1) =4) can also be stated as C(3,0) + C(2,0) + C(1,0) + C(0,0) = 1 + 1 + 1 + 1 = 4. (0 factorial equals 1)

Likewise, C(6,2) = 15 can be stated as C(5, 1) + (C(4,1) + C(3,1) + C(2,1) + C(1,1) = 5 + 4 + 3 + 2 + 1 = 15.

Now here is why this new formulation is so important: of the 15 ways in which, for example, 6 things can be taken two at a time,

5 of them contain the 1st largest value of the 6 as the largest value in the subset of 2 (You will win 0 out of 5 of these games)
4 of them contain the 2nd largest value of the 6 as the largest value in the subset of 2 (You will win 4 out of 4 of these games)
3 of them contain the 3rd largest value of the 6 as the largest value in the subset of 2 (You will win ½ of these games or 1.5 out of 3 of these games)
2 of them contain the 4th largest value of the 6 as the largest value in the subset of 2 (You will win1/3 of these games or 2/3 out of 2 of these games)
1 of them contains the 5th largest value of the 6 as the largest value in the subset of 2 (You will win1/4 of these games or 1/4 out of 1 of these games).

The winning probability, therefore, is (4 + 1.5 + .67 + .25)/15 = (6 + 5/12)/15 = 77/180 = 42.77%. If one were to enumerate every single permutation of 6 boxes, there would be 720 distinct permutations of which 308 would produce a win using the strategy of using a 2 box “pre-choice” segment and then selecting the next box that contains a larger amount than the largest amount selected in the pre-choice segment.

If there are 10 boxes, initially, the optimum strategy is to choose a “pre-choice” segment of 4 boxes (choosing 3 boxes is ever so slightly worse). One can conceive of the selection of the size of the “pre-choice” segment that optimizes the probability of success as the essence of the problem. As it turns out, the optimum size, for any number of boxes, n, is always n/e, where e is the mathematical constant defined by and named after the man who is arguably the greatest mathematician who ever lived, Euyler (pronounced “Oiler”). E is approximately equal to 2.72. Therefore, the optimum “pre-choice” segment with 100 boxes is 100/2.72 = 37 boxes. As the number of total boxes increase, the probability of success using the optimum strategy gets closer and closer to 1/e = 36.79%. With any finite number of boxes the actual probability of success will be slightly greater. The convergence is illustrated with the following examples:

With 3 boxes the probability of success using optimal strategy = 50.00%
With 4 boxes the probability of success using optimal strategy = 45.83%
With 6 boxes the probability of success using optimal strategy = 42.77%
With 10 boxes the probability of success using optimal strategy = 39.82%
With 13 boxes the probability of success using optimal strategy = 39.24%

Part of the reason for the relatively slow convergence is because one must round off the optimum “pre-choice segment to be an integer. Other games where no such requirement exists involves the following:

The first N integers are put in random order. What is the probability that none of the items is in its “correct” position (e.g., if “1” is not in position 1 AND “2” is in not in position 2 AND “3” is not in position 3, etc.

If n = 2 the number of possible orders are 2 and the number that contain no items in the “correct” position is 1. Probability = .5000
If n = 3 the number of possible orders are 6 and the number that contain no items in the “correct” position is 2. Probability = .3333
If n = 4 the number of possible orders are 24 and the number that contain no items in the “correct” position is 9. Probability = .3750
If n = 5 the number of possible orders are 120 and the number that contain no items in the “correct” position is 44 Probability = .3667
If n = 6 the number of possible orders are 720 and the number that contain no items in the “correct” position is 265. Probability = .3680
If n = 7 the number of possible orders are 5040 and the number that contain no items in the “correct” position is 1854. Probability = .3679

Notice how quickly this converges. Let’s look at a practical example: two decks of cards are shuffled. The probability that no card will be in the same position in both decks is .3679. This means, of course, that 1 or more cards will match with a probability of .6321. On a bet, therefore, if you predict 1 or more matches, the odds will be roughly 5 to 3 in your favor!!!

[Ghost Post]

Hey, deuceman.

Have you checked out my "A solitaire game" puzzle I posted on the Visitor Submitted Puzzles forum? Maybe you can help out with it.

[Borodog]

A very fine analysis. One teeny, tiny little nit (having NOTHING to do with your logic or math): Isn't e the "Naperian" base? How is this named for Euler?

Just curious if I missed an Euler connection (he's my hero!).


------------------
Insert humorous sig here.

[Ghost Post]

Tigger, I'll check the solitaire puzzle out and get back to you.

Borodog, I "learned" of the Euyler connection to e from another website only recently and took it at face value. I may well be mis-informed. I'll try to see if I can find where I got it from.

[Tom]

Interesting stuff, deuceman. It's always cool when someone really really works something out.