Question

В посёлке построили N дачных участков. N дачников, осмотрев участки, составили (каждый для себя) рейтинг участков: какой нравится больше всего, какой на втором месте, какой - на третьем, и так далее (ни одному из дачников никакие два участка не нравятся в равной степени). После случайного распределения участков между дачниками оказалось, что при любом другом распределении хотя бы один дачник получил менее нравящийся ему участок. Докажите, что хотя бы один дачник получил участок, который ему нравится больше всего.

Answer 1

Докажем, что если после случайного распределения участков ни одному из дачников не достался лучший на его взгляд участок (*), то возможно перераспределить участки так, чтобы каждому достался более хороший на его взгляд участок. В условии же сказано, что распределение оказалось таково, что при любом другом, хотя бы одному достался бы более плохой участок. Если мы докажем вышеизложенное утверждение, то по противоречию будет следовать, что распределение не отвечает условию (*), а значит задача решена.

Рассмотрим таблицу $N\times N$, где за строками скрываются дачники, а за столбцами - участки. В пересечении строки и столбца будет стоять число $1\leq A_{ij}\leq N$, которое равно месту, которое отдал i-ый дачник j-ому участку.

Пусть произошло распределение по условию (*). Пусть i-ому участнику достался участок с местом (на его взгляд) i; Тогда существует $i-1$ участок, который лучше того, который ему достался. Аналогично для остальных дачников. Для того, чтобы перераспределить участки необходимо, чтобы сумма всех участков, которые лучше того, что достались дачнику была не меньше общего количества дачников (иначе были бы пересечения и на один участок претендовало бы не менее двух дачников). То есть $\sum\limits_i g-N\geq N \Leftrightarrow \sum\limits_i g\geq 2N$; Так как никому не досталось первое место, а у каждого место не выше второго, то действительно сумма мест не меньше удвоенного количества дачников. Неравенство справедливо, а, значит, задача решена

Answer 2

Допустим, что ни один дачник не получил участок, который ему нравится больше всего. Это означает, что для каждого дачника его любимый участок был присвоен другому.

Рассмотрим одного из дачников, обозначим его A. Пусть его любимый участок был присвоен дачнику B. Тогда в своем рейтинге дачник B поставил этот участок на первое место. Поскольку каждый участок может быть только на первом месте у одного дачника, то участок, на который дачник B поставил первое место, был присвоен дачнику A.

Теперь рассмотрим участок, на который дачник A поставил второе место в своем рейтинге. Пусть этот участок был присвоен дачнику C. Тогда в своем рейтинге дачник C поставил этот участок на первое или второе место (поскольку никакие два участка не нравятся дачнику одинаково), иначе он бы поставил на первое место участок, который нравится ему больше. Если дачник C поставил этот участок на первое место, то мы можем повторить рассуждения, как для дачников A и B, и показать, что участок, на который дачник C поставил первое место, был присвоен дачнику A. Если же дачник C поставил этот участок на второе место, то мы можем продолжить аналогично и показать, что участок, на который дачник C поставил первое место, был присвоен дачнику A.

Таким образом, мы показали, что участок, на который дачник A поставил второе место в своем рейтинге, был присвоен дачнику A. Но это противоречит нашему предположению, что ни один дачник не получил участок, который ему нравится больше всего. Следовательно, по крайней мере, один дачник получил участок, который ему нравится больше всего.