Dragon moving in a board

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Dragon moving in a board

G H J

Reveal topic tags

analytic geometry

combinatorics proposed

L

G H BBookmark kLocked kLocked NReply

Source: Iberoamerican Olympiad 2007, problem 4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

388 posts

Jutaro

#1 h Sep 14, 2007, 2:22 AM • 4 Y

Y by Adventure10, Mango247, Mango247, Mango247

In a $19\times 19$ board, a piece called dragon moves as follows: It travels by four squares (either horizontally or vertically) and then it moves one square more in a direction perpendicular to its previous direction. It is known that, moving so, a dragon can reach every square of the board.

The draconian distance between two squares is defined as the least number of moves a dragon needs to move from one square to the other.

Let $C$ be a corner square, and $V$ the square neighbor of $C$ that has only a point in common with $C$ . Show that there exists a square $X$ of the board, such that the draconian distance between $C$ and $X$ is greater than the draconian distance between $C$ and $V$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

253 posts

#2 h Sep 15, 2007, 12:33 PM • 2 Y

Y by Adventure10, Mango247

Consider a set of coordinates so that corner $C$ is $(0,0)$ , the opposite corner of the $19\times19$ grid is $(18,18)$ , $V$ is obviously $(1,1)$ and wlog because of symmetry the first coordinate is horizontal and the second coordinate is vertical. We will call "horizontal" a move that changes the horizontal coordinate by 4 and the vertical coordinate by 1; "vertical" moves are defined reciprocally.

Since from $(0,0)$ to $(1,1)$ , the horizontal coordinate changes by 1, the number of vertical moves must be odd. Likewise, the number of horizontal moves must be odd. Assume that the dragon may move from $(0,0)$ to $(1,1)$ with less than 8 moves. Then it must be able to do it with 6 or less, i.e., at most 3 moves in each direction. So, the net change introduced by horizontal moves in the vertical coordinate is at most 3 (at most 3 times 1), while the change introduced by vertical moves in the vertical direction is at least 4 (odd number of times 4). Since the net change in the vertical coordinate is $+1$ , we would necessarily need two "upward" vertical moves, one "downward" vertical move and three horizontal moves so that in the three of them the change in the vertical coordinate is downward. Similarly, we would need two "rightbound" horizontal moves, one "leftbound" horizontal move and three vertical moves so that in the three of them the change in the horizontal coordinate is to the left (assuming 0 is the leftmost column, 18 the rightmost column). But this is impossible, since the first move must be horizontal righbound and up, or vertical upward and rightbound. So at least 8 moves are necessary. With 8 moves it is possible: $(0,0)\rightarrow(4,1)\rightarrow(8,0)\rightarrow(7,4)\rightarrow(6,8)\rightarrow(2,7)\rightarrow(1,3)\rightarrow(5,2)\rightarrow(1,1)$ .

So we need to find a square such that the dragon takes at least 9 moves to get to it, and one such square is $(18,17)$ . Since the change in vertical coordinates is odd, an odd number of horizontal moves is needed; similarly, an even number of vertical moves is needed. So if it is possible to get from $(0,0)$ to $(18,17)$ in 8 moves or less, it is possible to do it in at most 7 moves. If the change in both coordinates is added in absolute value, the net change in the sum of coordinates is at most 5, so 7 moves may bring a sum of changes in both coordinates of at most 35. But the net change in coordinates from $(0,0)$ to $(18,17)$ is exactly 35, so all changes in the horizontal direction (be it through horizontal or vertical moves) must be of the same sign, and likewise in the vertical direction. Or, if we have exactly $h$ horizontal moves and $v$ vertical moves, it must hold that $18 = 4h+v$ and $17 = h+4v$ , yielding $1 = 3(h-v)$ , absurd. So at least 9 moves are needed to get from $(0,0)$ to $(18,17)$ . Such a sequence of 9 moves is $(0,0)\rightarrow(4,1)\rightarrow(8,0)\rightarrow(9,4)\rightarrow(10,8)\rightarrow(11,12)\rightarrow(12,16)\rightarrow(13,12)\rightarrow(14,16)\rightarrow(18,17)$ .

I just realized that I have actually gone beyond the scope of the problem, since it was enough to show that it is not possible to get from $(0,0)$ to $(18,17)$ in less than 9 moves (I have shown that it is actually possible to do it in exactly 9 moves) and that it is possible to get from $(0,0)$ to $(1,1)$ in no more than 8 moves (I have shown that 8 is the minimum number of moves required)...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Umut Varolgunes

279 posts

Umut Varolgunes

#3 h Sep 15, 2007, 12:37 PM • 2 Y

Y by Adventure10, Mango247

same solution and i like this question. good number 4 i think.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

253 posts

#4 h Sep 15, 2007, 12:42 PM • 2 Y

Y by Adventure10, Mango247

Yep, numbers 1 and 4 problems in Ibero are typically problems where no "heavy equipment" is necessary at all, but if you fail to see the "essence" of the problem (in this case I would say parity is this "essence"), you bang your head against the wall to no avail...

Overall very simple (to IMO standards) problems, but good fun nonetheless

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a