Le Monde puzzle [#910]
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:
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)}
which returned a zero gain, hence no winning strategy for all values of N except 1.
> 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
Meaning that the starting player is always the loser!
Leave a Reply