Депутаты и комбинаторика

[Xenia1996]

В парламенте некоторой страны в рамках создания новой комиссии все депутаты заполняют бланк. Каждый депутат вписывает в бланк $14$ достойнейших, по его мнению, депутатов. Состав комиссии считается хорошим для депутата, если в нем присутствует кто-нибудь из его списка достойнейших. Известно, что для любой группы из шести депутатов можно подобрать хороший состав из двух. На комиссию нужно собрать депутатский состав из $n$ человек, хороший для всех депутатов. При каком максимальном $n$ это может оказаться невыполнимым?

[svv]

Xenia1996 в сообщении #363835 писал(а):

Известно, что для любой группы из шести депутатов можно подобрать хороший состав из двух.

Ксения, Вы не могли бы чуть подробнее пояснить эту фразу. Что за группа: хороший состав выбирается из этой группы, или он хороший для этой группы? Из двух депутатов или из двух разных вариантов хороших составов?

[Xenia1996]

svv в сообщении #363847 писал(а):

Что за группа: хороший состав выбирается из этой группы, или он хороший для этой группы?

Для этой группы.

svv в сообщении #363847 писал(а):

Из двух депутатов или из двух разных вариантов хороших составов?

Из двух депутатов.

[age]

Что-то я не совсем понял, но попробую так.
Пусть в парламенте $n$ депутатов. Исходя из того, что в бланк вписывается $14$ достойнейших, то это и есть количество членов комиссии.
Далее, дано, что для любой выборки из 6 человек есть 2 достойнейших, то это дает нам общее условие на количество достойнейших депутатов.
Другими словами, из общей совокупности получаем $C_6^2$ - "хороших" выборок, на каждую из которых приходится $C_{n-6}^4$ - "плохих" выборок.
Отсюда получаем количество достойнейших депутатов, как функцию от $n$:
$D(n)=\dfrac{C_n^6}{C_6^2\cdot C_{n-6}^4}$.
Ну и соответственно, т.к. в комиссии 14 членов, то для выполнения условий задачи она должна удовлетворять таким же требованиям:
$C_{D(n)}^1$ - из общего числа достойнейших д.б. хотя бы один.
$C_{n-D(n)}^{13}$ - все остальные могут быть не достойнейшими.
$C_n^{14}$ - общее число выборок по 14 членов из $n$.
Т.е. должно выполняться условие $\dfrac{C_n^{14}}{C_{D(n)}^1\cdot C_{n-D(n)}^{13}}\geq1$.

Но вот дальше у меня получается, что данное условие выполнимо при любых $n\geq16$.

[Xenia1996]

age в сообщении #363858 писал(а):

Что-то я не совсем понял, но попробую так.
Пусть в парламенте $n$ депутатов. Исходя из того, что в бланк вписывается $14$ достойнейших, то это и есть количество членов комиссии.
Далее, дано, что для любой выборки из 6 человек есть 2 достойнейших, то это дает нам общее условие на количество достойнейших депутатов.
Другими словами, из общей совокупности получаем $C_6^2$ - "хороших" выборок, на каждую из которых приходится $C_{n-6}^4$ - "плохих" выборок.
Отсюда получаем количество достойнейших депутатов, как функцию от $n$:
$D(n)=\dfrac{C_n^6}{C_6^2\cdot C_{n-6}^4}$.
Ну и соответственно, т.к. в комиссии 14 членов, то для выполнения условий задачи она должна удовлетворять таким же требованиям:
$C_{D(n)}^1$ - из общего числа достойнейших д.б. хотя бы один.
$C_{n-D(n)}^{13}$ - все остальные могут быть не достойнейшими.
$C_n^{14}$ - общее число выборок по 14 членов из $n$.
Т.е. должно выполняться условие $\dfrac{C_n^{14}}{C_{D(n)}^1\cdot C_{n-D(n)}^{13}}\geq1$.

Но вот дальше у меня получается, что данное условие выполнимо при любых $n\geq16$.

(правильный ответ - здесь)

13

[maxal]

Xenia1996 в сообщении #363835 писал(а):

В парламенте некоторой страны в рамках создания новой комиссии все депутаты заполняют бланк. Каждый депутат вписывает в бланк $14$ достойнейших, по его мнению, депутатов. Состав комиссии считается хорошим для депутата, если в нем присутствует кто-нибудь из его списка достойнейших. Известно, что для любой группы из шести депутатов можно подобрать хороший состав из двух. На комиссию нужно собрать депутатский состав из $n$ человек, хороший для всех депутатов. При каком максимальном $n$ это может оказаться невыполнимым?

Понятно, что хорошую для всех комиссию из 13 (или больше) депутатов всегда можно составить. Для этого достаточно выбрать 13 человек из списка какого-либо депутата X. Так как любой другой депутат Y состоит с X в какой-то шестерке, то у них в списках как минимум двое общих депутатов, причём как минимум один из этих общих депутатов выбран в комиссию (так как только один депутат из списка X в комиссию не попал). Поэтому комиссия является хорошей и для Y.
Остается доказать, что существует такая ситуация, что хорошую для всех комиссию из 12 человек выбать не удасться.