$m$ and $n$ are two nonnegative integers. In the Philosopher's Chess, The chessboard is an infinite grid of identical regular hexagons and a new piece named the Donkey moves on it as follows: Starting from one of the hexagons, the Donkey moves $m$ cells in one of the $6$ directions, then it turns $60$ degrees clockwise and after that moves $n$ cells in this new direction until it reaches it's final cell. At most how many cells are in the Philosopher's chessboard such that one cannot go from anyone of them to the other with a finite number of movements of the Donkey? Proposed by Shayan Dashmiz
Problem
Source: Iran TST 2013-First exam-2nd day-P4
Tags: analytic geometry, modular arithmetic, geometry, parallelogram, vector, number theory, combinatorics proposed
22.04.2013 11:59
Consider the center of each hexagon, we have infinitely equilateral triangle. After that, with some of number theory, we see that the maximum is $(m;n)^2-1$
23.04.2013 21:00
Nevergiveupbtw wrote: Consider the center of each hexagon, we have infinitely equilateral triangle. After that, with some of number theory, we see that the maximum is $(m;n)^2-1$ can you write your sol? because the answer is $m^{2}+n^{2}+mn$
16.05.2013 00:37
Set up a coordinate system in which the $y$ axis makes a $60^{\circ}$ angle with the $x$ axis, and let $g = \gcd(m, n)$ so that $m = gm'$ and $n = gn'$ where $\gcd(m', n') = 1$. Now given two hexagons at $(x_1, y_1), (x_2, y_2)$ we'll establish necessary and sufficient criteria that the donkey can move from $(x_1, y_1)$ to $(x_2, y_2)$. From the hexagon at $(x, y)$ we can move to one of six possible positions $(x', y')$: $(x \pm (m + n), y \mp n)$, $(x \pm n, y \pm m)$, or $(x \pm m, y \mp (m + n))$. Notice that $g | x' - x$ and $g | y' - y$, and also that \[m'\frac{(x' - x)}{g} - n'\frac{(y' - y)}{g} \equiv 0 \pmod{m'^2 + m'n' + n'^2}\] regardless of the choice of move. On the other hand, this is sufficient to guarantee we can move from $(x, y)$ to any $(x', y')$; if we make $a, b, c$ moves of each type, respectively, we want in general to be able to solve \[{ \{\begin{array}{lr} x' - x = a(m + n) + bn + cm \\ y' - y = - an + bm - c(m + n) \\ \end{array}}\] for $a, b, c$ in the integers. We can arbitrarily set $c = 0$ and after dividing through by $g$ note that by Cramer's Rule and the fact that \[(m' + n')(m) - n'(-n') = m'^2 + m'n' + n'^2 | m'\frac{(x' - x)}{g} - n'\frac{(y' - y)}{g}\] the system has an integer solution. Then the maximum number of squares is $m^2 + mn + n^2$; if we had any more, by PHP some pair $(x_1, y_1), (x_2, y_2)$ would satisfy $g | x_1 - x_2$, $g | y_1 - y_2$, $m'^2 + m'n' + n'^2 | m'(x_1 - x_2)/g - n'(y_1 - y_2)/g$ so we could move from one to the other. This is attainable by choosing a set of points where for each pair $(p, q)$ of proper residues modulo $g$, we include $m'^2 + m'n' + n'^2$ points $(x_i, y_i)$ where $x_i \equiv p \pmod{g}$, $y_i \equiv q \pmod{g}$, and \[m'\frac{(x_i - p)}{g} - n'\frac{(y_i - q)}{g}\] takes on all $m'^2 + m'n' + n'^2$ possible values modulo $m'^2 + m'n' + n'^2$ (which is possible by Bezout and the fact that $\gcd(m', n') = 1$). A geometric interpretation also seems possible. If we consider (as one of the previous posts mentions) the infinite equilateral lattice of points reachable from a single starting point, what we're trying to count is effectively the number of hexagons "interior" to the figure formed by two equilateral triangles (since corresponding hexagons in similar figures on the lattice can be reached by application of the allowable moves). Setting up a coordinate system again (here's where it gets very hand-wavy), we want the "area" of the parallelogram formed by the vectors $(n, m)$ and $(m + n, - n)$; this is simply \[ |\begin{array}{cc} n & m\\ m + n & -n\end{array}| = m^2 + mn + n^2\] (I'm not quite sure why this works, maybe someone can figure it out.)