Induction Proof

[intervade]

Hello!

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

Now, I've been doing pretty good on most of the homework with understanding it but this is a different type of problem, and I'm not sure how to set this one up.

Help would be much appreciated!

 

[daon]

n=2 is obvious

assume this holds for n people and consider a line with n+1 people

if the second person is a man, we're done

if the second person is a woman then we look at the line of n people behind the first woman and apply the induction hypothesis to it