I thought up this question while eating at a Chinese restaurant this summer, and I realized I had no idea what the answer was. I also didn't have the foggiest idea how to go about solving it. So here it is for the world at large. Answer this question correctly and win your choice of fifteen bucks in cold hard cash or a Rubik's Cube. E-mail your answer to abodeman@yahoo.com. Make sure to include a proof or at least a detailed explanation of your answer.
Note that even though this question looks daunting at first, it's not hard to understand once you've figured out what I'm saying. I just have to word things carefully and cover all my bases so I'm not leaving anything out.
You and I are playing a game. There are 100 cards laying face-down on a table. I have marked none, some, or all of those cards on their faces, and the rest are left blank. It is equally likely that none of the cards are marked, or exactly one card is marked, or exactly two cards are marked, or any given number of cards are marked (up to all 100). (Note that this is not the same as saying that any given card has a 50% chance of being marked.) Here's how the game is played.
Your turn begins with turning over any one card. You can then see whether or not that card is marked. You then consider this card and any you have previously turned over to be a perfect sample of the entire card population, and then extrapolate to all 100 cards and guess how many are marked. Another way of saying this is that you take a look at all the cards you have turned over and calculate the percentage that are marked (say, 9 of 17 are marked, so 52.94%), and then you guess, to the nearest whole number (rounding up in cases such as 43.5% or 72.5%), how many of the 100 are marked, based on this percentage (in our example, you would guess that 53 cards are marked). You win the game if you guess correctly. If you don't guess correctly, you take another turn--flip over another card and make another guess.
An example will probably help. Suppose that 67 cards out of the 100 are marked. The first card you flip over happens to be marked. Since 100% of the face-up cards are marked, you will guess that 100 cards are marked. This is an incorrect guess, so you flip over another card. As it turns out, this card is not marked. Now 50% of the cards that you see are marked, so you guess that 50 cards are marked. You're wrong again, so you flip over a third card, which is not marked. Now 33.33% of your cards are marked, so you round that to the nearest integer and guess that 33 cards are marked. Since this was also an incorrect answer, you turn over a fourth card, which is marked. Your percentage is back up to 50%, so, in accordance with the rules stated above, you again guess 50 cards (never mind the fact that this would be stupid, since you "know" that this answer is wrong). Flipping over the fifth card, which happens to be marked, brings your percentage up to 60%, but your guess of 60 cards is wrong again. Finally, when you flip over your sixth card and find that it's marked, you calculate that 66.67% of the cards you can see are marked. So, you round to the nearest integer, which is 67, and guess that 67 cards are marked. Lo and behold, you have won the game. You took six turns.
It's obvious that eventually you'll guess the right number; after all, once you've flipped over all 100 cards, you can't lose. The question is this: What is the expected number of moves you will take before you guess correctly? Note that you only have to guess the correct number; you don't have to be absolutely certain it's correct (since the only way you can be absolutely certain is if you actually do flip over all 100 cards).
This question is worth fifteen dollars, or a Rubik's Cube (your choice). However, you must include a proof or at least a detailed explanation of how you arrived at your answer, since I don't know what the correct answer is.
If you'd like to win more than that, you can consider the game with one additional stipulation: No number can be guessed more than once. This eliminates the "stupid factor" of the above rules, meaning that if 66.67% of the cards you can see are marked, but you've already guessed 67 before, you won't guess 67 again. Instead, you'll guess the closest integer to 66.67 that you haven't already guessed, which is 66 (or, if you've already guessed 66 too, then it'll be 68). Another situation arises when, say, 50% of the cards showing are marked, you've already guessed 50, but 49 and 51 are both available options. Which one of these choices do you choose? I don't have a definitive answer. If I were writing a computer algorithm for playing this game, I would say that you would choose between 49 and 51 at random, with a 50% probability of choosing either one. But that makes it harder to solve the question (I think), so you might want to specify that the higher of the two numbers is chosen, or the lower of the two, or whatever. Just make it clear what your rule is in this case. Of course, if in this example 49 had already been guessed, then it leaves you with no choice; 51 will be your guess. This additional stipulation for the game (eliminating the "stupid factor") increases the difficulty of the question (I think), so it's worth more (somewhere around twenty-five dollars, probably).
This is an extremely complicated question, and it's currently 2:55 a.m., so there's probably something that's not clear. If you're confused about what the question is asking, don't hesitate to e-mail me at abodeman@yahoo.com about it, and I'll send you a clarification. I'll probably also change the wording of the question on this page to make it clearer, if that should be necessary.
From here you can return to zifyoip.com.