All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Nine trolls (Posted on 2015-07-23)
Nine trolls are placed in the cells of a three-by-three square.
The trolls in neighboring cells shake hands with each other.
Later they re-arrange themselves in the square and the neighbors greet each other once more.
Then they repeat it again for the 3rd time.

Prove (or provide a counterexample) that there is at least one pair of trolls who didnâ€™t greet each other.

Based on a problem in Russian "Kvantik",2012

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer solution | Comment 2 of 9 |
below Mathematica code runs through all possible ways for the first shuffle to happen, then looks to see if the set of handshakes for the shuffled arrangement is disjoint from the initial set of handshakes.  It does not find any permutations which result in a disjoint set of handshakes.  Thus from the first set of handshakes to the second, there will be at least 1 repeated handshake.  Since, as Charlie pointed out, if any handshake is repeated then that means at least one of the possible handshakes has to be missed.

Thus the assertion is true.

HandshakeList[p_] := Module[{p1, p2, p3, p4, p5, p6, p7, p8, p9, h},
p1 = p[[1]];
p2 = p[[2]];
p3 = p[[3]];
p4 = p[[4]];
p5 = p[[5]];
p6 = p[[6]];
p7 = p[[7]];
p8 = p[[8]];
p9 = p[[9]];
h = {{1, 2}, {1, 4}, {2, 3}, {2, 5}, {3, 6},
{4, 5}, {4, 7}, {5, 6}, {5, 8}, {6, 9},
{7, 8}, {8, 9}};
Return[h];
];
trolls = Table[i, {i, 1, 9}];
hbase = HandshakeList[trolls];
perms = Permutations[trolls];
plng = Length[perms];
dset = {};
For[pi = 1, pi <= plng, ++pi,
pr = perms[[pi]];
h = HandshakeList[pr];
If[Intersection[hbase, h] == {},
AppendTo[dset, pr];
];
];
Length[dset]

 Posted by Daniel on 2015-07-23 10:13:56

 Search: Search body:
Forums (0)