Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Interesting problem from a 2000 St. Petersburg school olympiad.

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.

I think I'm missing the key insight here.

share|improve this question
3  
Perhaps the idea of a Steiner Triple System is a place to start: mathworld.wolfram.com/SteinerTripleSystem.html and en.wikipedia.org/wiki/Steiner_system –  Joseph Malkevitch Dec 31 '10 at 15:25
2  
It will take a little over 16 years. Surely by then some of the soldiers will have left the service, so I would say it is not possible. –  Ross Millikan Dec 31 '10 at 21:13
    
As Joseph said, a Steiner Triple system exists (as $109 = 1 \mod 6$, proved by Kirkman). Taking 3 copies of that should solve this, I believe. Or is there a condition that no patrol can repeat? –  Aryabhata Dec 31 '10 at 23:35
    
You sure this is a school olympiad question. –  Uma kant May 11 '13 at 3:05
1  
@Uma: yes. In Russia. –  Weltschmerz May 27 '13 at 16:38
add comment

1 Answer 1

up vote 6 down vote accepted

I believe the following does the trick and that the $109$ is really a red herring, and that the problem has a solution for each odd $n \ge 3.$

Suppose $n=2m+1$ and consider the triples $(i,i+j,i+2j)$ where $i=1,2,3,\ldots,(2m+1)$ and $j=1,2,3,\ldots, m.$ We can construct a $(2m+1) \times m $ array of triples with $(i,i+j,i+2j)$ 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} (1,2,3) & (1,3,5) & (1,4,7) & (1,5,9) \\ (2,3,4) & (2,4,6) & (2,5,8) & (2,6,1) \\ (3,4,5) & (3,5,7) & (3,6,9) & (3,7,2) \\ (4,5,6) & (4,6,8) & (4,7,1) & (4,8,3) \\ (5,6,7) & (5,7,9) & (5,8,2) & (5,9,4) \\ (6,7,8) & (6,8,1) & (6,9,3) & (6,1,5) \\ (7,8,9) & (7,9,2) & (7,1,4) & (7,2,6) \\ (8,9,1) & (8,1,3) & (8,2,5) & (8,3,7) \\ (9,1,2) & (9,2,4) & (9,3,6) & (9,4,8) \end{array}$$

The number of triples = $m(2m+1)= { 2m+1 \choose m } = $ the number of distinct pairs of integers in $S= \{ 1,2,3,\ldots,2m+1 \} $ and all triples are unique, where the order of the elements is taken into account. (For suppose $(x,y,z)$ is in our array, then $x=i,y=i+j$ and $z=i+2j$ for some $i,j$ and thus if $x<y$ this triple is in the $x$th row and $(y-x)$th column, and if $x>y$ it is in the $x$th row and $(y-x + 2m+1)$th column. So its position is uniquely determined by its elements.

Moreover, if $(x,y,z)=(i,i+j,i+2j)$ is in the array then none of $(x,z,y),(z,y,x)$ and $(y,x,z)$ 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 $(a,b),$ which appears in a given triple, $(a,b,c)$. There cannot exist another triple in the array $(a,b,d),$ say, with $c \ne d$ since $c$ is uniquely determined by $a$ and $b.$

The pair $(a,b)$ cannot appear in more than three triples, in whatever order (we've already noted that we cannot have both $(a,b,c)$ and $(b,a,c)$ 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} (1,2,3) & (1,3,5) & (1,4,7) & (1,5,9) & (1,6,11) \\ (2,3,4) & (2,4,6) & (2,5,8) & (2,6,10) & (2,7,1)\\ (3,4,5) & (3,5,7) & (3,6,9) & (3,7,11) & (3,8,2) \\ (4,5,6) & (4,6,8) & (4,7,10) & (4,8,1) & (4,9,3) \\ (5,6,7) & (5,7,9) & (5,8,11) & (5,9,2) & (5,10,4) \\ (6,7,8) & (6,8,10) & (6,9,1) & (6,10,3) & (6,11,5) \\ (7,8,9) & (7,9,11) & (7,10,2) & (7,11,4) & (7,1,6) \\ (8,9,10) & (8,10,1) & (8,11,3) & (8,1,5) & (8,2,7) \\ (9,10,11) & (9,11,2) & (9,1,4) & (9,2,6) & (9,3,8) \\ (10,11,1) & (10,1,3) & (10,2,5) & (10,3,7) & (10,4,9) \\ (11,1,2) & (11,2,4) & (11,3,6) & (11,4,8) & (11,5,10) \end{array}$$

Note that I'm not using Steiner triples, as $11 \ne 6k+1$ or $6k+3.$

share|improve this answer
1  
Excellent. –  Weltschmerz Jan 1 '11 at 23:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.