[Prime]

The king of your country decided to attend to the state’s budget matters. For that purpose, he wants to first conduct some layoffs of his court staff, and second, beef up the military funds by borrowing money from foreign investors. He calls upon you as one of his top mathematical advisors to provide your learned opinion on the borrowing matter in the following manner:

In his study hall, there is a box containing 100 cards, each with a number representing the dollar amount to be borrowed from foreign investors. The cards are drawn from the box at random one by one and presented to you for an opinion. You can reject a card with a number on it, then it is tossed away and the next card is drawn. If you accept the card, then the number on it is taken to be your advice and the session stops.

You know for a fact that unless you select the card with the largest number on it, your employment will be terminated. What strategy can you adopt to maximize your chance to select the largest number? With the best strategy, what is the probability to retain your position as a top mathematical advisor?

[bonanova]

Post numbers [in brackets]:

Prof T [3] asserts 25% at N/2.

nobody [5] says it doesn't matter how many cards are skipped [N/3 or N/2], it's always 33%.

armcie [6] points out it's not 33% if N-1 are skipped, refuting nobody's result.

nobody [7] concedes the probability diminishes after N/2.

armcie [8] shows it's about more than just where the top few cards are.

unreality [9] reminds us he posted a similar problem a month ago, where it's discussed, including Chuck Rampart pointing out that the N/2 and 25% result depends on randomness and could be subverted by a clever dealer. Unreality links another statement of the problem, where Prof T's suggestion is given, mainly to show the approach, not to claim that N/2 and 25% are optimal.

Prime [10] claims differences and reminds that the optimal solution is called for.

Prime [11] gives a nod to armcie's first steps [8].

unreality [13] says his topic 4061 left out a reshuffle condition, but that with it, the problem is identical.

Prime [14] claims they are not identical, and that Chuck Rampart's answer is wrong.

Prime [15] concedes the problems are identical if the numbers on the cards are rewritten each time.

He does not help us understand how rewriting the numbers and reshuffling their sequence leads to different problems.

Prime [17] opines that unreality's link is a similar problem, but shows an incorrect answer.

bonanova [18] give the general approach to optimization problems - finding the value of the independent variable [x = number of cards skipped] which makes the derivative of the results [p(x) = winning probability] vanish. He gives the link to the exp​ression for p[x]. He further states that for very large decks [high values of N] the optimal value of x tends to N/e and the optimum probability tends to 1/e. For finite N, specific results for x near N/e are calculated to find the highest p. For N=100 that calculation gives optimal values of x = 37 and p = 0.371043.

Prime [19] repeats that N/2 and 25% are incorrect.

He says the link gives "a correct general answer," but he rejects it.

He claims an original solution using integers and rational numbers.

He gives a nod to armcie's comments [8].

Prime [21] again refutes N/2 and 25% with an enumerable case [N=4].

He hints at an approach that does not rely on differential equations.

Prime [22] gives his N/2 result as "a bit over 34.90%."

nobody [23] again contends N/2 gives 33%.

bonanova [24] plots the winning percentage for 100,000 decks of 10, 20, 50 and 100 cards.

The simulation shows convergence [from above] to the results in [18]:

Optimal: x = N/e, p = 1/e

Approximate: x = N/2, p = .349...

Prime [25] tell us his secret approach agrees with the simulation.

Prime [26] again refutes nobody's 33% claim.

Prime asks for a solution that uses integers and rational numbers.

A deck of N=100 cards comprises [unique] positive integers.

You are to find the highest of these integers.

The process you use is to find the highest integer of the first x cards

and pick the first card after x that has a higher number [if there is one].

The approach wins if the highest number is in the i^th position and that you choose it if it's there.

That will happen if and only if you didn't choose a number before you got to the i^th card.

That means the highest of the first i-1 cards was not chosen.

That means the highest of the first i-1 cards was skipped: i.e. was one of the first x cards.

That happens with a probability of x/(i-1): i.e., x chances out of i-1 equally likely possibilities.

For any value of i, the probability that the highest card is the i^th card is 1/N = 1/100.

i.e. 1 chance out of 100 equally likely possibilities.

Suppose the highest card is the 85^th card, and suppose you skip the first 20 cards.

The probability that the highest of the first 84 cards is in the first 20 cards is 20/84.

i.e. 20 chances out of 84 equally likely possibilities.

The probability that the highest card is the 85th card is 1/100.

Thus the probability that the highest card is number 85 and that you will choose it is 1/100 * 20/84.

Now we can find the overall probability p[x] that we will win by skipping the first x cards.

p[x] is the simply the sum of these individual probabilities for i not being among the first x cards.

Let i be the position of the winning card, given that i > x. Then,

p[x] = sum[i=x+1, 100] x/(i-1) * 1/100, or

p[x] = .01 * sum[i=x+1, 100] x/(i-1).

By inspection, p[x] is always positive and is very small for x near 1 and 100.

So p[x] increases to some largest value then decreases, as x ranges from 1 to 100.

The optimal value of x is the lowest value of x for which p[x] > p[x+1],

and the optimal winning probability is p[x].

This is a solution [proof] that, as requested, uses only integers and rational numbers.

To find the best x we search the neighborhood of x=N/e.

That's because ...

As N increases without bound, x becomes continuous, the sums become integrals

and the difference becomes a derivative. The condition that the derivative vanishes

leads to the optimal values of

x = N/e, and p[x] = 1/e.

Exploring the neighborhood of x = N/e shows that p[36] and p[38] are less than p[37].

Thus, the optimal result for N = 100 is

x = 37

p[37] = 0.371043

[Guest]

Bravo! Looks good to me

[Prime]

Bravo! Looks good to me

Bonanova is a genius! What I thought was a difficult problem and which took me few evenings to solve, he solved so quickly, economically, and with such ease! As I said, knowledge of calculus helps.

I derived a different series yielding the same result. It allowed me to find the number of cards to skip without the approximation 1/e. However, my series are not nearly as economical and elegant as Bonanova's equation.

[soop]

Ok, this was kind of over my head, but it kind of gave me an idea.

[Prime]

Having disposed of this problem so quickly and efficiently, we are now ready to revisit the one posted by Unreality. For as far as I can see, it was left without proper solution it deserves. I have restated and clarified the problem and added some very necessary conditions and justifications.