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.

Lindsey Ibarra 2022-09-23 Answered
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

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

Kinowagenqe
Answered 2022-09-24 Author has 4 answers
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'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 < y this triple is in the xth row and ( y x )th column, and if x > 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'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 )
Did you like this example?
Subscribe for all access

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2021-09-08

A restaurant offers a $12 dinner special with seven appetizer options, 12 choices for an entree, and 6 choices for a dessert. How many different meals are available when you select an appetizer, an entree,and a dessert?

asked 2021-09-09
In a fuel economy study, each of 3 race cars is tested using 5 different brands of gasoline at 7 test sites located in different regions of the country. If 2 drivers are used in the study, and test runs are made once under each distinct set of conditions, how many test runs are needed?
asked 2022-11-25
A three-person committee is needed to study ways of improving public transportation. Ho many committees could be formed from the eight people on the board of supervisors?
asked 2021-09-11
There are 5 women and 3 men waiting on standby for a flight to New York. Suppose 3 of these 8 people are selected at random, and a random variable X is defined to be the number of women selected. Find Pr[X = 2].
asked 2022-07-02
What is P ( E F )? Is this P ( E F )? What is ( 48 12 , 12 , 12 , 12 ) ?
asked 2022-05-22
How can we show that the number of pairs ( a , b ) (where the pairs ( a , b ) and ( b , a ) are considered same) with lcm ( a , b ) = n is equal to
( 2 e 1 + 1 ) ( 2 e 2 + 1 ) . . . ( 2 e k + 1 ) + 1 2 ,
Where
n = p 1 e 1 p 2 e 2 p k e k , pis are prime for all 1 i k.
asked 2022-07-14
Simple combinatorics and probability theory related question
5 apples are randomly distributed to 4 boxes. We need to find probability that there are 2 boxes with 2 apples, 1 box with 1 apple and 1 empty box.
I'm getting the correct answer with 5 ! 2 ! 2 ! 1 ! 0 ! 4 3 4 5 = 0.3515625 (anyway, the answer is said to be 0.35, but I think it is a matter of rounding).
But I don't understand why there are 4 5 elementary events in total. Firstly, I thought It should be ( ( 4 5 ) ) - number of combinations with repetitions, but I couldn't get the proper answer.
Isn't approach with ( ( 4 5 ) ) elementary events more correct?

New questions