Turkey TST 1998 Problem 4, n houses and n people

[drago]

Имаме [tex]n[/tex] къщи, които трябва да бъдат разпределени между [tex]n[/tex] човека. Всеки човек е направил списък, в който е подредил една след друга къщите според предпочитанията му.
След като разпределението е вече направено се установило, че при всяко друго разпределение ще има човек, който ще получи по-малко предпочитана къща от тази, която е получил.
Докажете, че при така направеното разпределение има човек получил къщата, която е поставил на първо място в списъка с предпочитанията.

Може да видите и английския текст тук: http://www.artofproblemsolving.com/Foru ... 2&t=449149

[drago]

Да означим хората с номерата [tex]1,2,\cdots,n[/tex]. Къщата, която е разпределена на човека с номер [tex]n[/tex] я означаваме с [tex]n[/tex]. С тези означения [tex]n[/tex]-тата къща е разпределена на [tex]n[/tex]-тия човек.
Списъкът с предпочитанията на [tex]i[/tex]-тия човек може да бъде представен с пермутацията [tex]\sigma_{i}[/tex].
Нека сега допуснем противното, че няма човек, който е получил къща, поставена на първо място в списъка му т.е. [tex]\sigma_i(1) \neq i,\, i=1,2,\cdots,n[/tex].
Идеята е да се конструира пермутация [tex]\sigma[/tex] (различна от идентитета), за която [tex]\sigma(i) = i[/tex] или [tex]\sigma(i) = \sigma_i(1)[/tex]. Ако такава пермутация съществува това ще противоречи на условието.
За тази цел построяваме следната редица:
[tex]a_1 = 1, \, b_1 = \sigma_1(1);\, a_{i+1} = b_i,\, b_{i+1} = \sigma_{a_{i+1}}(1)[/tex].
Ясно е, че [tex]b_i \neq a_i[/tex]. В тази редица ще дойде момент, когато [tex]b_k = b_s,\, s < k[/tex]. Сега дефинираме пермутацията [tex]\sigma[/tex] по следния начин:

Ако [tex]i=a_j[/tex] за някое [tex]j=s+1,s+2,\cdots, k[/tex] тогава [tex]\sigma(i) = b_j[/tex], в противен случай [tex]\sigma(i) = i[/tex].

Вижда се, че това е пермутация и че при такова разпределение на къщите няма да има човек, който получава къща намираща се по-назад в списъка му от тази която е получил в началото.
Това е противоречие, което доказва, че има човек получил къщата, намираща се на първо място в списъка му.