The Magic Cafe Forum Index » » Puzzle me this... » » Want to bet? (0 Likes) magicjohn2278 Special user Isle of Man UK 536 Posts  Posted: Mar 21, 2006 09:35 am 0 In the absence of a few new puzzles lately, I found this - (blatently stolen from another web-site!) I offer you the following deal: I have 100 blank cards. I am going to write a positive integer on each card, all different and leaving none blank. You can then turn over as many or as few cards as you wish, one at a time and look at what I have written. If the last card you turn over is the highest in the deck, you win, otherwise, you lose. If you win, I give you \$50, if you lose, you give me just \$10. Would you accept this challenge? Daegs Inner circle USA 4283 Posts  Posted: Mar 21, 2006 04:16 pm 0 No.... you'd have 1:100 chance of winning, and you are only getting 5:1 on your money... Make it \$1 against \$100 and I'll take it. stanalger Special user St. Louis, MO 996 Posts  Posted: Mar 21, 2006 05:44 pm 0 I'd take the bet. magicjohn2278 Special user Isle of Man UK 536 Posts  Posted: Mar 21, 2006 05:58 pm 0 So far the scores are: 1 to Daegs with the answer "No", (because he got the answer right. He can't see a way of beating me and therefore obviously shouldn't take the gamble.) and 1 to stanalger with the answer "Yes", (because he got the answer right. - assuming of course that he has a strategy that will beat me!) any more takers? TomasB Inner circle Sweden 1143 Posts  Posted: Mar 22, 2006 02:48 am 0 As long as you pay over 17 bucks, which you do since you offer 50, I'm playing. /Tomas magicjohn2278 Special user Isle of Man UK 536 Posts  Posted: Mar 22, 2006 03:34 am 0 Half a point to Tomas for trying! I really can't see any way you can win 10 out of 17 times, without cheating! (But perhaps you can?) TomasB Inner circle Sweden 1143 Posts  Posted: Mar 22, 2006 03:41 am 0 I thought that with 0.37 probability of winning my expected earnings would be 0.37*18-0.63*10=0.36 so if you pay 18 dollars when I win I earn 36 cents a game on an average. /Tomas magicjohn2278 Special user Isle of Man UK 536 Posts  Posted: Mar 22, 2006 04:08 am 0 Surprisingly (to me) that sounds right! (The 0.37 probabllity of winning surprised me - I thought it was 0.25 plus a bit! - Obviously the bit is a lot bigger than I thought!) TomasB Inner circle Sweden 1143 Posts  Posted: Mar 22, 2006 07:08 am 0 I must admit that I cheated and simulated to get the result. If you look at the N first cards then stop at the first card that is larger than all cards in the N-group you win if The largest card is _not_ among the first N (probability (100-N)/100) AND none of the cards before the largest card are bigger than the N-group. (Can someone reason me through how to get that probability?) Maximize that with regard to N. You can also minimize the following: You fail if The largest card is among the first N (probability N/100) OR The card is among the last 100-N cards (probability (100-N)/100)) AND at least one before it is larger than the cards in the N-group. According to the simulations I made it's a good strategy to wait 37 cards and then select the biggest one after that. While that seems to be a winning strategy I have no way of saying that it is the optimal strategy. There might be a better one. Help? /Tomas magicjohn2278 Special user Isle of Man UK 536 Posts  Posted: Mar 22, 2006 07:27 am 0 .. I can't see it! Surely that for an optimal result N should be 50? (It makes the explaination much simpler too!) Say I have numbered the cards 1 to 100 (obviously I haven't as you would just look for the 100 card and win every time! But 100 is the biggest number and 99 is the next biggest....) If you look at the first 50 cards and note the highest number, then go through the next 50 and stop on a number higher than the one you saw in the first 50, then in simple terms you will win 1 in 4 plays - Probability of winning 0.25. The 100 card is in either the first 50 cards or the second 50 with a probability of 0.5 The 99 card is in either the first 50 or the second 50 with a probability of 0.5 So First 50 ---- Second 50 ---- outcome 100.............99............lose 99..............100...........win 100 99........................lose .................99 100.......lose* Giving you a probability of winning of 0.25 * At least that was the answer that was given. - Which I concluded was wrong (and that's why I posted it here.) The last case is shown as a lose, as you might see the 98 card in the first 50 and stop on the 99. However, this is not always the case and I guess that you have an even chance of winning this situation too (just guessing). It all depends on whether you see the 99 card or the 100 first in the second 50. Taking this to it's logical (but unlikely) conclusion even if the first half comprises all the low cards 1 to 50, then there is still a remote chance (1 in 50) that you could win if the 100 card happened to be the 51st card. Anyone care to check the actual probability! TomasB Inner circle Sweden 1143 Posts  Posted: Mar 22, 2006 07:43 am 0 John, you could, for example, lose if you see the 98th card before the 100th if none larger than 97 is among the first 50. So the reasoning is faulty, yet your strategy is good. Edit: Ooops, just saw that you wrote about that flaw yourself. /Tomas TomasB Inner circle Sweden 1143 Posts  Posted: Mar 22, 2006 12:15 pm 0 The solution popped up in my head on the way home from work. Feel free to jump in if any detail is wrong. Let's call the biggest value X. Given that X is among the last 100-N cards (probability (100-N)/100)) it has a square distribution of 1/(100-N) of being in any of those positions. If it has zero cards before it (ie it comes right after N) the probability is 1 of finding it. If it has M cards before it (not counting the first N cards) you find it if none of those M is bigger than the biggest one among the N first. So what is the probability? The reasoning that popped up in my head during the drive home was this: There is exactly _one_ biggest item among the first N+M items. It has the same probability of being anywhere among those. What we desire is it to be among the first N which means that the probability of that happening is N/(N+M). Now we can write the full expression of the probability to find the biggest item if we first look at N items then stop att the first one bigger than all of them. P(N)=(100-N)/100*( 1/(100-N)*N/(N+0) + 1/(100-N)*N/(N+1) + 1/(100-N)*N/(N+2) + ... + 1/(100-N)*N/99 ) which is easier written as P(N)=N/100*sum[i=N:99](1/i) To save time calculating I can make a recursive formula P(N+1)=(N+1)/100*sum[i=N+1:99](1/i)=(N+1)/100*(100/N*P(N)-1/N)=(N+1)/N*(P(N)- 0.01) Since I know the result is around 37 due to the simulations I'll start with P(35) and work my way upwards. P(35)=35/100*sum[i=35:99](1/i)=0,370786... P(36)=36/35*(P(35)-0.01)=0,3710145955... P(37)=37/36*(P(36)-0.01)=0,3710427787... P(38)=38/37*(P(37)-0.01)=0,37080069... which shows us that the maximum probability of succeeding is when N=37 and the probability is about 0.37104 for success. /Tomas magicjohn2278 Special user Isle of Man UK 536 Posts  Posted: Mar 22, 2006 12:22 pm 0 Quote:On 2006-03-22 13:15, TomasB wrote: The solution popped up in my head on the way home from work. P(N)=(100-N)/100*( 1/(100-N)*N/(N+0) + 1/(100-N)*N/(N+1) + 1/(100-N)*N/(N+2) + ... + 1/(100-N)*N/99 ) P(N)=N/100*sum[i=N:99](1/i) P(N+1)=(N+1)/100*sum[i=N+1:99](1/i)=(N+1)/100*(100/N*P(N)-1/N)=(N+1)/N*(P(N)- 0.01) P(35)=35/100*sum[i=35:99](1/i)=0,370786... P(36)=36/35*(P(35)-0.01)=0,3710145955... P(37)=37/36*(P(36)-0.01)=0,3710427787... P(38)=38/37*(P(37)-0.01)=0,37080069... /Tomas I hope you don't DRIVE home from work... shouldn't you be concentrating on the road? TomasB Inner circle Sweden 1143 Posts  Posted: Mar 23, 2006 04:21 am 0 Hehehe, well it'd be torture to not follow through a thought like that regardless what I'm doing. Yes, I drive from work. A followup question I don't have an answer to yet is: What should your strategy be if you do not know how many cards there are, but you know that there are much more than 100? Compare that to random dating: How many girls do you need to date before you stop at the next one that is better than all the girls you have dated so far? Here you don't have a clear upper limit of how many dateable girls there are. My GUESS is that the sum P(N,T)=N/T*sum[i=N:T-1](1/i) goes towards 1/e (approx 0.368) for N=37 when T goes towards infinity and that that is the optimum N. No idea how to show that though, yet. If that is true the result would be that you should always let the first 37 dates pass if you know that there is a big number of possible dates. No idea if that is true or even if P(37,T) has a limit when T goes towards infinity. Anyone have any idea how to show that or disprove it? /Tomas TomasB Inner circle Sweden 1143 Posts  Posted: Mar 23, 2006 05:06 am 0 I just think I found a way to disprove it. Assume there is a limit to the sum for a fixed N. That means that 1/T*sum[i=N:T-1](1/i) must have a limit > 0 when T goes to infinity. Call that limit C. That means that P(N,inf)=N*C. But if we chose N>1/C the result is bigger than 1 which is a contradiction as P can't be > 1. Hence it's safe to assume that the limit of 1/T*sum[i=N:T-1](1/i) is 0 and that N is dependant of T so it can't be fixed to anything. In other words, it can't be fixed to 37 or any other value but has to be increased with the number of cards used. /Tomas Daegs Inner circle USA 4283 Posts  Posted: Mar 24, 2006 09:11 pm 0 Yes.... but it could be 37% of the way through, or .37 * N? TomasB Inner circle Sweden 1143 Posts  Posted: Mar 25, 2006 01:01 am 0 It sure can. The optimum N _could_ be 0.37*T but I do not know if that is the case. Is it? /Tomas stanalger Special user St. Louis, MO 996 Posts  Posted: Mar 25, 2006 10:54 am 0 http://www.amazon.com/gp/product/0883855......ing=UTF8 This problem appeared in Martin Gardner's Mathematical Games column in 1960. And to tie it in to "Puzzle me this..."'s most frequently mentioned game show host, google "revenge Philip Newman." The Magic Cafe Forum Index » » Puzzle me this... » » Want to bet? (0 Likes)
 The views and comments expressed on The Magic Café are not necessarily those of The Magic Café, Steve Brooks, or Steve Brooks Magic. > Privacy Statement <   