2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Депутаты и комбинаторика
Сообщение20.10.2010, 10:25 


01/10/10

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

 Профиль  
                  
 
 Re: Депутаты и комбинаторика
Сообщение20.10.2010, 11:24 
Заслуженный участник
Аватара пользователя


23/07/08
10910
Crna Gora
Xenia1996 в сообщении #363835 писал(а):
Известно, что для любой группы из шести депутатов можно подобрать хороший состав из двух.
Ксения, Вы не могли бы чуть подробнее пояснить эту фразу. Что за группа: хороший состав выбирается из этой группы, или он хороший для этой группы? Из двух депутатов или из двух разных вариантов хороших составов?

 Профиль  
                  
 
 Re: Депутаты и комбинаторика
Сообщение20.10.2010, 11:33 


01/10/10

2116
Израиль (племянница БизиБивера)
svv в сообщении #363847 писал(а):
Что за группа: хороший состав выбирается из этой группы, или он хороший для этой группы?


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

svv в сообщении #363847 писал(а):
Из двух депутатов или из двух разных вариантов хороших составов?

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

 Профиль  
                  
 
 Re: Депутаты и комбинаторика
Сообщение20.10.2010, 12:12 
Заблокирован
Аватара пользователя


17/06/09

2213
Что-то я не совсем понял, но попробую так.
Пусть в парламенте $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$. :?

 Профиль  
                  
 
 Re: Депутаты и комбинаторика
Сообщение20.10.2010, 12:20 


01/10/10

2116
Израиль (племянница БизиБивера)
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

 Профиль  
                  
 
 Re: Депутаты и комбинаторика
Сообщение22.10.2010, 21:18 
Модератор
Аватара пользователя


11/01/06
5710
Xenia1996 в сообщении #363835 писал(а):
В парламенте некоторой страны в рамках создания новой комиссии все депутаты заполняют бланк. Каждый депутат вписывает в бланк $14$ достойнейших, по его мнению, депутатов. Состав комиссии считается хорошим для депутата, если в нем присутствует кто-нибудь из его списка достойнейших. Известно, что для любой группы из шести депутатов можно подобрать хороший состав из двух. На комиссию нужно собрать депутатский состав из $n$ человек, хороший для всех депутатов. При каком максимальном $n$ это может оказаться невыполнимым?

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Shadow


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group