Turkey TST 1998 Problem 4, n houses and n people
Source: Turkey TST 1998 Problem 4
December 2, 2011
combinatorics proposedcombinatorics
Problem Statement
Suppose houses are to be assigned to people. Each person ranks the houses in the order of preference, with no ties. After the assignment is made, it is observed that every other assignment would assign to at least one person a less preferred house. Prove that there is at least one person who received the house he/she preferred most under this assignment.