Условие
В банде 50 бандитов. Все вместе они ни в одной разборке ни
разу не участвовали, а каждые двое встречались на разборках
ровно по разу. Докажите, что один из бандитов был
не менее, чем на восьми разборках.
Подсказка
Покажите, что в одной из разборок Р участвовало не менее восьми
бандитов; с каждым из них бандит, не участвовавший в
разборке Р, должен встретиться на разных разборках.
Решение
Допустим противное. Выберем бандита А. Он участвовал не
более, чем в 7 разборках, причем
каждый из оставшихся бандитов присутствовал
ровно на одной из этих разборок.
Всего бандитов (без бандита А) 49, поэтому хотя бы в
одной из разборок (обозначим ее через Р) участвовало не меньше 7
бандитов, всего же на этой разборке (вместе с А) участвовало не
меньше 8 бандитов. Возьмем бандита Б, не участвовавшего в
разборке Р. Он искомый, так как он участвовал в разборках со всеми
бандитами разборки Р, причем все эти разборки различны. Действительно,
пусть Х и У - бандиты, участвовавшие в разборке Р, а
С - разборка, в которой участвовали Б, Х и У.
Тогда Х и У участвовали в двух разборках Р и С,
что противоречит условию задачи.
Источники и прецеденты использования
