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.

Question

Kinowagenqe · Accepted Answer

Suppose   n  =  2  m  +  1 and consider the triples   (  i  ,  i  +  j  ,  i  +  2  j  ) where   i  =  1  ,  2  ,  3  ,  …  ,  (  2  m  +  1  ) and   j  =  1  ,  2  ,  3  ,  …  ,  m  .. We can construct a   (  2  m  +  1  )  ×  m array of triples with   (  i  ,  i  +  j  ,  i  +  2  j  ) in the   ith row and   jth column. We work modulo   2  m  +  1..For example here&#039;s a solution for   n  =  9.                    (        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        )            The number of triples =   m  (  2  m  +  1  )  =                              (                                      2          m          +          1                m                              )                      = the number of distinct pairs of integers in   S  =  {  1  ,  2  ,  3  ,  …  ,  2  m  +  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  +  2  j for some   i  ,  j and thus if   x  &amp;lt;  y this triple is in the   xth row and   (  y  −  x  )th column, and if   x  &amp;gt;  y it is in the   xth row and   (  y  −  x  +  2  m  +  1  )th column. So its position is uniquely determined by its elements.Moreover, if   (  x  ,  y  ,  z  )  =  (  i  ,  i  +  j  ,  i  +  2  j  ) 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  ≠  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&#039;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  ≥  3..So a solution for   n  =  11 is:                    (        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        )

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.

Answered question

Answer & Explanation

New Questions in Precalculus