Le Monde puzzle [#835]

The current puzzle is apparently suffering from combinatoric complexity :

N persons (with 20≤N≤23) are sitting around a round table and everyone has a green or red token. Both colours are represented. First, each player with a red token take the token of the player immediately to her or his left. Second, each player with at least one green token gives it to the player next to the player immediately to her or his left. By that time, everyone has a token in front of her or him. What are the possible values of N?

I first tried a brute force approach where I fill a table at random and apply the rules:

sole=FALSE
while (!sole){
N=sample(20:23,1)
arthur=merlin=cbind(sample(1:2,N,rep=TRUE),rep(0,N),rep(0,N))
#Move 1
merlin[arthur[,1]==1,2]=arthur[(1:N)[arthur[,1]==1]%%N+1,1]
merlin[(1:N)[arthur[,1]==1]%%N+1,1]=0
#Move 2
mordred=merlin
green=(1:N)[apply(merlin,1,max)==2]
mordred[(green+1)%%N+1,3]=merlin[green,1]
mordred[green,1]=0
#Solution
sole=(min(apply(mordred,1,max))>0)
}
mordred

After a rather long while that had me fear the loop had became “infinite”, this R code produced a (non-trivial) result:

> arthur[,1]
 [1] 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2

which shows that for N=21 and two green (2) tokens following a red (1) token, the procedure returns a configuration where all players have one and only one token. (Of course, the R code does not exclude the extreme case when all tokens are from a single colour.) From there, the generic solution follows: N must be a multiple of 3 and the tokens must be set as red-green-green-red-green-green-…

7 Responses to “Le Monde puzzle [#835]”

  1. tried to formulate the problem as an Integer Programming model, which helps in ruling out the trivial solutions (all red or all green). It solved in Excel in seconds.

  2. is all red a possible solution,too? so N can be any number?

    • Thanks. As I wrote in the previous reply, the R code does not exclude all red/all green solutions (which would be easily avoided by adding a green and a red in the sample line). So indeed you may get all red/all green solutions with this code. For all N’s.

  3. Sort of takes the fun out of this one to calculate the layout. It only takes a few logic sentences to work it out, I think, since it quickly becomes clear that there has to be some sort of RGG or GRR pattern to avoid having some players end up with zero tokens :-)

    • Carl, I think most of my solutions take the fun out. I started this series to give my students R programming exercises and from time to time R exams, which is why I skip some problems where programming is out of the game.

  4. I copied the code, but the output was 21 green tokens.

    • Yes, this is a possible outcome: as I wrote in the post, my R code does not exclude the all-green and all-red draws. If you rerun the code, you may find the red-green-green-red-green-green-…solution.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 644 other followers