Question

В 6B классе учится 20 человек, и все они очень любят многопользовательские компьютерные игры. Каждый из учащихся играет в одну или две таких игры. При этом для любых 2 учащихся найдется общая игра (в которую играют оба). Найдите наибольшее Y, такое, что гарантированно найдется игра, в которую играют не менее Y учащихся. (ПОМОГИТЕ ПЖ)

Answer 1

Пусть X - количество игр, в которые играет каждый учащийся. Тогда из 20 учащихся в каждую игру играет не менее 20/X человек.

Если X = 1, то в каждую игру играет не менее 20 человек, что удовлетворяет условию.

Если X = 2, то в каждую игру играет не менее 10 человек. Если бы существовала игра, в которую играли более 10 человек, то это была бы общая игра для любых 2 учащихся, что противоречит условию.

Поэтому наибольшее Y равно 10.

Answer 2

Для решения этой задачи можно воспользоваться принципом Дирихле, который утверждает следующее:

Если n + 1 объектов распределить по n ящикам, то в одном из ящиков окажется хотя бы два объекта.

Применим этот принцип к нашей задаче. У нас есть 20 учащихся и каждый играет в одну или две игры. Предположим, что существует игра, в которую играет менее Y учащихся, где Y - некоторое число, которое мы хотим найти.

Предположим, что для каждого учащегося мы отводим по одному "ящику". Если учащийся играет только в одну игру, он помещается в соответствующий "ящик". Если учащийся играет в две игры, он также помещается в соответствующий "ящик".

Таким образом, у нас будет 20 "ящиков". По принципу Дирихле, если в каждый "ящик" помещено только одно число (число учащихся, играющих в определенную игру), то в одном из "ящиков" будет хотя бы два числа.

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