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
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 |
computer solution
