Sixteen people are queuing at the bakery. The owner of the bakery offers wine to the customers. A bottle is handed to the first person in line and passed from person to person from the first in line to the last, without returning. The bottle was passed from a woman to a woman four times, from a woman to a man three times, and from a man to a man six times.

a) How many times was the bottle passed from one customer to another?

b) How many times was the bottle passed from a man in the queue to a woman in the queue?

c) Is the first person in the queue a man or a woman? And the last person in the queue?
Solution

a) Each time a person in the line passes the bottle, another must receive it. Except for the first person in line, each person receives the bottle from another person in the line exactly once. Since there are 16 people in the line, the bottle is received 15 times, and thus it is also passed 15 times.

b) The bottle was passed from a woman to a woman 4 times, from a woman to a man 3 times, and from a man to a man 6 times. These transfers account for a total of $4+3+6=13$ times. From the previous item, the total number of times the bottle is transferred is 15. Therefore, the bottle was passed $15-13=2$ times from a man to a woman.

c) (First Solution) Let $N(h, h)=6, N(h, m)=2, N(m, h)=3$, and $N(m, m)=4$ be the number of times the bottle was passed from a man to another man, from a man to a woman, from a woman to a man, and from a woman to another woman, respectively. Observe that:

- the bottle was received by men a total of $N(h, h)+N(m, h)=9$ times;
- the bottle was passed by a man a total of $N(h, h)+N(h, m)=8$ times.

Since men received the bottle more times than they passed it, the last person in the line must be a man, as this is the only person in the line who receives the bottle from someone in the line but does not pass it.

Now observe that:

- the bottle was received by women a total of $N(h, m)+N(m, m)=6$ times;
- the bottle was passed by a woman a total of $N(m, h)+N(m, m)=7$ times.

Since women received the bottle fewer times than they passed it, the first person in the line must be a woman, as this is the only person who passes the bottle without having received it from someone in the line.

(Second Solution) Let's enumerate the 16 people in the order they appear in the line:

$$
\left\{p_{1}, p_{2}, p_{3}, \ldots, p_{15}, p_{16}\right\}
$$

Above, each $p$ with a number as an index represents a person. Since there are 16 people, the indices range from 1 to 16. Don't be alarmed, it's just notation, a way to represent the problem!

We can now divide the set of 16 people into groups of the same gender such that consecutive groups are formed by people of different genders:

$$
\left\{p_{1}, \ldots, p_{16}\right\}=\underbrace{\left\{p_{1}, p_{2}, \ldots, p_{k_{1}}\right\}}_{\text {same gender A }} \cup \underbrace{\left\{p_{k_{1}+1}, p_{k_{1}+2}, \ldots, p_{k_{2}}\right\}}_{\text {same gender B }} \cup \cdots \cup \underbrace{\left\{p_{k_{\ell}+1}, p_{k_{\ell}+2}, \ldots, p_{15}, p_{16}\right\}}_{\text {same gender (A or B) }}
$$

The total number of times the bottle was passed between people of different genders is $3+2=5$. Therefore, we must have exactly 6 groups:

$$
\begin{aligned}
& \underbrace{\left\{p_{1}, \ldots, p_{k_{1}}\right\}}_{\text {same gender A }} \cup \underbrace{\left\{p_{k_{1}+1}, \ldots, p_{k_{2}}\right\}}_{\text {same gender B }} \cup \underbrace{\left\{p_{k_{2}+1}, \ldots, p_{k_{3}}\right\}}_{\text {same gender A }} \cup \\
& \cup \underbrace{\left\{p_{k_{3}+1}, \ldots, p_{k_{4}}\right\}}_{\text {same gender B }} \cup \underbrace{\left\{p_{k_{4}+1}, \ldots, p_{k_{5}}\right\}}_{\text {same gender A }} \cup \underbrace{\left\{p_{k_{5}+1}, \ldots, p_{16}\right\}}_{\text {same gender B }}
\end{aligned}
$$

It is now clear that to have 3 bottle passes from a woman to a man, the people in the groups of gender $A$ must be women and those in the group $B$ must be men. Therefore, the first person in the line is a woman while the last is a man.