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
(In reply to computer solution
It sounds as if you're saying that even after only one shuffle, there has to be a repeated handshake from the initial position. However, this is not the case:
Note that diagonals do not count as handshakes; otherwise we'd have more than 12 handshakes per stage of the game and more than 36 for the set of 3 grids.
Posted by Charlie
on 2015-07-23 11:37:25