Use well-ordering property to prove that if n people stand in a line, where n is a positive integer, and if the first person in the line is a woman and the last person in line is a man, then somewhere in the line there is a woman directly in front of a man.

Question

Harper Middleton

Mathematics

22 May, 12:04

Use well-ordering property to prove that if n people stand in a line, where n is a positive integer, and if the first person in the line is a woman and the last person in line is a man, then somewhere in the line there is a woman directly in front of a man.

+3

Answers (1)

Know the Answer?

Zaid Campos · Answer 1

The people forming the line form a well ordered set, this means, every non empty subset has a minimum. In other words, in any smaller (but non empty) set of people there will always be one that is last in the line.

Lets take the subset formed of all the Women in the line. This subset in non empty because there is a women in the line (the first person in the line is a women), therefore, there is a women that is behind every other women in the line; this women can only have men behind, if any. If she had no men behind her, then she should be last in the line, bacause the doesnt have any men or women behind her. This is a contradiction because there is a man at the end of the line, not a woman. This shows that this woman that is behind every other woman has men behind, in particularly immediately behind, her.