Author |
Topic: Can you help this guy keep the maximal money (Read 1328 times) |
|
wonderful
Full Member
Posts: 203
|
 |
Can you help this guy keep the maximal money
« on: Aug 12th, 2008, 3:08pm » |
 Quote  Modify
|
A gives B $ 50 and challanges B:
- A will think of a number from 1 to 100. Let's call this number x.
- B's responsibility is to find out what that number is.
- To do so, B will go throught a process of investigating x. In particular, B can speak out a number as long as he gives A $1. If this number is smaller than or equal to x , A will say "It is not correct, give me some money !". If this number is greater than x, A will reply:"You're almost there !" and B has to give A additional $15.
The above process goes on until B has enough confidence to tell A what is x. If B is correct he can keep all the reamaining $. Otherwise, B has to invite A to a concert.
Can you help B find out the optimal strategy?
Have A Great Day!
|
| « Last Edit: Aug 12th, 2008, 4:21pm by wonderful » |
 IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
|
Re: Can you help this guy keep the maximal money
« Reply #1 on: Aug 13th, 2008, 12:37am » |
Quote Modify
|
Does the concert cost less than $43?
Actually, I'm not sure what model to use, because either A isn't very bright, or he must think B isn't very bright.
|
| « Last Edit: Aug 13th, 2008, 12:45am by Eigenray » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Can you help this guy keep the maximal money
« Reply #2 on: Aug 13th, 2008, 1:32am » |
Quote Modify
|
B can break even at least, but in the worst case I don't see how he could end up with more than a few dollars. That $15 penalty really cuts into the profits.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Can you help this guy keep the maximal money
« Reply #3 on: Aug 13th, 2008, 3:30am » |
Quote Modify
|
| hidden: | C(1) = 0
C(n) = min { max[1+C(n-k+1), 16+C(k-1)], k=2...n } |
gives C(100) = 43 as the worst-case cost.
Edit: Whoops!
|
| « Last Edit: Aug 14th, 2008, 2:42am by Eigenray » |
IP Logged |
|
|
|
wonderful
Full Member
Posts: 203
|
|
Re: Can you help this guy keep the maximal money
« Reply #4 on: Aug 13th, 2008, 10:08pm » |
Quote Modify
|
Eigenray,
Your approach is very interesting. Can you elaborate on it a little bit?
Have A Great Day!
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Can you help this guy keep the maximal money
« Reply #5 on: Aug 14th, 2008, 1:03am » |
Quote Modify
|
C(n) is the worst-case cost to find x when it is known to lie in an interval of size n, WLOG [1,n]. If you guess k, then either: you pay $1, and you've narrowed it down to [k,n]; or you pay $16, and you've narrowed it down to [1,k-1]. Therefore, if you guess k, you won't have to pay more than max[ 1+C(n-k+1), 16+C(k-1) ] so you pick k to minimize this.
Finding the Nash equilibrium is more tricky. A is going to try to pick x to maximize the amount B pays; since B knows this, this strategy might not be optimal. But B can guarantee a profit of at least $7 in any case.
Edit: Whoops!
|
| « Last Edit: Aug 14th, 2008, 2:43am by Eigenray » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Can you help this guy keep the maximal money
« Reply #6 on: Aug 14th, 2008, 2:31am » |
Quote Modify
|
on Aug 14th, 2008, 1:03am, Eigenray wrote:| If you guess k, then either: you pay $1, and you've narrowed it down to [1,k]; or you pay $16, and you've narrowed it down to [k+1,n]. |
|
Shouldn't that be reversed?
If you pay $16, then your number was larger, so x must lie in [1..k-1]; and if you pay $1, your number was smaller, so x lies in [k..n].
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Can you help this guy keep the maximal money
« Reply #7 on: Aug 14th, 2008, 2:46am » |
Quote Modify
|
You're right of course. And I had double checked it too, because I thought I had it wrong when I posted it...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Can you help this guy keep the maximal money
« Reply #8 on: Aug 14th, 2008, 3:03am » |
Quote Modify
|
c(1) = 0
c(n) = n+14, for 1 < n <= 18
c(n) = ceil((sqrt(1+8*(n-16))-1)/2) + 30, for n >= 16
(Granted, I haven't proved it yet, but the pattern seems to be there)
[edit]Nevermind, it seems to break at 188[/edit]
|
| « Last Edit: Aug 14th, 2008, 3:08am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Can you help this guy keep the maximal money
« Reply #9 on: Aug 14th, 2008, 6:31am » |
Quote Modify
|
I didn't actually think about it, I just want to note a variant I have sloved 20 year ago ... with costs 1,2 this leads to Fibonacci / golden rate solution.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Can you help this guy keep the maximal money
« Reply #10 on: Aug 14th, 2008, 1:19pm » |
Quote Modify
|
Certainly C(n) < 16 lg n...
Heuristically, suppose C(n) ~ a*log n, and that the optimal choice of k is k(n) ~ b*n. Then we should have
a log n = 1 + a log((1-b)n) = 16 + a log(bn),
which gives
a log (1/(1-b)) = 1, a log (1/b) = 16
b ~ 0.123 is a root of b = (1-b)16, and a = -16/log b ~ 7.63.
So C(n) ~ 7.63 log n ~ 5.29 lg n. Heuristically.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Can you help this guy keep the maximal money
« Reply #11 on: Aug 15th, 2008, 8:23am » |
Quote Modify
|
Yes it is An=An-1+An-16 recursion with A0=...=A15=1.
So  16- 15-1=0 ...
|
| « Last Edit: Aug 15th, 2008, 8:23am by Hippo » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print