February 2007
Answer:
A player will ensure he wins at least 50% of the time by choosing to receive a new number when his original number is less than (sqrt(5)-1)/2 = .6180+.
It should be clear that we need only consider strategies of the form, choose a new number if the original number is < x otherwise keep the original number. Suppose player A uses threshold x and player B uses threshold y. Then it can be shown that the probability, p, that A will win is
p=.5*(1+x-y-x*y+y*y+x*y*y-x*x*y) for x <= y
p=.5*(1+x-y-x*x+x*y+x*y*y-x*x*y) for x >= y
or
p=.5+.5*(x-y)*(1-y-x*y) for x <= y
p=.5+.5*(x-y)*(1-x-x*y) for x >= y
Suppose A chooses x=(sqrt(5)-1)/2. Note x*x+x=1.
Now if y > x then x*y+y > 1 so (x-y) < 0 and (1-y-x*y) < 0 so
(x-y)*(1-y-x*y) > 0 which implies p > .5.
Also if y < x then x*y+x < 1 so (x-y) > 0 and (1-x-x*y) > 0
so (x-y)*(1-x-x*y) > 0 which implies p > .5.
So if A chooses x = (sqrt(5)-1)/2 he will win more than 50% of the time unless B chooses y = (sqrt(5)-1)/2 also in which case he will win exactly 50% of the time.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com