P(n) = in a line of n people show that somewhere in the line a woman is directly in front of a man. The first person will always be a woman and the last person in the line will always be a man
I wanted to prove this with induction and I was a little unsure of how to express this problem in the inductive step and whether I had the right cases and if I had shown them correctly.
Base case: n=2:
P(2) holds as a woman (front of line) will be directly in front of the man at the back of line since there are only 2 people.
Assume P(k) holds for some integer k >= 2 there will be a woman directly in front of a man somewhere in the line, where the kth person is at the back of the line.
Assuming P(k) holds, show P(k+1) holds too:
In a group of k+1 people consider the cases: (this is where I am slightly unsure)
(1) There are k males and 1 female
(2) There are k females and 1 male
- Case (1):
If there are k males and 1 female, k males will always be behind the 1 female at the front by the rule in the statement and so the 2nd male from the front will be directly behind the female at the front and so there is always at least one case where a female is directly in front of a male while there are k males and 1 female in a group of k+1 people
- Case (2):
If there are k females and 1 male, k females will always be in front of the 1 male at the back of the line by the rule of the statement and so the kth person who is a female will be directly in front of the k+1 person who is a male.
So in both cases there will always be at least one case where a female is directly in front of a male in a line of k + 1 people which concludes the inductive step.
As mentioned, I'm unsure if I've included the correct and all cases necessary in the inductive step and if I've explained them correctly for this proof. Could you verify and provide any pointers?