It's almost nighttime and some children are trying to light up their backyard. They have $n$ torches ($n \in \mathbb{N}$) and want to distribute themselves on the $n \text{ } \text{x} \text{ }n$-Meter backyard in such a way, that no two torches illuminate each other. Each torch sends light in 8 different directions, as in the following picture:
There are horizontal beams (marked in red), vertical beams (marked in green) and diagonal beams (marked in yellow).
We suppose that $n \geq 5$ and that $n$ is not divisible by $2$ nor $3$. Prove that the following positioning of $n$ children with torches $T_0, T_1, ..., T_{n-1}$ works, i.e no two torches light the same position in the backyard:
For $0 \leq i \leq n-1$ we position the torch $T_i$ on the field ($i, 2i \text{ } \text{mod } n).$
Here, we use the ($x$-coordinate, $y$-coordinate) coordinate system, where $x$ describes the horizontal position, and $y$ the vertical. For example: The three torches in the picture are placed on the fields $(3, 1), (2, n-3)$ and $(n-2, n-2).$
My idea was to prove by contradiction and break up each case on how the torches light up their path (horizontally, vertically and diagonally), but I can't see what follows. Can someone offer their thoughts or point me in the right direction?
from Hot Weekly Questions - Mathematics Stack Exchange
Post a Comment