## Behind a man there is a woman

Imagine a queue consisting of men and women only. The first person in the queue is a man, and the last person is a woman. An autistic child refuses to believe that somewhere in the queue there is a woman directly behind a man. Fortunately, some teachers have succeeded in teaching him the principle of mathematical induction. Now, can you show the child, using mathematical induction only, that somewhere in the queue, directly behind a man there is a woman?

[SOLVED]

#### Siddhesh Chaubal solved this puzzle:

Let there be $$n$$ people in the queue.

Base case: If $$n = 2$$, directly behind the man who stands first in the queue, there is a woman who stands last in the queue.

Induction hypothesis: Let us assume that in a queue of $$n$$ people where the first person is a man and the last one is a woman, it is true that there is a woman directly behind a man somewhere in the queue.

Induction step: In a queue of $$n + 1$$ people, the $$(n + 1)$$th person in the queue is a woman. If the $$n$$th person in the queue is a man, this man has a woman directly behind him. If the $$n$$th person in the queue is a woman, by induction hypothesis, somewhere in the queue consisting of the first $$n$$ people only, there is a woman directly behind a man.

#### Rino Raj solved this puzzle:

Let $$P(n)$$ be the statement that in a queue of $$n$$ people ($$n \gt 1$$), first being a man and the last being a woman, there is always a woman directly behind a man somewhere in the queue. Now $$P(2)$$ is true because the last woman is directly behind the first man.

Let us assume that $$P(n)$$ is true. In the queue of size $$n$$, by the induction hypothesis, there is a woman $$B$$ directly behind a man $$A$$, somewhere in the queue. Now for $$P(n + 1)$$, we can add a person $$C$$, to a queue of size $$n$$. Now, if $$C$$ is not added in between $$A$$ and $$B$$, clearly the woman $$B$$ still remains directly behind the man $$A$$ and $$P(n + 1)$$ is true. Now, consider that $$C$$ is inserted between $$A$$ and $$B$$. Now we have $$A$$-$$C$$-$$B$$ in the queue. Now if $$C$$ is a man, $$C$$-$$B$$ proves $$P(n + 1)$$. However, if $$C$$ is a woman, $$A$$-$$C$$ proves $$P(n + 1)$$.

### Credit

This is an original puzzle from cotpi.