Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There is two-dimensional grid with integer coordinates. We can do some moves by coins. If the coin is in point $(x,y)$ and point $(x+1,y)$ and $(x,y+1)$ are free from coins, we can remove coin from $(x,y)$ and put two coins at $(x,y+1)$ and $(x+1,y)$. In the beginning we have only one coin at the origin. The question is "Can we make free from coins square with coordinates of the lower left corner $(0,0)$ and upper right corner $(2,2)$?"

share|improve this question
add comment

2 Answers

up vote 5 down vote accepted

Assign point $(x,y)$ the weight $2^{-(x+y)}$. Then the weight of $(x,y)$ equals the weight of $(x+1,y)$ plus the weight of $(x,y+1)$, so the total weight of the occupied points never changes. At the beginning, with a single coin at the origin, the total weight is just $1$. The points outside that square have total weight $15/16$, which is less than $1$, so it's impossible.

share|improve this answer
add comment

This is a cute little problem.

The insight here is to look for an invariant that is preserved by the allowed moves. In this case, the right way to approach it is to think of the original coin at the origin as having a fixed mass of 1. The rule for replacing the coin with two others can be thought of as breaking the coin in half, to be replaced by two coins of half the mass. Since we are starting with one coin of mass one at the origin, our rules tell us that a coin on a given square will have a certain prescribed mass, regardless of the sequence of moves that got it there. In particular, a square that is $n$ steps away from the origin will support a mass of $2^{-n}$.

The way to proceed should now be clear - we determine the (finite) mass of the entire grid. Then, we can check and see if a region can be cleared by computing the mass of the complement - if this is less than our original mass of one, a region can't be cleared.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.