Challengee vs Challenger

 his puzzle was inspired by an old bar challenge reprised for me by world champion bridge player, John Swanson.  Your drinking buddy (YDB) offers that if you write N numbers on individual slips of paper -- no restrictions at all on sizes: negative numbers, positive numbers, irrational numbers, whatever -- he will in a Carnac the Magnificent type of way identfy the largest number.  You fold the slips and put them in a bowl without YDB having seen any of them.  He then randomly draws one slip out of the bowl, looks at it and announces if it is the largest number.  If he rejects it and it is the largest number, you win. If he announces it as the largest number and it is not, you win.  If he rejects it and it is not the largest number, he may look at another number.  This procedure is repeated until YDB either correctly identifies the largest number or, more likely, rejects the largest or accepts any number that is not the largest.  Without invoking extrasensory perception, what are YDB's odds in favor of winning the bar challenge?

ere is a simple version of the bar challenge with N = 3.  Just for fun, consider...

1.  - 459.67 ~~~~~ absolute zero in degrees on the Fahrenheit scale
2. 3.141592654 ~~~ something to do with a circle
3. 1492 ~~~~~~~~~~ "Columbus sailed the ocean blue."
Enough with the 'fun'.  For convenience, simply write down the indices 1, 2, 3 to represent their respective rankings in size.  It would seem that YDB has only one chance in three to win -- in the Land of Odds, that's a two-to-one wager against YDB's winning.

He takes the first slip out of the bowl, looks at it, and is immediately confronted with the question, "Is that first number the largest of the three?"  A yes answer would be a pure guess, with a one-in-three chance of being correct, and a no answer would have two out of three chances of being correct.  Thus, YDB will surely answer no, rejecting the first number.  If you then disclose that the first number happens to be the largest of the three, YDB loses the bet. Otherwise, if the first number happens not to be the largest, YDB does not win the bet but instead gets to see the number on a second slip chosen at random.

When that happens, YDB must answer the question, "Is that second number the largest of the three?"  Now, if he sees that second number happens to be smaller than the first number, he will obvously answer no, which is not a pure guess.  He then knows for sure that he will get to see the third number, which, being the last, must be the largest, giving YDB the win.

If the second number happens to be larger than the first number, YDB continues to confront the same question, "Is that second number the largest of the three?"  We will show that a yes answer has three out of four chances of being correct, while no, rejecting the second number, will give YDB a one out of four chance for winning.

ophisticated solvers will observe that for the bar challenge, there are N! (N-factorial) arrangements, or permutations -- sequences of disclosures.  For N = 3, there are a total of N! = 6 permutations as follows: 321, 312, 231, 213, 123, 132.   Let us now use all six sequences for disclosure tabulated below to develop a Strategic Policy on behalf of YDB...

 Slip #1 Slip #2 Slip #3 3 ~~ No: LOSE 2 ~~ (Already Lost) 1 ~~ (Already Lost) 3 ~~ No: LOSE 1 ~~ (Already Lost) 2 ~~ (Already Lost) 2 ~~ No: SEE NEXT  ==> 3 ~~ Yes: WIN 1 ~~ (Already Won) 2 ~~ No: SEE NEXT  ==> 1 ~~ No:  Sure Win  ==> 3 ~~ (Predicted) WIN 1 ~~ No: SEE NEXT  ==> 2 ~~ Yes: LOSE 3 ~~ (Already Lost) 1 ~~ No: SEE NEXT  ==> 3 ~~ Yes: WIN 2 ~~ (Already Won)

Accordingly, in the bar challenge with N = 3, on average YDB will WIN three out of six wagers, assuring "even money" -- a one-to-one wager in the Land of Odds.  Without invoking ESP at all, YDB's probability for winning p(WIN) = 3/6 = 1/2, which is significantly higher the 1/3 for a pure guess. The outcomes suggest a simple policy for YDB:  Always answer No for the first slip, then, if the second number is larger than the  first always answer Yes, accepting the second number.  Note: YDB has no need to see the third number.

By using, say, a coin-flip to make the select/reject decision for Slip #1, YDB would expect to have a 50-50 chance to win the 321 and 312 permutations but also a 50-50 chance to lose 231, 213, 123, 132 permutations, never having an opportunity to see the number on Slip #2.

Given the opportunity to see Slip #2, YDB would expect to have only a 50-50 chance to win the 123 permutation but also suffers a 50-50 chances to lose the 231 and 132 permutations.  Accordingly, YDB would expect to win only two out of six bets using the Pure Guess Policy, which is tantamount to looking at only one slip from the bowl.  Exclamation point declined for now.

It is easy to carry out the analysis of YDB's prospects for N = 4, wherein N! = 24 permutations, as follows:

4321 ~ LOSE, 4312 ~ LOSE, 4231 ~ LOSE, 4213 ~ LOSE, 4132 ~ LOSE, 4123 ~ LOSE
3421 ~~ WIN, 3412 ~~ WIN, 3241 ~~ WIN, 3214 ~~ WIN, 3142 ~~ WIN, 3124 ~~ WIN
2431 ~~ WIN, 2413 ~~ WIN, 2341 ~ LOSE, 2314 ~ LOSE, 2143 ~~ WIN, 2134 ~ LOSE
1432 ~~ WIN, 1423 ~~ WIN, 1342 ~ LOSE, 1324 ~ LOSE, 1243 ~ LOSE, 1234 ~ LOSE

Using an extended Strategic Policy, the number of winning wagers for YDB turns out to be 11 out of 24, which may not be an even bet, but still better than 1/4 for the Pure Guess Policy.  You are invited to try your hand at extending the Strategic Policy and confirming that for N = 5, YDB wins 50 out of 120 permutations (the table for N = 5 on this page is available for your convenience).  As expected, the larger the value of the smaller will be YDB's probability of winning p(WIN).

 1/N N! WINS p(WIN) 0.333 6 3 0.500 0.250 24 11 0.458 0.200 120 50 0.417 0.167 720 274 0.382

Those factorials do get huge fast, making the analysis of each permutation quite tedious -- eventually impossible for the Challengee vs Challenger puzzle, inasmuch as...

For half the standard deck of cards, N! = 25,852,016,738,884,976,640,000, which is greater than the number of subatomic particles in the known universe.
By the way, the limit is 51 playing cards for selection by Gee from a full deck.  If Gee lets N = 52, Ger merely waits until the King of Spades turns up and takes Gee's money.

Optimal Stopping Problem

More than 10,000 websites explore this fascinating class of problems under a variety of names, Secretary Problem being most common.  Others deal with finding optimum gasoline prices, communications switching algorithms, space missions -- hey, even optimizing web searches.

The bar challenge imposed a kind of "sudden death" upon YDB, which would be administered by you, having god-like knowedge available for instant disclosure.  An equivalent outcome arises from the more common formulation called the "Cut-off Rule" (CoR), in which YDB says no to the first K slips with no immediate consequences if one of the passed up numbers happens to be the largest.  Then starting with the Kth slip, YDB ascertains whether that slip happens to be the largest number seen so far.  If not, YDB continues to the next and the next, stopping only when a slip has the largest number of those written on the unfolded slips and takes the consequences if that number is not the largest of all the numbers in the bowl.

he Challengee vs Challenger puzzle is designed as a two-handed card game, thereby allowing a sequence of wagers without waiting in between to think up and write down numbers on slips of paper.  Like the bar challenge, the game narrative might feature "Carnac the Magnificent" and something else.  The number of cards selected by Gee is not specified by Ger.  That might seem to necessitate Ger to devine the exact size of the stack, adding to the mystery.  However, we will show that the solution is the same for all values of K! Exclamation point or a factorial symbol, your choice.

The solution to the puzzle may be derived directly from the "Cut-off Rule" (CoR) appearing in many web references...

Set K = N / e (integer value), where e = 2.718281828, the base of the natural logarithms.
For increasing values of N, the probability for Ger's success converges to an asymptote of...
p(WIN) > 1 / e = 0.367879441, which is better than the 2-to-1 odds proposed by Ger.
 N = 7 8 9 13 26 39 K = 3 4 4 5 10 15 p(WIN) = 0.428 0.41 0.406 0.368 0.368 0.368 2-to-1 0.333 0.333 0.333 0.333 0.333 0.333