Xi'an's Og

An game-theoretic Le Monde mathematical puzzle:

A two-person game consists in choosing an integer N and for each player to successively pick a number in {1,…,N} under the constraint that a player cannot pick a number next to a number this player has already picked. Is there a winning strategy for either player and for all values of N?

for which I simply coded a recursive optimal strategy function:

[sourcecode language=”r” gutter=”false”]
gain=function(mine,yours,none){
fine=none
if (length(mine)>0)
fine=none[apply(abs(outer(mine,none,"-")),
2,min)>1]
if (length(fine)>0){
rwrd=0
for (i in 1:length(fine))
rwrd=max(rwrd,1-gain(yours,c(mine,fine[i]),
none[none!=fine[i]]))
return(rwrd)}
return(0)}
[/sourcecode]

which returned a zero gain, hence no winning strategy for all values of N except 1.

[sourcecode language=”r” gutter=”false”]
> gain(NULL,NULL,1)
[1] 1
> gain(NULL,NULL,1:2)
[1] 0
> gain(NULL,NULL,1:3)
[1] 0
> gain(NULL,NULL,1:4)
[1] 0
[/sourcecode]

Meaning that the starting player is always the loser!

This entry was posted on May 8, 2015 at 12:15 am and is filed under Books, Kids, Statistics, University life with tags Le Monde, mathematical puzzle, recursive function. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.