iconEuler Examples

A Taking Game

by R. Grothmann

I recently found the following game in a beautiful book by Peter
Winkler (Mathematische Rätsel für Liebhaber). The game starts with a
row of coins of various values. The players in turn can take a coin
from either end of the row. The problem is to show that the first
player cannot lose if the game starts with an even number of coins. I
will present the solution at the end of the notebook.

The following is just a programming lesson, and has nothing to do
with numerical math or symbolic solutions. We will compute the
optimal strategy for this game.

So we start by defining a simple recursive function for the optimal
value a player can achieve. The vector x contains the values of the
coins.
>function f(x) ...
n=cols(x);
if n>1 then
 return max(x[1]-f(x[2:n]),x[n]-f(x[1:n-1]))
else
 return x[1]
endif
endfunction
It should not be too difficult to see, why this works. Let us
test some examples, where the optimal strategy is clear. E.g.,
if the coins are increasing from the left to right, it is obviously(?)
best to take the coins at the large end.

E.g., the win for the first player is n (1 at each take), if the
coins are 1 to 2n.
>f(1:10)
5
In the next example, we have to take ones, until the second player
is forced to uncover the 10. So the win is 10-1=9.
>f([1,10,1,1,1,1,1,1])
9
If we want to know the optimal move, we need to return it too.
So I change the code a bit.
>function fi(x) ...
n=cols(x);
if n>1 then
 e=extrema([x[1]-(fi(x[2:n])),x[n]-(fi(x[1:n-1]))]);
 return {e[3],e[4]}
else
 return {x[1],1}
endif
endfunction
>side=["left","right"];
1 means left and, and 2 means right end.
>{a,i}=fi(1:10); a, side[i],
5
right
For a challenge, let us simulate an optimal game.
>function simulate (x) ...
n=cols(x);
if mod(n,2)==0 then "A takes:" else "B takes:" endif;
if n==1 then x[1], return x[1]; endif
{a,i}=fi(x);
if i==1 then x[1]|" from the left", simulate(x[2:n]);
else x[n]|" from the right", simulate(x[1:n-1]);
endif
return a
endfunction
>v=simulate([1,10,20,30,10,1]); "Result:", v,
A takes:
1 from the right
B takes:
1 from the left
A takes:
10 from the left
B takes:
20 from the left
A takes:
30 from the left
B takes:
10
Result:
10
>simulate(1:5);
B takes:
5 from the right
A takes:
4 from the right
B takes:
3 from the right
A takes:
2 from the right
B takes:
1
The recursion in the example above works for a small number n of
coins. However, it generates 2^n function calls.

To avoid this in a recursive algorithm, we can add some memory for
function results. In fact, there are only n^2 possible coin positions
during the game.

So we add a matrix to denote the optimal value for the position
x[i],...,x[j] in A[i,j] and the optimal move in I[i,j]. We set up the
matrices once, and use the fact that Euler passes matrices by
reference. Assigning to a submatrix will in fact change the matrix.
>function fifastrek (x,i,j,I,A) ...
if I[i,j] then return A[i,j]; endif;
if i==j then A[i,j]=x[i]; I[i,j]=i; return x[i], endif;
a1=x[i]-fifastrek(x,i+1,j,I,A); a2=x[j]-fifastrek(x,i,j-1,I,A);
if a1>a2 then I[i,j]=i; A[i,j]=a1; return a1;
else I[i,j]=j; A[i,j]=a2; return a2;
endif;
endfunction
Instead of global matrices, we write a main function.
>function fifast (x) ...
n=cols(x); I=zeros(n,n); A=zeros(n,n);
return fifastrek(x,1,n,I,A);
endfunction
Now we can solve 100 coins, which would be unthinkable with the
simple recursion above.
>fifast(1:100)
50

Solution of the Problem

How about the proof that the first player can always win at an even
number of coins?

This is very simple with a trick. Number the coins from left to right.
If you think about it, you see that the starting player can either
take all the even coins, or all the odd coins. So he simply chooses,
which is better.
>function g(x) ...
n=cols(x);
return sum(x[2:2:n])-sum(x[1:2:n])
endfunction
>g([1,10,20,30,10,1])
10
However, this is not the optimal strategy! In the following example
the odd coins 4+6 yield a win of 1. But it is better to take the
7 first, and then either the 4 for a win of 3, or the 6 for a
win of 7.
>h=[4,2,6,7]; g(h), fifast(h),
-1
3

Examples Homepage