Here is the last of the brain teasers that arose from our annual family gathering a week ago. The game is the “1000 Card Challenge.” Please read the puzzle and vote without reading the responses. If you have a way to beat the game, please only post it in a spoiler box, at least for the first dozen responses or so. While the rules of the game are very simple and there are no “tricks” in the rules, it is OK to post a question without spoiler boxes if I have not made things clear enough.
Here goes:
This is the Thousand Card Challenge:
I have one thousand flash cards. Each card has a different number printed on the front of the card. The number printed on a card might be any integer, large or small. The number could even be a negative number. However, the number will never contain so many digits that you cannot tell easily what it is. You are not allowed to see the front of the cards before the game.
The flash cards are fairly shuffled and thus in random order. If you accept the challenge, you will pay me five dollars to play. I will place the shuffled cards face down in front of me. I will begin turning the cards over slowly, one by one. When you see a card that you think has the highest number of any in the entire stack of a thousand cards, you must say “Stop.”
At this point I will quit turning cards and we will look together through all of the thousand cards. If the card you have chosen indeed has the largest number of all, you win the game and I will pay you $40.00. If the number on this card is not the largest in the stack of a thousand cards, then you lose and get nothing. If you do not tell me to stop somewhere and we run through the whole stack, then you lose and get nothing. Also: Once I turn over a card, any cards previously turned cannot be chosen.
Therefore, the only way you win is if you tell me to stop at a just-turned card during the game, and then we immediately check together through the complete stack and confirm that the card chosen indeed has the highest number.
You may play this game as often as you like. However, you must pay me $5.00 every time you choose to play. In addition, each time you play I will have a completely different set of a thousand cards with different numbers from the previous game. I am not above rigging the numbers so that high and low numbers in any given stack of cards will vary greatly from the previous stack. I want to win, after all. However, I will promise that the cards are always fairly shuffled into random order and that each card in the stack has a unique integer.
I’ll play. I may have gotten this completely wrong, tear apart my logic here:
[spoiler]My strategy is to note the highest card in the first 500 cards, and then pick the first card in the second 500 that beats it. I lose half the games off the bat, because the highest card in the deck is the one I note, so the second half goes by without me picking a card. For the rest of the games, based on my brute forcing random numbers in excel, the odds are very good that either the 2nd highest card is in the first half, thus ensuring that I pick the highest card, or I pick the 3rd or 4th or 5th highest card and the actual highest card luckily comes up before any of the others.
There’s probably a mathematical formula here to prove this; I ran through a few different deck sizes, stopping at 100, and the odds didn’t seem to change. Based on my (admittedly) very small sample size, I expect to win about 3 out of every 8 games. I’ll pay $40 to win $120.
There may be a more optimal strategy, and if I were going to be betting large sums I’d want to run it through an actual simulation rather than just eyeballing lists in excel, but there you go.[/spoiler]
I would not play the game. I would like to deal. The payout is 8 to 1. The player has a 1 in 1000 chance of picking the correct card. Since I’m allowed to stack each new deck with any integers, I would count on most players to out-think themselves.
You are paying 8:1 odds so I would let the first 7/8th of the deck pass and then pick the first card of the remaining 125 that is higher than the highest previous 875 cards. If none occur, I’m out. I think doing this would have me break even rather than make a profit, so perhaps I push my luck and let 900 cards go by and choose one of the last 100, but this is all gut feeling
I’m certain that this strategy won’t work. There’s a 90% chance that the highest card is in the first 900, so 9/10 of the time you’ll definitely lose. Of the remaining 10% of the time, there’s still a nonzero chance that there are two cards higher than any of the first 900; when there are at least two such cards, half the time you’ll still lose because the lower of those two high cards will appear first, and you’ll pick it. You’d need better than 8:1 odds to make this strategy work.
As I understand it, you should let the first 368 cards go by, to get a sense of range. Note the highest card in those 368. Choose the next card that’s higher than that highest card.
36.8% of the time, you’ll lose straight off, because the highest card will have been in those 368. Another third (more or less) of the time, there’ll be more than one card in the remaining 632 cards that’s higher than any in the first 368, AND the higher cards will be in ascending order, meaning you’ll not choose the very highest card. But about 30% of the time, the next highest card will be the highest in the entire set.
I’ve seen this problem before - it’s often called “the marriage problem,” the idea being that you have to find the best spouse for yourself without having met all the potential spouses you will ever meet.
I haven’t read the previous responses.
[spoiler]It works out to, you look at the first 1/e cards and reject them out of hand, but remember the largest number you saw. Next time you see a card higher than the highest you had seen previously, choose that one.
You win about 1/e of the time. 1/e is ~36%.
So you look at 360 cards, remember the largest, and then hope the next card you see larger than the largest is the largest in the stack, and you’ll win about 36% of the time.[/spoiler]
The problem for the player is to guess the highest number that the dealer has selected for each new deck.
The player has no idea which one thousand numbers the dealer has selected. -500 to 500? -2000 to 1? 10 to 10,000? 1234 to 4321? The chosen numbers always change.
In the Secretary problem, the number of applicants is known. In the 1000 Card Challenge, there would always be 1000 numbers, but the highest number would always change.
In the secretary problem, the quality of the secretary is comparable to the highest number in the card challenge. The number of applicants is comparable to the number of cards in the card challenge. I’m really not seeing a difference between the problems.
The dealer gets to change the highest number in every new deck. In other words, the goalpost will always be moving. (If I understand the rules correctly.)
You could figure the odds for guessing the highest number in the deck but you would have to read the dealers mind to discover which number he chose for each deck.