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

Home > Just Math
Nine trolls (Posted on 2015-07-23) Difficulty: 2 of 5
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

No Solution Yet Submitted by Ady TZIDON    
Rating: 4.0000 (1 votes)

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}};
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];

  Posted by Daniel on 2015-07-23 10:13:56
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information