[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?

[Guest]

wild guess

watch the exprressions of those around u and after the first few cards come up with an estimate of the highest number

[Prof. Templeton]

After 50 cards, remember the highest number. In the next 50 cards when you reach a figure that is higher than in the first half, stick with it. There should be a 50/50 chance the highest card is in the second half and a 50/50 chance that the second highest was in the first half. Combining to give you a 25% chance of keeping your job. Best I can see right now.

[Prime]

After 50 cards, remember the highest number. In the next 50 cards when you reach a figure that is higher than in the first half, stick with it. There should be a 50/50 chance the highest card is in the second half and a 50/50 chance that the second highest was in the first half. Combining to give you a 25% chance of keeping your job. Best I can see right now.

Good effort on devising a method!

I disagree with your calculations, though. Especially, the 25%.

Edited September 26, 2008 by Prime

[Guest]

I'm not sure but I hope my solution is true and you keep your job in %33 chance. And it doesn't matter whether you start at 33. card to pick the biggest card or start at 50. card. The chances are same. I suppose Prof.s error was that: The probability of the second highest figure to be in the second 50 cards is %25, as he said, but this doesn't force you to pick it before the first highest figure. Thus its total probability is 1/4 * 1/2 = 1/8. But we should take into account another probability: If the third highest figure is in the second 50 cards, you will fail again if you pick it before the highest one. The chance of 3. to be in second 50 cards is (while 2. highest is in the 2. 50 cards and it comes after first highest) 1/8 * 1/2 = 1/16. We must multiply this again with 1/2 because the third highest, being though in the second 50, may come after the first highest. = 1/32 .By this way we get a series of

1/2 + 1/8 + 1/32 + 1/128 + 1/512 ..... = %66.6

If we start at 33. card, we avoid leaving the first highest in the fist 33 cards, but have a grater bad chance to pick the second or third highest before first highest. Indeed, when I calculated, I found the same %66 rate.

%33 chance keeping the job, is very high, for such a hard problem. I think I'm false

[Guest]

I'm not sure but I hope my solution is true and you keep your job in %33 chance. And it doesn't matter whether you start at 33. card to pick the biggest card or start at 50. card. The chances are same. I suppose Prof.s error was that: The probability of the second highest figure to be in the second 50 cards is %25, as he said, but this doesn't force you to pick it before the first highest figure. Thus its total probability is 1/4 * 1/2 = 1/8. But we should take into account another probability: If the third highest figure is in the second 50 cards, you will fail again if you pick it before the highest one. The chance of 3. to be in second 50 cards is (while 2. highest is in the 2. 50 cards and it comes after first highest) 1/8 * 1/2 = 1/16. We must multiply this again with 1/2 because the third highest, being though in the second 50, may come after the first highest. = 1/32 .By this way we get a series of

1/2 + 1/8 + 1/32 + 1/128 + 1/512 ..... = %66.6

If we start at 33. card, we avoid leaving the first highest in the fist 33 cards, but have a grater bad chance to pick the second or third highest before first highest. Indeed, when I calculated, I found the same %66 rate.

%33 chance keeping the job, is very high, for such a hard problem. I think I'm false

The fact that starting on either card 33 or card 50 gives the same result throws up warning lights for me... that would suggest that if you started at card 100 the odds would still be 33%, when that should be 1%...

[Guest]

The fact that starting on either card 33 or card 50 gives the same result throws up warning lights for me... that would suggest that if you started at card 100 the odds would still be 33%, when that should be 1%...

After 50. card (or a little more) your chance of keeping job is getting down. I didn't work on it anymore, as it is likely to be false.

Edited September 26, 2008 by nobody

[Guest]

After 50 cards, remember the highest number. In the next 50 cards when you reach a figure that is higher than in the first half, stick with it. There should be a 50/50 chance the highest card is in the second half and a 50/50 chance that the second highest was in the first half. Combining to give you a 25% chance of keeping your job. Best I can see right now.

I think we also need to take into consideration the option where the second and first highest are both in the second half... but you still pick the right answer:

say the numbers on the cards are 1 to 100

The order the cards come out is 1,2,...,49,50 (at which point you say you will stop when you pick a card 51 or higher)

And then the next card is 100

We've picked the correct card... but neither the second, nor third, nor fourth.... highest cards were in the first fifty.

So... say we draw the line at card n.

We need to calculate the probability that:

the highest card is in the last (100-n) cards

AND all cards before we get to the highest card are less than the highest card in the first n

Which seems tricky. But not totally intractable.

[unreality]

I think I've already posted this:

http://brainden.com/forum/index.php?showtopic=4061

unless they are different somehow

[Prime]

I think I've already posted this:

http://brainden.com/forum/index.php?showtopic=4061

unless they are different somehow

The supplement question in your post "what if the deck was shuffled between each game" makes it basically the same problem. Whereas, continuing the game with the same deck after an incorrect guess is a different problem. I browsed quickly through your topic and didn't see anyone even beginning to move in the direction of the solution. If people can solve this problem, they can move on to the one you posted, where you get more than one attempt to select the highest number.

This problem is complex. A strategy has been suggested by Prof. T to skip a number of cards (he suggested 50) remembering the highest number among the skipped cards, and then pick the first number that is higher if that happens. I'm going to ease down on a formal proof that such method presents the best strategy. Assume that it is the strategy. The questions become:

1. How many cards do you want to skip up front? (Seeing that 50 is just an unsubstantiated guess and there is no evidence to support it.)

2. Calculate exact probability to select the highest number with the best strategy. I haven't seen any posts here (or in that related topic) even starting to move in the right direction to accomplish that task.

This problem has an elegant answer in terms of a limit for such probability in general (for any number of cards.)

However, be forwarned: it took me few evenings to solve. And in the end I had to feed my formulas into a spreasheet and arrive to the solution numerically. (Too much work just using pen and paper.) Knowledge of calculus could help in solving this problem. I see it as a dragon of probability problems and I hope I managed to scare many a brave knight venturing to attack it.

[Prime]

...

So... say we draw the line at card n.

We need to calculate the probability that:

the highest card is in the last (100-n) cards

AND all cards before we get to the highest card are less than the highest card in the first n

Which seems tricky. But not totally intractable.

In view of the above, I have to take back what I said in my previous post about "not even starting to move in the right direction". Sorry, I wasn't paying close attention.

[peace*out]

What you do is say no to the first 100 cards. keep track of the highest #. then, when it comes around again say, "Yes, Yes that is it!!! I know it now!!! Lets do this!!!!"

100% unless they give up on you, then its 0%.

[unreality]

Prime, the original intention of the riddle was to reshuffle, I just left that out of the OP by accident. So yeah they're the same ;D I think Chuck Rampart gave the answer on my riddle, though we can discuss it more here if there's more to be discussed

[Prime]

Prime, the original intention of the riddle was to reshuffle, I just left that out of the OP by accident. So yeah they're the same ;D I think Chuck Rampart gave the answer on my riddle, though we can discuss it more here if there's more to be discussed

I checked your post again and did not find any correct answers there, or even hint thereof. Not even by Chuck Rampart, who simply made a reference to an incorrect solution he saw at another website. There is much to discuss with respect to this problem for those who are into solving difficult math problems. If there are indeed such members (or will show up in future) who find this problem interesting, it's best to discuss it on my post. My formulation of the problem is more precise and I myself solved it few years back and hope I am still able to repeat the feat. Also, I happen to know the correct answer and can guide someone who shows some progress in solving this problem.

I'll repeat, we are looking for the answers in the form of how many cards to skip and what is the exact probability to select the highest number. I can tell you off the bet, 50 cards and 25% are not the answers.

I appologize for not finding your post before I started my topic here. I made rather extensive search for different types of arrangements in which this problem appeared in popular literature, but missed your post somehow. The arrangement in which I gave here is my own.

[Prime]

The problem at Unreality's post would be the same if the deck there was re-written with a whole new set of numbers after each game, not just reshuffled.

[Yoruichi-san]

The supplement question in your post "what if the deck was shuffled between each game" makes it basically the same problem. Whereas, continuing the game with the same deck after an incorrect guess is a different problem. I browsed quickly through your topic and didn't see anyone even beginning to move in the direction of the solution. If people can solve this problem, they can move on to the one you posted, where you get more than one attempt to select the highest number.

This problem is complex. A strategy has been suggested by Prof. T to skip a number of cards (he suggested 50) remembering the highest number among the skipped cards, and then pick the first number that is higher if that happens. I'm going to ease down on a formal proof that such method presents the best strategy. Assume that it is the strategy. The questions become:

1. How many cards do you want to skip up front? (Seeing that 50 is just an unsubstantiated guess and there is no evidence to support it.)

2. Calculate exact probability to select the highest number with the best strategy. I haven't seen any posts here (or in that related topic) even starting to move in the right direction to accomplish that task.

This problem has an elegant answer in terms of a limit for such probability in general (for any number of cards.)

However, be forwarned: it took me few evenings to solve. And in the end I had to feed my formulas into a spreasheet and arrive to the solution numerically. (Too much work just using pen and paper.) Knowledge of calculus could help in solving this problem. I see it as a dragon of probability problems and I hope I managed to scare many a brave knight venturing to attack it.

Lol...ironically, mentioning calculus has just made me interested in solving this...;P

[Prime]

Prime, the original intention of the riddle was to reshuffle, I just left that out of the OP by accident. So yeah they're the same ;D I think Chuck Rampart gave the answer on my riddle, though we can discuss it more here if there's more to be discussed

I also checked the "braingle" website referred to in your post. It has a similar problem, which was posted there 4 years ago with a wrong answer (50, 25%). So the topic lives on.

[bonanova]

A strategy has been suggested by Prof. T to skip a number of cards (he suggested 50) remembering the highest number among the skipped cards, and then pick the first number that is higher if that happens. I'm going to ease down on a formal proof that such method presents the best strategy. Assume that it is the strategy.

This problem has an elegant answer in terms of a limit for such probability in general (for any number of cards.)

the method suggested by Prof T. who suggests skipping 1/2 for a 25% success rate, which is fair but not optimal.

To find the optimal fraction of cards to skip, derive an exp​ression[*] for the success probability p in terms of the number x of cards skipped, then find the value of x for which dp/dx vanishes. One finds the optimal fraction to skip is approximated by 1/e, where e=~2.7182818 is the base of natural logarithms. In the limit of infinitely large deck this answer is exact. For finite decks it is an approximation, and actual probabilities near that fraction must be calculated to find the best answer. For N=100, it is optimal to skip 37 cards and obtain a 37.1043% success rate. For very large N the optimal winning probability is 1/e =~ 36.79%.

[*] The exp​ression for p[x] can be found here.

[Prime]

...

the method suggested by Prof T. who suggests skipping 1/2 for a 25% success rate, which is fair but not optimal.

... where e=~2.7182818 is the base of natural logarithms. In the limit of infinitely large deck this answer is exact. For finite decks it is an approximation, and actual probabilities near that fraction must be calculated to find the best answer.

...

First of all, skipping 1/2 cards does not mean 25% success rate as Prof. T suggested. That was an incorrect guess in both respects (number of cards to skip, and the resulting probability.)

Second, I posted this problem here for those who want to give a shot solving it. I did few years ago, and I did not use number e, or any logarithmic integrals for that.

The web reference you are citing gives an answer to a general problem, but not the solution. It, in turn, cites a theorem equating the series to an integral, but does not show the proof.

Original problems, especially math, are very few on this forum, if any. You can always find a precedence in math literature and on the internet. But what's the point of looking up the solution? To me a process of solving problem is rewarding. What you cite inside the spoiler is a correct general answer, but not a solution. So I take your answer as an opinion that this problem is too difficult for this forum and I should not have posted it here.

As I already stated, the problem is complex. However, for the actual answer, the number of cards to skip is an integer and the probability is a rational number. And you don't need to use any differential equations, or natural logarithm for the solution. <_<

P.S. Armcie actually cited a correct approach earlier in this topic.

Edited September 27, 2008 by Prime

[bonanova]

As long as you simply offer opinions, Denizens can't critique you - they can only stand in awe of your brilliance.

How long before you grace this forum with, for example, the "correct" winning probability for Prof T?

Hint: If you don't want to disclose all your breakthrough thought processes, you could just give your opinion of the answer and let someone here prove that you are or are not right.

[Prime]

As long as you simply offer opinions, Denizens can't critique you - they can only stand in awe of your brilliance.

How long before you grace this forum with, for example, the "correct" winning probability for Prof T?

Hint: If you don't want to disclose all your breakthrough thought processes, you could just give your opinion of the answer and let someone here prove that you are or are not right.

Here is a simple proof that 25% is incorrect probability estimate when you skip 1/2 of the deck:

Take a deck of 4 cards with the numbers 1, 2, 3, and 4. Here are all 4!=24 possible permutations with those winning using "skip 1/2" strategy marked with "+" and loosing marked with "-".

1234 - 2134 - 3124+ 4123-

1243+ 2143+ 3142+ 4132-

1324+ 2314+ 3214+ 4213-

1342+ 2341+ 3241+ 4231-

1423 - 2413 - 3412 - 4312-

1432 - 2431 - 3421 - 4321-

There are 10 cases, where you win with "skip 1/2" strategy for a total probability of 10/24 = 5/12, which is greater than 25%. QED.

Also, notice that if we adopted "skip 1 card" strategy (picking first larger card thereafter), we would win in 11 out of 24 cases.

I'm not going to show my derivation for the formula to get the correct probability by other than heuristics method. As it may spoil the fun for those who want to solve the problem on their own.

I sense, you are under impression that I claimed to have solved the problem without differential equations just to brag. But I had another motive in addition to that. My statement was also meant as hint that the problem may be solved in such a way. You can derive series using combinatorial formulas and/or complex equations with probability fractions.

[Prime]

As long as you simply offer opinions, Denizens can't critique you - they can only stand in awe of your brilliance.

How long before you grace this forum with, for example, the "correct" winning probability for Prof T?

Hint: If you don't want to disclose all your breakthrough thought processes, you could just give your opinion of the answer and let someone here prove that you are or are not right.

And here is "my opinion of the answer" for the probability to win when skipping first 50 cards out of 100. It's just a bit over 34.90% (which is less than the optimal 1/e).

Although, I don't really see the point of that exercise.

[Guest]

And here is "my opinion of the answer" for the probability to win when skipping first 50 cards out of 100. It's just a bit over 34.90% (which is less than the optimal 1/e).

Although, I don't really see the point of that exercise.

I claim that you will come to my %33 result, that I wrote here before.

[bonanova]

The process was simulated 100,000 times each, for values of N = 10, 20, 50 and 100, and the results were averaged.

Winning probability [expressed as percentage] was plotted as the number of skipped cards increased from 1 to N-1.

Probabilities for small values of N are slightly higher than the theoretical values, but they decrease as N increases.

At N=100 the results are decreasing only slightly as they approach the theoretical limit of 1/e for N/e skipped cards.

A simulation for N=1000 cards [not shown] gave results indistinguishable from the theoretical values.

Note that the winning probability for N/2 skipped cards also approaches the theoretical value of 349...

[Prime]

The process was simulated 100,000 times each, for values of N = 10, 20, 50 and 100, and the results were averaged.

Winning probability [expressed as percentage] was plotted as the number of skipped cards increased from 1 to N-1.

Probabilities for small values of N are slightly higher than the theoretical values, but they decrease as N increases.

At N=100 the results are decreasing only slightly as they approach the theoretical limit of 1/e for N/e skipped cards.

A simulation for N=1000 cards [not shown] gave results indistinguishable from the theoretical values.

Note that the winning probability for N/2 skipped cards also approaches the theoretical value of 349...

That's quite a research! How fast do you need to shuffle the cards to conduct 100,000 experiments?

So experimental data largely conforms to the formula that I hold secret. The solution to the problem still remains: Show the derivation of a formula that estimates the theoretical probability exactly.

[Prime]

...

But we should take into account another probability: If the third highest figure is in the second 50 cards, you will fail again if you pick it before the highest one. The chance of 3. to be in second 50 cards is (while 2. highest is in the 2. 50 cards and it comes after first highest) 1/8 * 1/2 = 1/16. We must multiply this again with 1/2 because the third highest, being though in the second 50, may come after the first highest. = 1/32 .By this way we get a series of

1/2 + 1/8 + 1/32 + 1/128 + 1/512 ..... = %66.6

...

I claim that you will come to my %33 result, that I wrote here before.

I don't believe so. You can check my example, which shows that 25% estimate is wrong. It also shows that 33% is wrong.

Here is my analysis of where your line of reasoning may be wrong.

I see a problem with your reasoning at the third step: "We must multiply this again with 1/2 because the third highest, being though in the second 50, may come after the first highest". How do you figure the probability of 1/2 for hiding the 3rd largest card behind the first largest, while the 2nd largest is already hiding there? Try a deck of 6 cards. The last cards 3 for your 3rd step where second largest (2) is already behind the 1st largest (1) has the following arrangements:

123

132

312 -- only this last arrangement fails to win.

So the probability is 1/3, not 1/2 as you estimated. You can experiment with larger decks and find that probability of 1/2 to hide the next largest card behind the largest card only true for the second largest card.

So the first two terms of your sequence (1/2 + 1/8) are correct. The rest of them are not.