We have a $ (n+2)\times n $ rectangle and we’ve divided it into $ n(n+2) \ \ 1\times1 $ squares. $ n(n+2) $ soldiers are standing on the intersection points ($ n+2 $ rows and $ n $ columns). The commander shouts and each soldier stands on its own location or gaits one step to north, west, east or south so that he stands on an adjacent intersection point. After the shout, we see that the soldiers are standing on the intersection points of a $ n\times(n+2) $ rectangle ($ n $ rows and $ n+2 $ columns) such that the first and last row are deleted and 2 columns are added to the right and left (To the left $1$ and $1$ to the right). Prove that $ n $ is even.
Problem
Source:
Tags: geometry, rectangle, induction, combinatorics proposed, combinatorics
jgnr
20.09.2010 18:34
[edited] It's difficult to explain this without diagrams but I'll try.
We prove by induction that the task cannot be done for odd $n$. The base case $n=1$ is obvious. Suppose our claim is true for $n=2k-1$. For the sake of contradiction, assume that the task can be done for $n=2k+1$. The soldiers in the outer columns must move one step inside, and the soldiers in the outer rows must move one step outside. All other soldiers in the inner $n\times(n-2)$ rectangle must move so that they fill in the new $(n-2)\times n$ rectangle, which is impossible according to the induction hypothesis. Therefore our claim is true, and hence $n$ is even.
kevinatcausa
20.09.2010 21:03
Soldiers are allowed to stay put, meaning that the color of their square may or may not change.
jgnr
21.09.2010 12:02
Sorry. I have edited my solution, is it okay now?
mahanmath
21.09.2010 12:15
Johan Gunardi wrote: Sorry. I have edited my solution, is it okay now? Yes !