Someone and Anyone

“I walk slowly, like one who comes from so far away he doesn’t expect to arrive.”

Harry Vs Draco

with one comment

Harry Potter and Draco Malfoy are the frontrunners for the “Best Student of the Year” award at Hogwarts. Professor Dumbledore suggests that they play a certain game (invented by a great wizard) to determine the winner. Dumbledore describes the game to Harry and Draco as follows.

Consider a board as below, with two distinct non-zero integers m and n “thrown” onto it. At the beginning of the game, Dumbledore, as the impartial referee, will provide m and n. Then, there will be a toss to decide who gets to make the first move. The winner of the toss can either make the first move himself or invite his opponent to make the first move.

When his turn comes, each player has to introduce a new positive integer onto the board such that it is the difference between any two existing integers on the board.

For example:

First move: Player 1 would introduce k = |m – n|

Second move: Player 2 would introduce either x = |m – k| or y = |n – k|

Third move: (Assuming that Player 2 introduced x = |m – k| in the second move) Player 1 introduces either u = |m – x| or v = |n – x| or w = |k – x| or y = |n – k|

Fourth move: Player 2 introduces…

and so on…

The game goes on like this and concludes only when one of the players finds it impossible to introduce any more new numbers to the board; the other player thus wins.

Well, now, the stage is set. Dumbledore has provided m and n. Harry has won the toss!

Can you help Harry ensure that he wins the game? Who should make the first move and why?


Written by Anyone

May 29, 2008 at 10:12 pm

Posted in Mathematics

Tagged with , , , ,

One Response

Subscribe to comments with RSS.

  1. {m,n} (moves) number of moves in game

    {2,1} () 0
    {3,1} (2) 1
    {3,2} (1) 1
    {4,1} (3,2) 2
    {4,2} () 0
    {4,3} (1,2) 2
    {5,1} (4,3,2) 3
    {5,2} (3,1,4) 3
    {5,3} (2,1,4) 3
    {5,4} (1,3,2) 3
    {6,1} (5,4,3,2) 4
    {6,2} (4) 1
    {6,3} () 0
    {6,4} (2) 1
    {6,5} (1,4,3,2) 4

    moves in game: max(m,n)/gcd(m,n) – 2

    If the number of moves is even, make the other player go first.


    August 29, 2008 at 3:26 am

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: