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