Each of the points $G$ and $H$ lying from different sides of the plane of hexagon $ABCDEF$ is connected with all vertices of the hexagon. Is it possible to mark 18 segments thus formed by the numbers $1, 2, 3, \ldots, 18$ and arrange some real numbers at points $A, B, C, D, E, F, G, H$ so that each segment is marked with the difference of the numbers at its ends? Proposed by A. Golovanov
Problem
Source: Tuymaada 2002, day 1, problem 1. - Author : A. Golovanov.
Tags: modular arithmetic, combinatorics proposed, combinatorics
06.07.2009 23:09
Hint for anyone looking to solve this:
07.07.2009 05:10
Since the differences are all integers, then the fractional parts of the numbers must be equal. If we subtract the numbers by this fractional parts, the differences remain the same, and the numbers become integers. So now we assume that ther numbers assigned at the points are all integers. There are three cases to consider: (i) $ G$ and $ H$ are of different parity, wlog $ G$ is even and $ H$ is odd. Assume that $ k$ among $ A,B,C,D,E,F$ are even, the other $ 6-k$ are odd. So $ 6-k$ numbers on $ G$ are odd, $ k$ numbers on $ H$ are odd. Therefore 6 numbers on $ G$ and $ H$ are odd. Similarly, 6 numbers on $ G$ and $ H$ are even. Thus, 3 numbers (the differences) on $ ABCDEF$ are even and 3 numbers are odd. From $ A$, we go along the hexagon until back to $ A$. We change the parity three times, which means $ A$ has the different parity as itself, a contradiction. (ii) $ G$ and $ H$ are odd. Now $ 12-2k$ numbers on $ G$ and $ H$ are even and $ 2k$ are odd. We have $ 12-2k<9$ and $ 2k<9$ so $ k=2$ or $ k=4$ ($ k=3$ is impossible as in case (i)). Suppose $ k=2$. $ 12-2k=8$ difference values are even, so only one difference in $ A,B,C,D,E,F$ is even. So, if we start from $ A$ and go along the hexagon, we always change parity except one time. Assume wlog the $ A\equiv F\pmod2$. From $ A$ to $ F$ we always change parity. Clearly this is impossible. Suppose $ k=4$. Now only one difference in $ A,B,C,D,E,F$ is odd. Now we only change parity one time, this is clearly impossible. (iii) $ G$ and $ H$ are even. This is exactly the same as case (ii), just change $ k$ into $ 6-k$. So the task is impossible.