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!
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.