Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Feb 9, 2010

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!

2 comments:

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

    1) 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 !

    ReplyDelete
  2. \m/
    Creativity at its best! Couldn't reach even close. Nice solution. Thanx.

    ReplyDelete