Question

В 7^А классе учится 20 человек, и все они очень любят многопользовательские компьютерные игры. Каждый из учащихся играет в одну или две таких игры. При этом для любых 2 учащихся найдется общая игра (в которую играют оба). Найдите наибольшее N, такое, что гарантированно найдется игра, в которую играют не менее N учащихся.

Answer 1

Пусть $$n_i$$ - число учащихся, которые играют в игру $$i$$. Нужно отсортировать игры в порядке возрастания $$n_i$$. Тогда мы можем получить следующую систему неравенств:

$$n_1 + n_2 + \dots + n_{k-1} \le 20$$

$$n_1 + n_2 + \dots + n_{k-1} + n_k 20$$

Где $$k$$ - наибольший индекс, такой что $$n_k \le 20$$. В этой системе неравенств $$n_1 + n_2 + \dots + n_{k-1}$$ является наибольшим возможным числом учащихся, которые играют в одну из игр $$1 \dots k-1$$, а $$n_k$$ - число учащихся, которые играют только в игру $$k$$. Таким образом, наибольшее число $$N$$ учащихся, которые играют в одну игру, равно $$n_1 + n_2 + \dots + n_{k-1}$$. Наша задача - найти наибольшее возможное значение $$k$$.

По условию, для любых двух учащихся найдется общая игра. Это означает, что для любой пары $$(i, j)$$, $$i \ne j$$, выполняется условие $$n_i + n_j 1$$. Также из условия $$n_1 + n_2 + \dots + n_k 20$$ следует, что для любой пары $$(i, j)$$, $$1 \le i, j \le k$$, выполняется условие $$n_i + n_j 1$$. Если мы присвоим значение $$n_i = 1$$ всем играм $$i$$, то условия выше будут выполнены, но сумма $$n_1 + n_2 + \dots + n_k$$ будет меньше $$20$$. Поэтому мы можем заметить, что если $$n_i = 1$$ для некоторых $$i$$, то сумма $$n_1 + n_2 + \dots + n_k$$ будет меньше $$20$$. Отсюда следует, что все игры $$i$$ имеют $$n_i \ge 2$$. Таким образом, наибольшее число учащихся, которые играют в одну игру, равно $$\sum_{i=1}^{k-1} n_i \ge 2(k-1)$$. Поскольку это число должно быть меньше $$20$$, то $$k-1 \le 10$$, что означает, что $$k \le 11$$. Значит, наибольшее число $$N$$ учащихся, которые играют в одну игру, равно $$\sum_{i=1}^{k-1} n_i \ge 2(k-1)$$, где $$k$$ - наибольший индекс, такой что $$n_k \le 20$$. Значит, наибольшее число $$N$$ учащихся, которые играют в одну игру, равно $$2(k-1) = 2(11-1) = 20$$.

ответ: $$\boxed{20}$$.

Answer 2

Наибольшее число N, при котором гарантированно существует игра, в которую играют не менее N студентов, равно 20. Это объясняется тем, что если каждый студент играет в одну или две игры, и для любых двух студентов есть общая игра, то каждый студент должен играть хотя бы в одну игру, которая является общей для всех 20 студентов в классе. Поэтому наибольшее число N, при котором гарантированно найдется игра, в которую играют не менее N учеников, равно 20.