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."

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...
 

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.

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 N  the smaller will be YDB's probability of winning p(WIN).
 

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. 

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.

p(WIN) > 1 / e = 0.367879441, which is better than the 2-to-1 odds proposed by Ger.