Fog Creek Software
Discussion Board




Pick a number...

Two people pick a number (1,2,3... no upper limit) secretly.
Lowest number wins $1 EXCEPT when the Highest number = Lowest Number + 1 in which case Lowest number LOSES $2. Nothing happens in case of tie. Game gets played repeatedly over a long time.

Develop a strategy that cannot be reliably beaten even if someone else knows the strategy.

WanFactory
Friday, June 17, 2005

Always pick two.  For 3...n, you are the winner.  For 1 you are the winner of $2 since 1 (lowest) + 1 = 2 (highest).  2 is tie.  This strategy works until they realize you're always picking 2, in which case they pick 2, you always tie until everyone gets tired & go home.

But you never lose any money.

tjk
Friday, June 17, 2005

scratch that.  When they realize that you're picking 2, they'll pick 3 and you lose.  So, the strategy is play once and go home.

tjk
Friday, June 17, 2005

Let the range in of n number!.
if you choose 1
Win =  (n-2) cases  1$ each.
Loose= 1 case 2 $
Total profit= n-4 $.

Now do the same taking 2 $.

Win =  (n-3) cases  1$ each.
Win =  1 cases  2$ .
Loose= 1 case 2 $
Total profit= n-3 $.

Hence choose the 2 $.

further adding it can be continued if only the result is displayed by the system not the number choosen !!!@@@.

Deepak pant(STM)
Friday, June 17, 2005

Hint: if someone knows what number you will pick, they can beat you. So the unbeatable strategy must be somewhat random. So the question is how to optimally distribute your picks. There is a unique solution.

WanFactory
Monday, June 20, 2005

1. Start with number k chosen randomly.
2. Let N=k(k+1)/2. In each subsequent round, choose the number as per the following distribution:
With probability 1/N, pick k
With prob 2/N, pick k-1.
With 3/N, pick k-2
.....
With j/N pick k-j+1
.....
With k/N pick 1.

Intiution: Randomized strategy with higher chances of your picking up smaller numbers than the opponent.

Proof:
Now given that the opponent knows this strategy, it is obvious that his best choice is to choose a number between 1 and k-1. If he choses a number greater than k-1, his expected profit is negative.

Let the opponent chose a number (k-j) where 1<=j<=k-1.
Expected value of the opponents profit = -(k/N+(k-1)/N....j/N ) + 2(j-1)/N + (j-2)/N + ...1/N

This simplifies to (j^2 - 2j -2)/N -1.

This expression is maximized for j=(k-1) because j<=k-1.
Hence maximum value of this expression is simplified to (k^2 -9k+2)/k(k+1).

For k<=4, the above expression (expected profit of the opponent) is always negative.

This means if we initially pick our number randomly from numbers 1 to 4, the above strategy always ensures that the opponent can not beat us.

Mithun
Tuesday, June 21, 2005

<i>Now given that the opponent knows this strategy, it is obvious that his best choice is to choose a number between 1 and k-1.</i>

I think you made a false assumption.
If your solution is to
pick 1: 4/10 of the time
pick 2: 3/10 of the time
pick 3: 2/10 of the time
pick 4: 1/10 of the time

Then if I choose 2 all the time
I win $2 4/10 of the time (+0.8)
tie 3/10 of the time (0)
lose $2 2/10 of the time (-0.4)
win $1 1/10 of the time (+0.1)

with an expected profit of $0.50 per round.

You are getting close though...

WanFactory
Tuesday, June 21, 2005

ok, i'm assuming that 1 is the lower limit, in other words you can't pick 0?

if this is the case, i have developed a break-even strategy. alternate between 1, 3, and 5.

choose 1: 2/7 of the time
choose 3: 3/7 of the time
choose 5: 2/7 of the time.

overall, their best bet is to choose 4 repeatedly. so basically, they: lose 2 dollars, win 6 dollars, lose 4 dollars. break even baby! as you said, it can't be beaten! i am still working on a winning strategy tho, but no luck so far.

Reuben Moss
Monday, June 27, 2005

and if 0 is the lower limit (you definitely can't choose - numbers right?) you just do the same, except alternate between 0, 2, and 4.

Reuben Moss
Monday, June 27, 2005

Reuben, you are right, zero is not allowed.

You are right to go for a break-even strategy. However, if someone knows your strategy, they can beat it by picking 1 all the time.

Looks like you need more 2's in your random distribution...

WanFactory
Monday, June 27, 2005

*  Recent Topics

*  Fog Creek Home