### Checkers Problem

**Source:**Nikhil Garg (Sophomore, IITD) mailed them to me.

**Problem 1:**

A checker starts at point (1,1). You can move checker using following moves :

1) if it is at (x,y) take it to (2x ,y ) or (x,2y)

2) if it is at (x,y) & x>y take it to (x-y,y)

3) if it is at (x,y) & x<y take it to (x,y-x)

Characterise all lattice points which can be reached.

**Problem 2:**

You have a checker at (0,0) , (0,1) , (1,0), (2,0), (0,2), (1,1) each. You can make a move as follows:

if(x,y) is filled & (x+1,y) and (x,y+1) both are empty, remove checker from (x,y) & put one at each of (x+1,y) and (x,y+1)

Prove that under this move , you can not remove checker from all the six initial points.

**Solution:**

Update (02/03/10): Solution posted by Nikhil Garg in comments!

Since none has posted the solutions , I am posting them :

ReplyDelete1) Note that after steps 2 or 3 , gcd(x,y) does not change.

2) After step 1 , gcd either does not change or if changes , get doubled.

So this is the invariant on gcd. Initial gcd is 1. So finally it can either be 1 or some power of 2.

It is also easy to prove ( possibly induction ) that all such points can infact be reached.

2) This is indeed a tough one.

Consider a weight function w(x,y) associated with every lattice point.

w(x,y)= 1/( 2^(x+y) )

So this ensures that every move leaves total weight of board unchanged.

Now total weight of all the board ( all first quadrant ) is 4. & weight of given 6 squares is more then 2. So these 6 checkers are too heavy for the rest of board !

\m/

ReplyDeleteCreativity at its best! Couldn't reach even close. Nice solution. Thanx.