There is a frog jumping on a $ 2k \times 2k$ chessboard, composed of unit squares. The frog's jumps are $ \sqrt{1 + k^2}$ long and they carry the frog from the center of a square to the center of another square. Some $ m$ squares of the board are marked with an $ \times$, and all the squares into which the frog can jump from an $ \times$'d square (whether they carry an $ \times$ or not) are marked with an $ \circ$. There are $ n$ $ \circ$'d squares. Prove that $ n \ge m$.
Problem
Source: Baltic Way 2000 Problem 9
Tags: combinatorics unsolved, combinatorics
gwen01
17.02.2009 16:26
Label the unit squares by pairs of integers $ (a,b)$ with $ 1\le a,b\le2k$. Consider the $ \times$'d squares $ (a,b)$. If $ a$ is even and $ b\le k$, the squares $ (a-1,b+k)$ is $ \circ$'d. If $ a$ is odd and $ b\le k$, the squares $ (a+1,b+k)$ is $ \circ$'d. If $ a$ is even and $ b>k$, the squares $ (a-1,b-k)$ is $ \circ$'d. If $ a$ is odd and $ b>k$, the squares $ (a+1,b-k)$ is $ \circ$'d. Clearly, these $ \circ$'d squares are pairwise distinct. Hence the number of $ \circ$'d squares is at least $ m$.
Xell
18.02.2009 17:34
gwen01 : but the frog can jump from different x'd squares to the same o'd square !!
gwen01
19.02.2009 13:37
Xell wrote: gwen01 : but the frog can jump from different x'd squares to the same o'd square !! Sure, I am aware of that. That's why I correspond one x'd square with one o'd square (bijection).
Xell
23.02.2009 22:21
ok I see now
AnonymousBunny
30.07.2014 20:29
Note that moving $k$ units to one direction and 1 unit to its perpendicular direction produces a path of length $k^2+1.$ From x'd square, the frog can go to at least two other cells (either move $k$ units up, 1 unit right; $k$ units down, 1 unit right; $k$ units left, 1 unit up; or $k$ units right, 1 unit left) depending on its position (for example, it cannot move $k$ units left if it's in the leftmost column). Furthermore, the original x'd square gets uniquely determined by those two squares. So we have a bijection, giving $n \geq m.$ $\blacksquare$
chaotic_iak
31.07.2014 02:37
Wrong. A frog on the top-left corner can only move to one square that is mentioned by you (namely $k$ right, $1$ down).
AnonymousBunny
31.07.2014 05:12
Oops, I see. The argument still holds though... the original position of the frog is uniquely determined by the set of squares it can travel to.
chaotic_iak
31.07.2014 05:50
Sure, but what then? You still haven't established the bijection.
AnonymousBunny
31.07.2014 06:00
Yeah, that's why I called it a "horribly phrased solution". Well, the sets of squares the frog can move to from a x'd square are all mutually disjoint, so given a set of x'd squares $\{\mathcal{P}_1, \mathcal{P}_2, \cdots , \mathcal{P}_x\},$ the frog can find a set $\{\mathcal{Q}_1, \mathcal{Q}_2, \cdots , \mathcal{Q}_x\}$ such that the frog can move from $\mathcal{P}_i$ to $\mathcal{Q}_i$ for all $i.$ I'm not very sure how to explain this in words.