358
471
всего разделов:
активных пользователей:
30 мартра 2005
Форумы снова функционируют.
21 декабря 2004
Видимо в связи с обнаруженными дырами в phpBB, форум был взломан, а через него взломано и всё остальное содержимое ceemat.ru. Всё кроме форума восстановлено, ведется дискуссия по поводу его сохранения.
Приносим извинения за неудобства.
29 сентября 2004
Форум обновился до версии 2.0.10
15 мая 2004
Новый раздел: "Программирование"
16 апреля 2004 года
Задачи Ярославского турнира математических боев — 124 задачи с решениями.
29 марта 2004
Таллинская викторина: занимательные вопросы и задачи для увлеченных химией.
Вариант боев 4 (10)
Задачи 32-39 составили боле сложный вариант, задачи 32, 33, 35, 37-41 составили менее сложный вариант
На турнир съехалось 105 школьников. Оказалось, что среди любых пятнадцати есть школьники, знакомые между собой. Кроме того, любые два школьника, имеющие одинаковое количество знакомых среди участников турнира — не знакомы между собой, а имеющие разное количество знакомых — знакомы между собой. Докажите, что среди участников найдется школьник, знакомый со всеми остальными. |
Решение. Разобьем всех школьников на несколько групп, объединив в одну группу всех тех,
кто имеет равное число знакомых среди участников олимпиады. Тогда никакие два школьника из одной
группы не знакомы между собой, а любые два из разных групп — знакомы. Заметим, что в разных
группах могут быть только разные количества школьников. Действительно, если бы было, например, по
n школьников, то у каждого школьника из обеих групп было бы равное число знакомых среди
участников олимпиады — (105 – n), и, следовательно, все они должны находиться
в одной группе. Кроме того, в одной группе может находиться не более 14 школьников, иначе бы не
выполнялось условие задачи о том, что среди любых 15 школьников можно найти двух знакомых между
собой. Достаточно доказать, что существует группа, состоящая из одного школьника. А это действительно
так. Иначе учитывая данные, полученные выше, в олимпиаде участвовало бы не более
|
Автор задачи — В.Каскевич |
11 Ноября 2003 17:55 Раздел каталога :: Ссылка на задачу
|