Scaling a Square

Source: Saurabh Joshi, IIT Kanpur

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?

Update (November 4, 2011)
Solution: Posted by Siddhant Agarwal (EE IITB Alumnus, CMI Grad student) and Rudradev Basak (IITD CSE Senior Undergraduate) in comments!


Comments

  1. sid8:25 PM, November 03, 2011

    nice problem :)

    We observe that the parity of the L1 distance between any two coins is an invariant. In 1×1, for any coin, the L1 distance to its neighbors is odd. While in 2×2 every L1 distance between coins is even. Hence not possible

    ReplyDelete
  2. Rudradev Basak11:57 PM, November 03, 2011

    No.
    If I can go from a 1x1 square to a 2x2 square, then by applying reverse operations, I can also go from a 2x2 square to a 1x1 square.
    By applying scaling this means we can also go from a 1x1 square to a 0.5x0.5 square. But this is impossible since if initially all coins are on lattice points, then they remain on lattice points forever. So this leads to a contradiction.

    ReplyDelete
  3. sid3:12 PM, November 04, 2011

    brilliant argument!

    ReplyDelete
  4. Pratik Poddar5:28 PM, November 04, 2011

    Correct solutions by both sid and Rudradev Basak. Thanks. Saurabh Joshi (whose blog this problem is taken from) gave Rudra's solution and I could also think of that only. Sid's solution seems fresh :)

    ReplyDelete
  5. Pratik Poddar9:35 AM, November 05, 2011

    On second thoughts, Rudradev's solution (i.e. Saurabh's solution) is more general. It even works if I am asked to make a 3x3 square. While parity argument is just for even x even squares.

    ReplyDelete
  6. H2:02 AM, April 19, 2013

    So this also extends to any r by r initial square, r \in R? Then there must a plain geometry proof other than Rudradev's?

    ReplyDelete

Post a Comment

Popular posts from this blog

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible? 
Read more

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.
Read more

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially)
Read more