Prove that if $n$ people are standing on line at a ticket counter, and the first person on line is a woman and the last is a man, then somewhere on the line there is a man standing directly behind a woman. (Perform induction on $n$, the number of people on line.) Well I know the steps to induction. But what is the approach and how do I set it up and prove it?
2026-05-16 15:18:13.1778944693
On
On
An induction problem that I can't think of an approach.
155 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
3
There are 3 best solutions below
0
On
Break it into cases. If person $n-1$ is a man, use the induction hypothesis. If it's a woman, then the last person in line has to be a man, so...
The base case is $n=2$, and I think you can probably prove it's true in that case.
0
On
Base case ($n=2$): man at back is right behind woman in front. So clearly a man is standing right behind a woman.
Inductive Step: Assume true for $n=k$, so for any line $k$ people long there is a man standing right behind a woman. Then suppose you are faced with a line of $k+1$ people. Remove a person not at either end - the resulting line ($k$ people long) has a man standing right behind a woman by the inductive assumption. If the person you removed was not between that man and woman, then the man was right behind the woman to begin with. If the person you removed was between the man and woman to begin with, then (since the person was either a man or woman themselves), the two options are:
- woman, removed woman, man
- woman, removed man, man
In either case, there is a man standing right behind a woman.
By the principle of induction, there is always a man standing right behind a woman.
Partial solution:
The base case is pretty easy:
Let $n = 2$ then there are two people in line. The first one a woman, and the second one a man. Then the man is directly behind the first woman.
Now you probably want to use strong induction. Assume it holds for $n=k, k-1, \ldots 2$ and consider when there are $k+1$ people in line. We know the $k+1$ person is a man and he is either behind a man or a woman. If he is behind a woman we are done, otherwise what can we do after that?