В каждом из трех университетов обучается по 300 студентов. У любого студента всего 301 знакомый из двух других университетов. Докажите, что вы можете выбрать
по одному студенту от каждого университета, так что выбранные три студента
знакомы друг с другом
Ответы на вопрос:
Среди всех 3n учеников выберем такого ученика (точнее, одного из таких учеников), который имеет наибольшее число kk знакомых в одной из двух других школ. Пусть для определенности им оказался ученик А первой школы, который знает kk учеников, например, из второй школы. Тогда А знает n+1–kn+1–k учеников из третьей школы, причем n+1–k≥1n+1–k≥1, так как k≤nk≤n. Рассмотрим ученика В третьей школы, знакомого с А. Если В знает хотя бы одного ученика С из kk знакомых А во второй школе, то ученики A, В, С образуют искомую тройку. Если же В не знает никого из kk знакомых А во второй школе, то в этой школе он знаком не более чем с n–kn–k учениками, а значит, в первой школе он знаком не менее чем с n+1−(n−k)=k+1n+1−(n−k)=k+1 учениками, что противоречит выбору kk.
Популярно: Математика
-
AlionaNigrevskaya18.11.2021 04:36
-
Ксения22233222.10.2020 10:27
-
Yaroslav164004.03.2020 15:15
-
Polinazaya0212.01.2023 13:47
-
Qwer3313qw24.05.2023 01:40
-
voloseikotatian30.11.2020 22:01
-
falaleevakata427.06.2020 19:16
-
Svetlanaaaa1605.12.2022 12:39
-
IBRAGIM05820.06.2020 08:49
-
лоло9713.06.2023 11:57