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]

2 comments

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.

Post a comment

RSS