Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/1999/01/17.pdf Дата изменения: Fri Dec 23 19:25:00 2005 Дата индексирования: Tue Oct 2 00:11:46 2012 Кодировка: Windows-1251

ЗАДАЧНИК 'КВАНТА'

Теперь докажем непосредственно утверждение задачи. После первого раскулачивания у всех, кроме раскулаченного, число овец делится на 2, общее число овец тоже делится на 2, значит, и остаток у раскулаченного тоже делится на 2. Аналогично, после второго раскулачивания у каждого число овец делится на 4, ..., после седьмого 7 на 2 = 128. Это значит, что у одного из крестьян 128 овец, а у остальных по 0 овец, что и требовалось доказать. А.Шаповалов

М1647. Докажите, что из любого конечного множества

точек на плоскости можно так удалить одну точку, что оставшееся множество можно разбить на два множества, диаметры которых меньше диаметра первоначального множества. (Диаметр это максимальное расстояние между точками множества.)

Пусть А и Влюбые две точки данного множества М, расстояние между которыми равно диаметру d этого множества. Тогда A из определения K диаметра следует, что если Р М, то Р лежит внутd C D ри или на границе d 'линзы', образоd ванной пересечеL нием кругов раB диуса d с центрами А и В (см. рисунок) Докажем, что на одной из дуг AKC и BLD нет точек множества М, т.е. что если K A, L В, то KL > d. Действительно, если BAK = , LAK = , то > и из теоремы косинусов получаем

KL = AK + d - 2AK d cos > d , K
так как AK = 2d cos > 2d cos . Пусть, например, на дуге АС нет точек множества М за исключением точки А. Тогда, выбросив точку А и разделив оставшееся множество точек на части по прямой АВ, получим искомое разбиение, добавив точки прямой АВ к левой части. Легко видеть, что в каждой из двух полученных таким образом частей нет точек на расстоянии d. В.Дольников Каждый участник знает три языка из пяти, официально принятых на конференции. Докажите, что всех участников можно разбить на три группы по 100 человек так, чтобы для каждой группы нашелся язык, общий для ее членов. Каждый человек не владеет ровно двумя языками. Изобразим языки точками вершинами графа, а пары языков отрезками ребрами графа. На каждом ребре напишем, сколько человек не владеют соответствующими двумя языками. Сумма всех написанных чисел равна 300. Если участники конференции распределены требуемым в задаче образом на три группы, то выполнены два усло1Решение задачи М1648 приведено в заметке 'Гауссовы суммы'.
5 Квант ?1

2

2

2

2

М1649 . На конференцию приехали 300 участников.

вия. Во-первых, на соединяющих эти языки ребрах написаны числа, не превосходящие 100 (поскольку люди, не владеющие двумя из трех рассматриваемых языков, должны войти в третью группу). Во-вторых, количество людей, не владеющих некоторым языком, это сумма чисел, написанных на четырех ребрах, выходящих из соответствующей вершины. Значит, такая сумма не должна превосходить числа 200 (иначе этим языком будут владеть менее 100 человек). План решения таков: мы докажем существование трех языков, удовлетворяющих двум последним условиям, и докажем затем, что эти условия не только необходимы, но и достаточны. Назовем вершину плохой, если сумма чисел, написанных на выходящих из нее ребрах, больше 200. Назовем ребро плохим, если написанное на нем число больше 100. Если бы нашлись три плохие вершины, то мы сложили бы три соответствующие суммы и получили число больше 600, что противоречило бы условию задачи. Значит, в графе не более двух плохих вершин. Если в графе есть хотя бы одна плохая вершина, то все плохие ребра выходят из нее (иначе сумма чисел на плохом ребре и на ребрах, выходящих из плохой вершины, была бы больше 300). Следовательно, если в графе есть плохая вершина, то все неплохие его вершины (их число, как мы уже говорили, не меньше 3) соединены между собой неплохими ребрами. Если же в графе нет ни одной плохой вершины, то мы воспользуемся тем, что количество плохих ребер не превосходит двух и потому найдется треугольник из неплохих ребер (убедитесь в этом!). Доказательство достаточности состоит в том, что если языки A, B, C удовлетворяют условиям, то мы будем по очереди распределять людей в три группы так, чтобы в одной все говорили на языке A, в другой на языке B, в третьей на C. На каждом этапе будем рисовать ориентированный граф, вершины которого наши три группы и очередной человек X, которого мы должны куда-то поместить. От X стрелки проведем во все вершины, соответствующие группам, на языке которых X говорит. Из одного из языков A, B, C к другому проведем стрелку, если в соответствующей этому языку группе есть человек, владеющий языком другой группы. Мы хотим поместить X в одну из трех групп. Очевидно, X знает хотя бы один из языков A, B, C. Для определенности, пусть X знает язык группы A. Если группа A не заполнена до конца, то поместим X в нее, если нет, но из группы A можно пройти по стрелке в незаполненную группу B, то поместим X в группу A и одного человека из группы A переместим в группу B. Рассуждая в таком духе, можно понять, что мы можем легко разместить очередного человека во всех случаях, кроме того, когда все группы, в которые можно от него дойти, двигаясь по стрелкам, уже заполнены. Этих заполненных групп одна или две. Если одна, то X и все люди группы A не знают языков B и C. Тогда парой языков B и C владеет менее 200 человек, что противоречит условию. Если же доступных групп две, то X и все люди этих двух групп не говорят на третьем языке, так что третьим языком владеет недопустимо малое число участников конференции. А.Берзиньш, А.Спивак, Г.Челноков

%