# There are 109 soldiers in a camp. Every night three of them go on watch patrol. Prove that it can be arranged so that after a while, every pair of soldiers has shared watch exactly three times.

There are 109 soldiers in a camp. Every night three of them go on watch patrol. Prove that it can be arranged so that after a while, every pair of soldiers has shared watch exactly three times.
You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Kinowagenqe
Suppose $n=2m+1$ and consider the triples $\left(i,i+j,i+2j\right)$ where $i=1,2,3,\dots ,\left(2m+1\right)$ and $j=1,2,3,\dots ,m.$. We can construct a $\left(2m+1\right)×m$ array of triples with $\left(i,i+j,i+2j\right)$ in the $i$th row and $j$th column. We work modulo $2m+1.$.
For example here's a solution for $n=9.$
$\begin{array}{cccc}\left(1,2,3\right)& \left(1,3,5\right)& \left(1,4,7\right)& \left(1,5,9\right)\\ \left(2,3,4\right)& \left(2,4,6\right)& \left(2,5,8\right)& \left(2,6,1\right)\\ \left(3,4,5\right)& \left(3,5,7\right)& \left(3,6,9\right)& \left(3,7,2\right)\\ \left(4,5,6\right)& \left(4,6,8\right)& \left(4,7,1\right)& \left(4,8,3\right)\\ \left(5,6,7\right)& \left(5,7,9\right)& \left(5,8,2\right)& \left(5,9,4\right)\\ \left(6,7,8\right)& \left(6,8,1\right)& \left(6,9,3\right)& \left(6,1,5\right)\\ \left(7,8,9\right)& \left(7,9,2\right)& \left(7,1,4\right)& \left(7,2,6\right)\\ \left(8,9,1\right)& \left(8,1,3\right)& \left(8,2,5\right)& \left(8,3,7\right)\\ \left(9,1,2\right)& \left(9,2,4\right)& \left(9,3,6\right)& \left(9,4,8\right)\end{array}$
The number of triples = $m\left(2m+1\right)=\left(\genfrac{}{}{0}{}{2m+1}{m}\right)=$ the number of distinct pairs of integers in $S=\left\{1,2,3,\dots ,2m+1\right\}$ and all triples are unique, where the order of the elements is taken into account. (For suppose $\left(x,y,z\right)$ is in our array, then $x=i,y=i+j$ and $z=i+2j$ for some $i,j$ and thus if $x this triple is in the $x$th row and $\left(y-x\right)$th column, and if $x>y$ it is in the $x$th row and $\left(y-x+2m+1\right)$th column. So its position is uniquely determined by its elements.
Moreover, if $\left(x,y,z\right)=\left(i,i+j,i+2j\right)$ is in the array then none of $\left(x,z,y\right),\left(z,y,x\right)$ and $\left(y,x,z\right)$ can be in the array, for if one of the positions of the elements is fixed the latter three triples cannot obey the construction rule, that its elements increase by $j,$ since we know that $x$, $y$ and $z$ increase by $j.$
Now consider a pair of integers $\left(a,b\right),$, which appears in a given triple, $\left(a,b,c\right)$. There cannot exist another triple in the array $\left(a,b,d\right),$, say, with $c\ne d$ since $c$ is uniquely determined by $a$ and $b.$
The pair $\left(a,b\right)$ cannot appear in more than three triples, in whatever order (we've already noted that we cannot have both $\left(a,b,c\right)$ and $\left(b,a,c\right)$ hence the three and not six), since the remaining element is uniquely determined by $a$ and $b.$ However, it cannot appear in less than three triples since the number of triples equals the number of pairs of distinct integers in $S,$ so this would mean that another pair must appear in more than three triples, a contradiction.
Thus we have a solution for any odd $n\ge 3.$.
So a solution for $n=11$ is:
$\begin{array}{ccccc}\left(1,2,3\right)& \left(1,3,5\right)& \left(1,4,7\right)& \left(1,5,9\right)& \left(1,6,11\right)\\ \left(2,3,4\right)& \left(2,4,6\right)& \left(2,5,8\right)& \left(2,6,10\right)& \left(2,7,1\right)\\ \left(3,4,5\right)& \left(3,5,7\right)& \left(3,6,9\right)& \left(3,7,11\right)& \left(3,8,2\right)\\ \left(4,5,6\right)& \left(4,6,8\right)& \left(4,7,10\right)& \left(4,8,1\right)& \left(4,9,3\right)\\ \left(5,6,7\right)& \left(5,7,9\right)& \left(5,8,11\right)& \left(5,9,2\right)& \left(5,10,4\right)\\ \left(6,7,8\right)& \left(6,8,10\right)& \left(6,9,1\right)& \left(6,10,3\right)& \left(6,11,5\right)\\ \left(7,8,9\right)& \left(7,9,11\right)& \left(7,10,2\right)& \left(7,11,4\right)& \left(7,1,6\right)\\ \left(8,9,10\right)& \left(8,10,1\right)& \left(8,11,3\right)& \left(8,1,5\right)& \left(8,2,7\right)\\ \left(9,10,11\right)& \left(9,11,2\right)& \left(9,1,4\right)& \left(9,2,6\right)& \left(9,3,8\right)\\ \left(10,11,1\right)& \left(10,1,3\right)& \left(10,2,5\right)& \left(10,3,7\right)& \left(10,4,9\right)\\ \left(11,1,2\right)& \left(11,2,4\right)& \left(11,3,6\right)& \left(11,4,8\right)& \left(11,5,10\right)\end{array}$