Proof Induction question

N

nwicole

New member
Joined
Oct 6, 2014
Messages
18
  1. Prove that, in a line of at least 2 people, if the 1st person is a woman and the last person is a man, then somewhere in the line there is a man standing immediately behind a woman.
    I dont get how to set the question
  2. thank you so much
 
nwicole said:
Prove that, in a line of at least 2 people, if the 1st person is a woman and the last person is a man, then somewhere in the line there is a man standing immediately behind a woman.
Click to expand...
Follow the usual procedure for induction proofs:

base case: n = 2
If there are only two people in line, then... what?

assumption: n = k
If there are k people in line, we assume that there is, at some point, a man standing immediately behind a woman somewhere within the line.

induction: n = k + 1
If there are k + 1 people in line, then we consider two cases. If there is a man in the second position, then... what? If not, then there is a woman in the second position. In this case, remove the first woman in line, leaving a line of k people with a woman first and a man last. Then... what? ;)
 
stapel said:
Follow the usual procedure for induction proofs:

base case: n = 2
If there are only two people in line, then... what?

assumption: n = k
If there are k people in line, we assume that there is, at some point, a man standing immediately behind a woman somewhere within the line.

induction: n = k + 1
If there are k + 1 people in line, then we consider two cases. If there is a man in the second position, then... what? If not, then there is a woman in the second position. In this case, remove the first woman in line, leaving a line of k people with a woman first and a man last. Then... what? ;)
Click to expand...

ok I get it thank you so much
one more question do I need to set the base case for n=2 which n must greater than 2?

again thank you so much :)
 
You must log in or register to reply here.
Top