2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4
 
 
Сообщение29.07.2007, 22:58 
Заслуженный участник


05/09/05
515
Украина, Киев
dm писал(а):
http://www.imo2007.edu.vn/index.php?module=ViewNew.....p;NewId=11 (Regulations of the IMO 2007, 5.8)


Ага, понятно. :)

 Профиль  
                  
 
 
Сообщение02.09.2007, 14:19 
Аватара пользователя


08/06/07
52
Киев
torbich писал(а):
Не внука, сына.

Если имеется в виду Даниил Радченко - то он не является ближним родственником Вадиму Николаевичу. :) Рассказывали, что Вадим Николаевич был очень ошарашен "искренними поздравлениями" с успехом его сына, хотя последний и на Межнар-то ещё не ездил.

 Профиль  
                  
 
 
Сообщение02.09.2007, 14:50 
Экс-админ
Аватара пользователя


23/05/05
2106
Kyiv, Ukraine
Sasha Rybak писал(а):
Если имеется в виду Даниил Радченко

Речь, конечно, не о нем. 8-)

 Профиль  
                  
 
 Solution of problem 3
Сообщение02.09.2007, 15:25 
Аватара пользователя


08/06/07
52
Киев
Даю мастер-класс по комбинаторике.

Решение задачи 3.

Пусть k - наибольшее число, для которого есть две НЕПЕРЕСЕКАЮЩИЕСЯ компании размера k. Следовательно, нет компании размера 2k+2 (иначе её можно было бы разбить на две компании размера k+1), а значит - нет и большей компании. А тогда нет и компании размера 2k+1, иначе размер максимальной компании был бы нечётным.
Пусть K_1 и K_2 - непересекающиеся компании размера k.

Разместим K_1 в одну комнату, а остальных - в другую. Если во второй комнате (а там есть K_2) нет компании размера k+1, то всё классно.

Если во второй комнате есть компания размера k+1 (назовём её L), то оставим L во второй комнате, а остальных перебросим в первую. Пока что в первой комнате есть компания из k человек (K_1) и, по выбору k, нет большей. Рассмотрим некоторого человека u в компании L. Если при его перебрасывании в первую комнату в ней не появляется компания размера k+1, то всё отлично.

Пусть такая компания появляется. Сначала рассмотрим случай, когда такая компания одна. Назовём её M_1. Тогда M_1\{u} - это компания размера k. В M_1\{u} найдётся чувак v, который не дружит со всеми участниками из L\{u}. [В противном случае L+(M_1\{u}) - это компания размера 2k+1 ("+" означает объединение).] Тогда пусть во второй комнате будут L\{u} и v, а в первой - все остальные. Всё супер.

И наконец, пусть при переводе u из второй комнаты (где была только компания L) в первую комнату, там появляется НЕСКОЛЬКО компаний размера k+1 - назовём их M_1, M_2, ..., M_n. Причём пусть M_1 и M_2 - это такие компании, пересечение которых - НАИБОЛЬШЕЕ среди всех возможных пересечений M_i и M_j (i<j). Тогда никакая другая M_i (i>2) не содержится в M_1+M_2 (+ означает объединение). [Иначе M_i должна была бы покрывать (M_1\M_2)+(M_2\M_1), а тогда (M_1\M_2)+(M_2\M_1) - компания, а значит и M1+M2 - компания, причём размера больше k+1. Тогда, выдёргивая u обратно к L, получаем, что есть две непересекающиеся компании размера k+1: L и некоторое подмножество (M_1+M_2)\{u} - возможно, сама (M_1+M_2)\{u}.]
Значит, в каждой M_i (i>2) можно выбрать человека v_i, который не принадлежит M_1+M_2 (все v_i не обязаны быть различными). Перебрасывая v_3, ..., v_n во вторую комнату (к L\{u}), мы НЕ ПОЛУЧИМ компании размера k+1 во второй комнате (так как таковые есть в первой - M_1 и M_2). Рассмотрим некоторых людей v_1 из M_1\M_2 и v_2 из M_2\M_1, которые НЕ ДРУЖАТ. Они найдутся, поскольку M_1+M_2 - не компания. Заметим, что (L\{u})+{v_1, v_3, ..., v_n} не содержит компании размера k+1, поскольку существует не пересекающаяся с этим множеством (k+1)-компания M_2. Аналогично и (L\{u})+{v_2, v_3, ..., v_n} не содержит компании размера k+1. Но тогда в (L\{u})+{v_1, v_2, v_3, ..., v_n} может быть только (k+1)-компания, содержащая и v_1, и v_2. Но такой компании нет, поскольку v_1 и v_2 не дружат. :)
Итак, в (L\{u})+{v_1, v_2, v_3, ..., v_n} (вторая комната) нет компании размера k+1, но есть k-компания L\{u}. В первой комнате мы уничтожили все компании размера k+1 (которые суть M_1, M_2, ..., M_n). Компания из k человек осталась - например, M_1\{v_1}. Ура-а-ааа!!!!

 Профиль  
                  
 
 Re: Solution of problem 3
Сообщение04.09.2007, 16:27 


25/06/07
124
Новосибирск
Sasha Rybak писал(а):
Даю мастер-класс по комбинаторике.
Тогда никакая другая M_i (i>2) не содержится в M_1+M_2 (+ означает объединение). [Иначе M_i должна была бы покрывать (M_1\M_2)+(M_2\M_1)

Почему так-то? Почему не может М_3, скажем, состоять из некоторых, но не всех элементов, принадлежащих М_1/М_2 и из некоторых, но не всех элементов, принадлежащих М_2/М_1?

 Профиль  
                  
 
 Re: Solution of problem 3
Сообщение05.09.2007, 22:39 
Аватара пользователя


08/06/07
52
Киев
lexus c. писал(а):
Почему так-то? Почему не может М_3, скажем, состоять из некоторых, но не всех элементов, принадлежащих М_1\М_2 и из некоторых, но не всех элементов, принадлежащих М_2\М_1?


M_1 и M_2 выбраны так, что они имеют НАИБОЛЬШЕЕ ПЕРЕСЕЧЕНИЕ. Из этого получаем нужное следствие. Это не так уж очевидно, но доказывается несложно. :)

 Профиль  
                  
 
 Re: Solution of problem 3
Сообщение06.09.2007, 02:06 


25/06/07
124
Новосибирск
Sasha Rybak писал(а):
lexus c. писал(а):
Почему так-то? Почему не может М_3, скажем, состоять из некоторых, но не всех элементов, принадлежащих М_1\М_2 и из некоторых, но не всех элементов, принадлежащих М_2\М_1?


M_1 и M_2 выбраны так, что они имеют НАИБОЛЬШЕЕ ПЕРЕСЕЧЕНИЕ. Из этого получаем нужное следствие. Это не так уж очевидно, но доказывается несложно. :)

А можно привести это доказательство, если не сложно? )))

 Профиль  
                  
 
 Re: Solution of problem 3
Сообщение06.09.2007, 21:16 
Аватара пользователя


08/06/07
52
Киев
lexus c. писал(а):
А можно привести это доказательство, если не сложно? )))

Да не вопрос.
Напоминаю, что рассматриваются множества одного и того же размера - k+1. Пусть N - это пересечение множеств M_1 и M_2. Пусть |M_1\M_2|=|M_2\M_1|=a. Тогда |N|=k+1-a.
Предположим, что M_3 содержится в M_1+M_2. Пусть x элементов множества M_3 лежат в M_1\M_2 и y элементов множества M_3 лежат в M_2\M_1. Тогда в N лежит k+1-x-y элементов множества M_3. M_3 пересекается с M_1 по x+(k+1-x-y)=k+1-y элементам, а с M_2 - по y+(k+1-x-y)=k+1-x элементам. По выбору M_1 и M_2: k+1-y<=|N|=k+1-a и k+1-x<=|N|=k+1-a. Поэтому x>=a и y>=a. С другой стороны, x<=|M_1\M_2|=a и y<=|M_2\M_1|=a. То есть, x=y=a.
Значит, M_3 покрывает |M_1\M_2| и |M_2\M_1|.

 Профиль  
                  
 
 Re: Solution of problem 3
Сообщение06.09.2007, 22:40 


25/06/07
124
Новосибирск
Sasha Rybak писал(а):
lexus c. писал(а):
А можно привести это доказательство, если не сложно? )))

Да не вопрос.
Напоминаю, что рассматриваются множества одного и того же размера - k+1. Пусть N - это пересечение множеств M_1 и M_2. Пусть |M_1\M_2|=|M_2\M_1|=a. Тогда |N|=k+1-a.
Предположим, что M_3 содержится в M_1+M_2. Пусть x элементов множества M_3 лежат в M_1\M_2 и y элементов множества M_3 лежат в M_2\M_1. Тогда в N лежит k+1-x-y элементов множества M_3. M_3 пересекается с M_1 по x+(k+1-x-y)=k+1-y элементам, а с M_2 - по y+(k+1-x-y)=k+1-x элементам. По выбору M_1 и M_2: k+1-y<=|N|=k+1-a и k+1-x<=|N|=k+1-a. Поэтому x>=a и y>=a. С другой стороны, x<=|M_1\M_2|=a и y<=|M_2\M_1|=a. То есть, x=y=a.
Значит, M_3 покрывает |M_1\M_2| и |M_2\M_1|.

Понятно, спасибо большое )

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 54 ]  На страницу Пред.  1, 2, 3, 4

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



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

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


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

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