# Induction proof verificiation

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.

Inductive hypothesis:

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.

Inductive step:

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?

• There is no reason to think all but one is male or all but one is female. If we are going to use a formal induction, then strong induction seems like the natural tool. – André Nicolas Mar 26 '15 at 4:26

Your two cases are far from exhausting the possibilities. If $$k=10$$, for instance, the number of women can be anywhere from $$1$$ through $$10$$, and so can the number of men. You need to come up with an argument that covers all possibilities.

Try this: remove the man at the end of the line. Either the new line has a man at the end, in which case you can apply your induction hypothesis to it, or it has a woman at the end. How do you finish the argument in that second case?

• Maybe I've misread your answer but it was a rule in the statement that the first person in the line must be a woman and last must be a man which was why I was only focusing on what came between them when n >= 2 – joe Mar 26 '15 at 4:35
• @joe: There is nothing in my answer that conflicts with that rule; indeed, I assumed it when I wrote ‘the man at the end of the line’. My hint gives you a way to avoid worrying about the details of what’s between them. Instead, you need consider only two cases: the person in front of man at the end is a man, or that person is a woman. – Brian M. Scott Mar 26 '15 at 4:38
• I think I follow. So if person in front of man at end is a man then by the inductive hypothesis there will exist a female directly in front of a man (could be at the front or somewhere in the line) but point being that there will be a female in front. And if it's a female then whatever order follows doesn't matter since there is already a female in front of a male. Is this what you mean in your answer or am I not understanding correctly? – joe Mar 26 '15 at 4:58
• @joe: Yes, that’s exactly what I meant. – Brian M. Scott Mar 26 '15 at 4:59
• @joe: Assume the result true for $k$ people, and consider a line of $k+1$ people with a woman at the front and a man at the back. If the $k$-th person in line is a woman, we’re done: she’s standing immediately in front of the man at the end of the line. If the $k$-th person in line is a man, we can apply the induction hypothesis to the first $k$ people to conclude that somewhere in that line of $k$ people a woman is immediately in front of a man. – Brian M. Scott Mar 28 '15 at 0:28

Let $P(n)$ be true iff there is at least one woman directly in front of a man in a line of length $n, n \ge 2$, and containing only men and women, with the person at the front being a woman and at the back being a man.

Base case:
If $n = 2$, then the woman at the front is directly in front of the man at the back
$\therefore P(2) = true$

Inductive Step:
Assuming the second last person in line must either be a man or a woman:
If the second last person in line is a woman, the man at the end is behind that woman $\therefore P(n) = true$
If the second last person in line is a man, that man is the last in a shorter line which also begins with a woman $\therefore P(n) = P(n-1)$

$\therefore P(n-1) \implies P(n)$ independent of the gender of the second-last person in line. (there is no case where $P(n-1)$ is true and $P(n)$ is false)

$P(2) \land (P(n-1) \implies P(n))$
$\therefore P(n), \forall n \ge 2$

Starting from the last person in the line, in front of him must be a woman (solved) or a man. in front of this man must be a woman (solved), or another man. Eventually a woman must appear, because the first person in the queue is a woman (solved).

Also if true for $k$, then inserting a man or a women anywhere but the change is ok, but so is inserting a man/woman in between the change.

For example, WWWMM -> WMWWMM (ok) or WWW(W/M)MM (ok)

• what wrong - if you don't tell me, i don't know – JMP Mar 26 '15 at 4:48