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

Kinowagenqe

Answered 2022-09-24
Author has **4** answers

Suppose $n=2m+1$ and consider the triples $(i,i+j,i+2j)$ where $i=1,2,3,\dots ,(2m+1)$ and $j=1,2,3,\dots ,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)={\textstyle (}\genfrac{}{}{0ex}{}{2m+1}{m}{\textstyle )}=$ the number of distinct pairs of integers in $S=\{1,2,3,\dots ,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}$$

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)={\textstyle (}\genfrac{}{}{0ex}{}{2m+1}{m}{\textstyle )}=$ the number of distinct pairs of integers in $S=\{1,2,3,\dots ,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}$$

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(EF)$? Is this $P(E\cap F)$? What is $(}\genfrac{}{}{0ex}{}{48}{12,12,12,12}{\textstyle )$?

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 $\mathrm{lcm}(a,b)=n$ is equal to

$\frac{(2{e}_{1}+1)(2{e}_{2}+1)...(2{e}_{k}+1)+1}{2},$

Where

$n={p}_{1}^{{e}_{1}}{p}_{2}^{{e}_{2}}\dots {p}_{k}^{{e}_{k}}$, pis are prime for all $1\le i\le k$.

$\frac{(2{e}_{1}+1)(2{e}_{2}+1)...(2{e}_{k}+1)+1}{2},$

Where

$n={p}_{1}^{{e}_{1}}{p}_{2}^{{e}_{2}}\dots {p}_{k}^{{e}_{k}}$, pis are prime for all $1\le i\le 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 $\frac{\frac{5!}{2!2!1!0!}\ast 4\ast 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 $(\phantom{\rule{negativethinmathspace}{0ex}}\phantom{\rule{negativethinmathspace}{0ex}}{\textstyle (}\genfrac{}{}{0ex}{}{4}{5}{\textstyle )}\phantom{\rule{negativethinmathspace}{0ex}}\phantom{\rule{negativethinmathspace}{0ex}})$ - number of combinations with repetitions, but I couldn't get the proper answer.

Isn't approach with $(\phantom{\rule{negativethinmathspace}{0ex}}\phantom{\rule{negativethinmathspace}{0ex}}{\textstyle (}\genfrac{}{}{0ex}{}{4}{5}{\textstyle )}\phantom{\rule{negativethinmathspace}{0ex}}\phantom{\rule{negativethinmathspace}{0ex}})$ elementary events more correct?

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 $\frac{\frac{5!}{2!2!1!0!}\ast 4\ast 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 $(\phantom{\rule{negativethinmathspace}{0ex}}\phantom{\rule{negativethinmathspace}{0ex}}{\textstyle (}\genfrac{}{}{0ex}{}{4}{5}{\textstyle )}\phantom{\rule{negativethinmathspace}{0ex}}\phantom{\rule{negativethinmathspace}{0ex}})$ - number of combinations with repetitions, but I couldn't get the proper answer.

Isn't approach with $(\phantom{\rule{negativethinmathspace}{0ex}}\phantom{\rule{negativethinmathspace}{0ex}}{\textstyle (}\genfrac{}{}{0ex}{}{4}{5}{\textstyle )}\phantom{\rule{negativethinmathspace}{0ex}}\phantom{\rule{negativethinmathspace}{0ex}})$ elementary events more correct?