wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Can you help this guy keep the maximal money
        
(Message started by: wonderful on Aug 12^th, 2008, 3:08pm)

Title: Can you help this guy keep the maximal money
Post by wonderful on Aug 12^th, 2008, 3:08pm

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!

Title: Re: Can you help this guy keep the maximal money
Post by Eigenray on Aug 13^th, 2008, 12:37am

Does the concert cost less than [hide]$43[/hide]?

Actually, I'm not sure what model to use, because [hide]either A isn't very bright, or he must think B isn't very bright[/hide].

Title: Re: Can you help this guy keep the maximal money
Post by towr on Aug 13^th, 2008, 1:32am

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.

Title: Re: Can you help this guy keep the maximal money
Post by Eigenray on Aug 13^th, 2008, 3:30am

[hideb]C(1) = 0
C(n) = min { max[1+C(n-k+1), 16+C(k-1)], k=2...n }[/hideb]
gives C(100) = [hide]43[/hide] as the worst-case cost.

Edit: Whoops!

Title: Re: Can you help this guy keep the maximal money
Post by wonderful on Aug 13^th, 2008, 10:08pm

Eigenray,

Your approach is very interesting. Can you elaborate on it a little bit?

Have A Great Day!

Title: Re: Can you help this guy keep the maximal money
Post by Eigenray on Aug 14^th, 2008, 1:03am

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!

Title: Re: Can you help this guy keep the maximal money
Post by towr on Aug 14^th, 2008, 2:31am

on 08/14/08 at 01:03:49, 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].

Title: Re: Can you help this guy keep the maximal money
Post by Eigenray on Aug 14^th, 2008, 2:46am

You're right of course. And I had double checked it too, because I thought I had it wrong when I posted it...

Title: Re: Can you help this guy keep the maximal money
Post by towr on Aug 14^th, 2008, 3:03am

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]

Title: Re: Can you help this guy keep the maximal money
Post by Hippo on Aug 14^th, 2008, 6:31am

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.

Title: Re: Can you help this guy keep the maximal money
Post by Eigenray on Aug 14^th, 2008, 1:19pm

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)¹⁶, and a = -16/log b ~ 7.63.
So C(n) ~ 7.63 log n ~ 5.29 lg n. Heuristically.

Title: Re: Can you help this guy keep the maximal money
Post by Hippo on Aug 15^th, 2008, 8:23am

Yes it is A_n=A_n-1+A_n-16 recursion with A₀=...=A₁₅=1.
So http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gif¹⁶- http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gif¹⁵-1=0 ...