2014 dxdy logo

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

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




Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.
 
 Крупная конференция переводчиков
Сообщение09.12.2016, 08:21 


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

 Профиль  
                  
 
 Re: Крупная конференция переводчиков
Сообщение10.12.2016, 22:45 


02/04/13
289
Пусть К - множество людей, знающих казахский, Р - множество людей, знающих русский, А - множество людей, знающих английский.
Нужно построить алгоритм, на каждом шаге которого мы выбираем некоторое кол-во людей из уменьшаемого множества всех переводчиков и добавляем их в новое множество, в результате чего $\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.

 Профиль  
                  
 
 Re: Крупная конференция переводчиков
Сообщение10.12.2016, 23:22 
Заслуженный участник


27/04/09
28128

(Формулы)

Чем $\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.$$

 Профиль  
                  
 
 Re: Крупная конференция переводчиков
Сообщение10.12.2016, 23:30 
Заслуженный участник


26/06/07
1929
Tel-aviv

(Оффтоп)

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

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

It must be $\bigcap\limits_{i\in I} B_i$ :wink: :-)

 Профиль  
                  
 
 Re: Крупная конференция переводчиков
Сообщение10.12.2016, 23:49 
Заслуженный участник


27/04/09
28128

(Оффтоп)

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

 Профиль  
                  
 
 Re: Крупная конференция переводчиков
Сообщение11.12.2016, 02:02 
Заслуженный участник


12/09/10
1547
melnikoff в сообщении #1175786 писал(а):
Тогда выбираем одного человека из $K\cap P$ и одного человека из $A$, и переносим их в новое множество. Тем самым $\rho$ увеличивается до $|K\cap P\cap A| + 1$.

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

 Профиль  
                  
 
 Re: Крупная конференция переводчиков
Сообщение11.12.2016, 09:37 


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

 Профиль  
                  
 
 Re: Крупная конференция переводчиков
Сообщение11.12.2016, 09:51 
Заслуженный участник


12/09/10
1547
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$

 Профиль  
                  
 
 Re: Крупная конференция переводчиков
Сообщение11.12.2016, 10:14 


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

 Профиль  
                  
 
 Re: Крупная конференция переводчиков
Сообщение11.12.2016, 14:01 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Крупная конференция переводчиков
Сообщение12.12.2016, 16:13 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Крупная конференция переводчиков
Сообщение12.12.2016, 17:37 


01/11/16
4
Cash в сообщении #1175830 писал(а):
melnikoff в сообщении #1175786 писал(а):
Тогда выбираем одного человека из $K\cap P$ и одного человека из $A$, и переносим их в новое множество. Тем самым $\rho$ увеличивается до $|K\cap P\cap A| + 1$.

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

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

 Профиль  
                  
 
 Re: Крупная конференция переводчиков
Сообщение14.12.2016, 16:15 


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 13 ] 

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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