Крупная конференция переводчиков

[mc_krg]

На крупной конференции переводчиков некоторые знают по несколько языков. Известно, что казахский знают 2016 переводчиков, русский 2016 переводчиков, и английский знают тоже 2016 переводчиков. При каких натуральных значениях $\rho$ из этой группы всегда можно выбрать несколько переводчиков, чтобы среди них было ровно $\rho$ знающих казахский, ровно $\rho$ знающих русский и ровно $\rho$ знающих английский.

[melnikoff]

Пусть К - множество людей, знающих казахский, Р - множество людей, знающих русский, А - множество людей, знающих английский.
Нужно построить алгоритм, на каждом шаге которого мы выбираем некоторое кол-во людей из уменьшаемого множества всех переводчиков и добавляем их в новое множество, в результате чего $\rho$ увеличивается ровно на единицу.
1. Если $K\cap P\cap A \neq \varnothing$, то выбираем одного человека из $K\cap P\cap A$ ($\rho = 1$). Очевидно, что $\rho$ может принимать значения от 1 до $|K\cap P\cap A|$ (нужно просто выбрать всех переводчиков из $K\cap P\cap A$).
2. Рассмотрим множества $K\cap P$, $K\cap A$ и $P\cap A$. Пусть для определенности $|K\cap P| > |K\cap A| > |P\cap A|$. Тогда выбираем одного человека из $K\cap P$ и одного человека из $A$, и переносим их в новое множество. Тем самым $\rho$ увеличивается до $|K\cap P\cap A| + 1$. Продолжаем до тех пор, пока не выполнится $|K\cap P| = |K\cap A|$. После этого начинаем поочередно выбирать пары человек сначала из $K\cap P$ и $A$ по одному, затем из $K\cap A$ и $P$ по одному, до тех пор, пока не выполнится $|K\cap P| = |K\cap A| = |P\cap A|$. На каждом шаге выбора, $\rho$ увеличивается на 1.
3. Осталось три равномощных непересекающихся множества: подмножество K, подмножество P и подмножество A. Теперь для увеличения $\rho$ на 1 на каждом шаге выбираем по одному элементу из этих множеств до тех пор, пока не исчерпаем все оставшиеся элементы из первоначального множества всех переводчиков. В конце алгоритма $\rho = 2016$.
Ответ: $\rho$ может принимать любые значения от 1 до 2016.

[arseniiv]

(Формулы)

Чем $\bigcap$ настолько лучше $\cap$ \cap?

Для сравнения:

$$\begin{array}{c} K\bigcap P\bigcap A, \\ K\cap P\cap A. \end{array}$$

Исходно \bigcap предназначен для набора пересечений индексированных семейств множеств: $\bigcap\limits_{i\in I} B_i,$

$$\bigcap_{n=11}^{813} A_n.$$

[arqady]

(Оффтоп)

arseniiv в сообщении #1175793 писал(а):

Исходно \bigcap предназначен для набора пересечений индексированных семейств множеств: $\bigcap_{i\in I} B_i,$

It must be $\bigcap\limits_{i\in I} B_i$

[arseniiv]

(Оффтоп)

Хм, да, спасибо, лучше сделаю \limits, у нас же не принято индексы вправо выводить.

[Cash]

melnikoff в сообщении #1175786 писал(а):

Тогда выбираем одного человека из $K\cap P$ и одного человека из $A$, и переносим их в новое множество. Тем самым $\rho$ увеличивается до $|K\cap P\cap A| + 1$.

В этом случае у нас гарантирован один человек, знающий английский. Сколько знают казахский или русский - вопрос.
mc_krg, вы уверены, что задание не с действующей олимпиады?

[melnikoff]

Cash, ага, ошибочка. Нужно выбирать одного человека из $K\cap P$ и одного человека из $A\setminus (K\cup P)$. Напоминаю, что после первого пункта $A\cap K\cap P = \varnothing.$
Тоже интересно откуда задача.

[Cash]

melnikoff в сообщении #1175786 писал(а):

3. Осталось три равномощных непересекающихся множества: подмножество K, подмножество P и подмножество A.

Увы, еще нет. У нас только $|K\cap P| = |K\cap A| = |P\cap A|$, но не $|K\cap P| = |K\cap A| = |P\cap A|=0$

[melnikoff]

Cash, точно. Пропустил один пункт. 3-м пунктом должен быть выбор "по кругу" из пересечений и "противоположного" множества до тех пор, пока пересечения не истощатся.

[Cash]

melnikoff, в "противоположном" множестве может и не быть элементов.

[DeBill]

Если каждый знает ровно два языка, то токо четные $\rho$ годятся....
Однако это, видимо, единственное исключение: во всех остальных проходит "индукция" melnikoffа.
Именно, на шаге "индукции", будем, для заданного $n=2016$, искать набор для $\rho = 1$ (и выгоним их потом - равенство кол-в знающих языки сохранится - индукция пойдет дальше). Если есть полиглот - хорошо. Если есть три, знающих по одному языку - хорошо. Осталось: нет тройных пересечений, и знающий русский еще ченибудь знает. Если знающий Р знает и К, и есть знающий токо А, то - хорошо. Аналогично - наоборот. Остался токо вариант, когда каждый знает ровно по два языка - и тогда их всех поровну, и из них можно сотавить любое четное $\rho$. Итог: если удалось в начале сделать шаг на 1, то любые $\rho$ годятся (добавляя-убавляя этот наборчик). Если же изначально мы вляпались в последнюю возможность - только четные и проходят.

[mc_krg]

Cash в сообщении #1175830 писал(а):

melnikoff в сообщении #1175786 писал(а):

Тогда выбираем одного человека из $K\cap P$ и одного человека из $A$, и переносим их в новое множество. Тем самым $\rho$ увеличивается до $|K\cap P\cap A| + 1$.

В этом случае у нас гарантирован один человек, знающий английский. Сколько знают казахский или русский - вопрос.
mc_krg, вы уверены, что задание не с действующей олимпиады?

Олимпиада для 9-го класса.

[Lia]

Тема закрыта до внятных объяснений ТС, с какой именно олимпиады задача. Со ссылкой и прочее.

В ЛС, пожалуйста.