• LOGIN
  • No products in the cart.

Profile Photo

Diagonal Moves (TOMATO Subjective 181)

Suppose that one moves along the points (m, n ) in the plane where m and n are integers in such a way that each move is a diagonal step, that is, consists of one unit to the right or left followed by one unit either up or down.

(a) Which point (p, q) can be reached from the origin.

(b) What is the minimum number of moves needed to reach such a point (p, q)?

Discussion: 

For each horizontal movement (right or left) there is one vertical movement (up or down). Suppose there are R right moves, L left moves. Also there be U upward move and D downward move. Since number of horizontal movement equals number of vertical movements hence we have

R+L = U+D = k (say)

The final coordinate reached is (R – L , U – D) (as each right move counts as +1 and left move counts as -1, and similarly for vertical movements),

L = k -R

D = k -U

Hence the final coordinate is (2R – k, 2U – k)

Therefore both the coordinates are of same parity (that is either both are even or both are odd).

So we have shown that the final point that can be reached has both x and y coordinate of the same parity. Now we show the converse. That is all the points whose x and y coordinates are of same parity can be reached.

 

Read More…

No comments, be the first one to comment !

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    Login

    Register

    GOOGLECreate an Account
    X