Thread: Proof by induction

A group of people stand in line to purchase movie tickets. The first person in line is a woman and the last person in line is a man. Use proof by induction to show that somewhere in the line a woman is directly in front of a man.

This seems so obvious... but I'm not sure how to prove it using induction. Could someone give me a hint?

well prove the base case first.
If there are only 2 people in line then the first will be a woman, and the 2nd/last will be a man.

Thanks for your tip on how to start it. I've been working on it more, and this is what I have... would this be sufficient?

Let N represent the number of people in the line.

Basis step: Let N=2. If there are only two people in the line, then clearly a woman is directly in front of a man. Our base case is confirmed and we can continue.

Induction hypothesis: Suppose that in a line of k people, a woman is directly in front of a man.

Next, we need to show that in a line of k+1 people, a woman is directly in front of a man.

Look at the second to last person. If the second to last person is a woman, then clearly a woman is directly in front of a man, and we're done. On the other hand, if the second to last person is a man, then remove the last person and we have the exact same line as k, and therefore a woman is still directly in front of a man. Therefore, the statement is true for k + 1 people.