It’s been a while since I posted anything here. In addition to me being lazy and busy, I did not encounter any nice puzzle. This puzzle, again given to me by Ramprasad, who got it from someone when he attended China Theory Week. This is one of those puzzles that you will curse yourself for eternity if you do not get it. The solution is so simple that if you can’t get it, you should die of shame!! Surprisingly, many Professors who attended CTW could not get it. Anyways, without further ado here it goes.
Problem : On a table you have a square made of 4 coins at the corner at distance 1. So, the square is of size 1×1. In a valid move, you can choose any two coin let’s call them mirror and jumper. Now, you move the jumper in a new position which is its mirror image with respect to mirror. That is, imagine that mirror is a centre of a circle and the jumper is on the periphery. You move the jumper to a diagonally opposite point on that circle. With any number of valid moves, can you form a square of size 2×2? If yes, how? If no, why not?
Solution : My first intuition told me that no matter how many moves you take, you can never make a square of size 2×2. But why? Initially, I went on different directions like, putting a bound on the distances between the coin. Well, the distances between the coin can grow in an unbounded manner. What about an Area? Can we put a bound on the area trapped inside the convex hull formed by these 4 coins? If we can show that area can not grow upto 4x the originial size, we are done. But well, you can not even put a bound on the area. I leave it as an exercise to show how distances and area can grow in an unbounded manner.
One point to note is that instead of a square, if it is triangle, the area will remain constant, always!!
Anyways, here is the solution for those who have given up or who just wants to verify whether their solution is correct. Note, that every valid move is reversible. That is if you make a move in one direction, the other direction is also a possibility. So, if you can scale a square of size 1×1 into a square of size 2×2, then you should also be able to shrink it into arbitrary small square. Say 1/2 x 1/2 or 1/1024 x 1/1024.
So, now we need to show that you can not shrink the square. If we show that distance between any two coins is always greater than 1 unit, we are done. And here is the most simple part!
Imagine a grid on the 2-d plane. Let the coins be at (0,0) (0,1) (1,0) (1,1) forming a square of size 1×1. Our grid cells are of size 1×1. Note, that no matter how many moves you make, the coins will always have integer co-ordinates ( basically stays on the grid ). Since, the shortest distance on the grid is 1 unit, no two coins can have distance shorter than 1 unit. And we are done!
— Saurabh Joshi