The Magic Café
Username:
Password:
[ Lost Password ]
  [ Forgot Username ]
The Magic Cafe Forum Index » » Puzzle me this... » » Want to bet? (0 Likes) Printer Friendly Version

magicjohn2278
View Profile
Special user
Isle of Man UK
536 Posts

Profile of magicjohn2278
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
View Profile
Inner circle
USA
4283 Posts

Profile of Daegs
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
View Profile
Special user
St. Louis, MO
996 Posts

Profile of stanalger
I'd take the bet.
magicjohn2278
View Profile
Special user
Isle of Man UK
536 Posts

Profile of magicjohn2278
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
View Profile
Inner circle
Sweden
1143 Posts

Profile of TomasB
As long as you pay over 17 bucks, which you do since you offer 50, I'm playing.

/Tomas
magicjohn2278
View Profile
Special user
Isle of Man UK
536 Posts

Profile of magicjohn2278
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
View Profile
Inner circle
Sweden
1143 Posts

Profile of TomasB
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
View Profile
Special user
Isle of Man UK
536 Posts

Profile of magicjohn2278
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
View Profile
Inner circle
Sweden
1143 Posts

Profile of TomasB
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
View Profile
Special user
Isle of Man UK
536 Posts

Profile of magicjohn2278
.. 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
View Profile
Inner circle
Sweden
1143 Posts

Profile of TomasB
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
View Profile
Inner circle
Sweden
1143 Posts

Profile of TomasB
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
View Profile
Special user
Isle of Man UK
536 Posts

Profile of magicjohn2278
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
View Profile
Inner circle
Sweden
1143 Posts

Profile of TomasB
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
View Profile
Inner circle
Sweden
1143 Posts

Profile of TomasB
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
View Profile
Inner circle
USA
4283 Posts

Profile of Daegs
Yes.... but it could be 37% of the way through, or .37 * N?
TomasB
View Profile
Inner circle
Sweden
1143 Posts

Profile of TomasB
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
View Profile
Special user
St. Louis, MO
996 Posts

Profile of stanalger
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)
[ Top of Page ]
All content & postings Copyright © 2001-2020 Steve Brooks. All Rights Reserved.
This page was created in 0.17 seconds requiring 5 database queries.
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 <

ROTFL Billions and billions served! ROTFL