Квант 2019, №4 · Страницы

4

КВАНТ 2019/№4

составители задач в большинстве случаев дают для расчетов мало-мальски реальные величины и ждут в качестве ответа такие же. Задачи типа такой: «К батарейке от карманного фонарика, на которой написано 4,5 вольта, подсоединили лампочку, сопротивление которой при измерении оказалось 2 ома. Какой ток будет течь?» дают все-таки редко. Поэтому в задаче, в которой надо было определить энергию электрона при фотоэмиссии, а потом рассчитать длину его пробега в заданном тормозящем поле, школьники, получившие ответы типа 2,2 ◊ $10^{-} 40$ м; 5,9 ◊ $10^{-} 36$ м; 1,4 ◊ $10^{-} 22$ м; 8,7 ◊ $10^{-} 16$ м; 1,2 ◊ $10^{-} 11$ м; 2,7 ◊ $10^{7}$ м; 2,3 ◊ $10^{27}$ м, должны были насторожиться. Потому что предпоследний ответ – это два диаметра Земли, а про малые расстояния вы в этой статье уже прочитали. Кстати, один из получивших фантастический ответ, насторожился – у последнего ответа стоял знак «?». Ответ, превышающий размер Вселенной (в одном из современных пониманий), все-таки вызвал сомнение. Или такой пример – персонаж получил мощность от батарейки 4 ◊ $10^{-} 19$ Вт. Для обычной батарейки это соответствует току 2,5 ◊ $10^{-} 19 A$, т.е. полтора электрона в секунду! В среднем, в среднем… Да просто по воздуху потечет больший на порядки ток – и подсоединять к ней ничего не надо. Вот еще одна прелестная задача, в которой сделали некорректность изготовители и делали ошибку многие потребители. Дан объем, в него помещают $сколько-то^{210} Po$, который с таким-то периодом полураспада испускает D -частицы и превращается в Pb. Каким будет давление в объеме через некоторое время? Существенная часть правильно вычисляла, сколько атомов Po распадется и сколько атомов Pb получится, а потом определяла давление по универсальному газовому закону. Уже хорошо… Но вообще-то задача некорректна – D -частицы вылетают из образца в объем только из 10-микронного приповерхностного слоя (да и то не все), т.е. большинство вообще не вылетит. Кстати, частицы эти – не совсем атомы гелия, но «не будем о

страшном на ночь», как говорит один мой знакомый физик. Что делать на реальном экзамене – не вообще, а в аспекте этой статьи? Посмотреть на ответ и подумать, не противоречит ли он чему-то, известному из школы, например не получили ли вы энергию излучения меньше hQ или заряд меньше трети заряда электрона е (по модулю, по модулю!). Кроме того, полезно посмотреть просто на условие задачи. Школьник, который решал задачу о плавании объекта на границе двух жидкостей, плотности которых 900 кг $м^{3}$ и 2700 кг $м^{3}$, и получил ответ для плотности объекта 100 кг $м^{3}$, зря этого не сделал. В качестве печального анекдота можно добавить, что сотни школьников радостно писали, что это масло и алюминий, хотя в задаче это не спрашивалось. Зачем было демонстрировать ужасающую абстрактность своего мышления? Далее, внутри задачи часто приходится, как это ни странно, складывать. Получив в качестве промежуточного результата нечто вроде 0,515 ◊ $10^{15} + 2,75$, стоит насторожиться. Равно как и получив в качестве ответа на вопрос «во сколько раз» ответы «в 1,2 ◊ $10^{18}$ раза» или «в 0,4 ◊ $10^{26}$ раз». Если задачу составлял минимально разумный человек, такого не будет – складывать и вычитать в школе имеет смысл сравнимые величины (хотя бы из-за того, что разрешено пользоваться калькуляторами). Заметим, что в серьезной физике (и школьникам стоило бы это объяснять) ситуация сложнее – бывает, что сильно различающиеся величины приходится складывать. А чаще их приходится сравнивать – для выбора модели, для обоснования того, что мы учитываем, а чем в данном случае пока пренебрегаем. Итак, численные оценки имеют большое значение в физике – причем еще задолго до получения ответа! Они позволяют построить модель и определить направление ее развития. Это – одна из причин важности численных оценок для физики. Для остальных людей они важны еще и потому, что в некоторых случаях предохраняют от (Продолжение см. на с. 13)

(

)

Мудрецы, колпаки и арифметика конечных полей

С.ГРИБОК

Испытание 1. Два из трех. О двоичных наборах, кубах и шарах

Давным-давно правил в Персии царь Шахрияр. Целыми днями царь пировал, охотился и развлекался, устраивая жестокие испытания для своих придворных. В то время как царь проводил время в праздности, решением всех запутанных государственных дел и управлением страной занимался совет придворных мудрецов. Однажды царь решил проверить, так ли уж умны его придворные мудрецы. Он приказал позвать трех мудрецов и объявил условия испытания, которое ожидает их завтра. Каждому мудрецу на голову наденут колпак белого или черного цвета. Каждый сможет видеть чужие колпаки, но не будет знать, какого цвета его колпак. Какой именно колпак надеть на каждого мудреца, решит палач, трижды подбросив монету, одна сторона которой окрашена в белый цвет, а другая – в черный. Затем каждому мудрецу дадут перо и лист пергамента, на котором он напишет, какого цвета его колпак. Если хотя бы двое мудрецов ответят правильно, всех наградят, если же хотя бы двое ошибутся, всех мудрецов казнят. Подавать друг другу какие-либо знаки во время испытания запрещено. За ночь перед испытанием у мудрецов есть возможность договориться и выработать единую стратегию. Как следует действовать мудрецам, чтобы максимизировать шансы остаться в живых? Докажем, что не существует способа, позволяющего сделать вероятность выигрыша мудрецов больше чем 3 4.

DOI: https://doi.org/10.4213/kvant20190402

Пусть испытание повторяется много раз. Пусть мудрецам удалось разработать метод, позволяющий двум мудрецам из трех угадывать цвета своих колпаков в среднем чаще, чем в трех играх из четырех. Таким образом, из 12 ответов мудрецов, прозвучавших в течение четырех игр, в среднем более 6 ответов будут верными ( 6 3 ˜ 2 ). Но это невозможно, так как каждый мудрец угадывает цвет своего колпака в одном случае из двух, а значит, из 12 ответов в среднем ровно 6 ответов верны. Всего есть 8 различных вариантов распределения колпаков между тремя мудрецами. Вероятность выигрыша 3 4 означает, что мудрецы побеждают в шести вариантах, а проигрывают в двух вариантах из восьми. Попробуем построить такую стратегию мудрецов, которая позволит им выигрывать в шести случаях из восьми. Для удобства записи наборов колпаков будем использовать цифру 0 для обозначения белого колпака, а цифру 1 для обозначения черного колпака. Например, запись 001 будет означать, что первым двум мудрецам достались белые колпаки, а третий мудрец получил черный колпак. Выберем два «смертельных» набора колпаков, которые мудрецы не смогут угадать. Например, пусть смертельными будут наборы 000 и 111. Мы хотим, чтобы на всех остальных наборах мудрецы смогли выиграть. Как этого добиться? Прежде всего заметим, что для любого не смертельного набора колпаков один из мудрецов видит на соседях колпаки одного и того же цвета. Стратегия этого мудреца ясна: если видишь на соседях два колпака одного цвета, называй другой цвет. Оче-

6

КВАНТ 2019/№4

видно, для любого не смертельного набора эта стратегия работает и гарантированно позволит мудрецу угадать цвет своего колпака. Займемся оставшимися двумя мудрецами, каждый из которых видит на соседях колпаки разных цветов. Чтобы выиграть, достаточно, чтобы хотя бы один из этих мудрецов назвал цвет своего колпака правильно. Заметим также, что их собственные колпаки одного и того же цвета. Значит, если один из мудрецов назовет белый цвет, а другой – черный, то один обязательно угадает. Но как мудрецы узнают, какой цвет называть, если они оба видят одну и ту же картину – на соседях колпаки разных цветов? Дело в том, что если присмотреться внимательнее, мы заметим: в том, что видят эти два мудреца, есть некоторые различия. Пусть, например, мудрецы встали в круг. Тогда один из двух мудрецов видит слева белый колпак, а справа – черный. Другой мудрец видит иную картину: слева черный колпак, а справа – белый. Теперь легко придумать правило, которое позволит одному из этих мудрецов угадать цвет своего колпака: если видишь на соседях колпаки разных цветов, называй тот цвет, который видишь справа (заметим, что также годится и «зеркально-симметричное» правило: если видишь на соседях колпаки разных цветов, то называй тот цвет, который видишь слева). Итак, задача решена, но не будем торопиться. Во-первых, подумаем, нельзя ли упростить правила, которым должны следовать мудрецы. Нетрудно догадаться, что два найденных нами правила можно переформулировать в виде одного простого правила: называй НЕ тот цвет, который видишь на соседе слева. Во-вторых, построим геометрическую интерпретацию задачи о трех колпаках. Удобно представить множество вариантов распределения колпаков в виде куба (рис.1). Каждый набор колпаков соответствует одной из вершин куба. Если два набора колпаков отличаются лишь цветом одного колпака (такие наборы называются

Рис. 1

соседними), они расположены в вершинах, соединенных ребром. Достроим теперь два шара, центры которых находятся в смертельных точках 000 и 111, а радиусы равны ребру куба. Каждый шар покрывает четыре точки куба. Каждая точка куба либо находится на поверхности, либо в центре одного из шаров. В таких случаях говорят, что построено «покрытие куба непересекающимися шарами». Если точка оказалась в центре шара, мудрецы не угадают цвета своих колпаков, если же точка лежит на поверхности шара, большинство мудрецов назовут свои цвета правильно.

Испытание 2. Четыре из семи. О многочленах и кодовых множествах

На следующий день к царю привели семерых мудрецов. Правитель объявил, что сегодня состоится еще одно испытание. Правила те же, что и вчера: каждому мудрецу на голову наденут колпак белого либо черного цвета, после чего каждый мудрец должен записать, какого цвета по его мнению колпак на его голове. Если хотя бы четверо мудрецов ответят правильно, всех наградят, если же хотя бы четверо ошибутся, всех казнят. Как следует действовать мудрецам, чтобы и на этот раз свести вероятность казни к минимуму? Опять начнем с нижней оценки вероятности казни. Докажем, что не существует

7

МУДРЕЦЫ,

КОЛПАКИ

И

АРИФМЕТИКА

способа, позволяющего сделать вероятность выигрыша больше чем 7 8. Доказательство такое же, как и в первой задаче, с точностью до замены чисел. Пусть мудрецам удалось разработать метод, позволяющий четырем мудрецам из семи угадывать цвета своих колпаков в среднем чаще, чем в семи играх из восьми. Таким образом, из 56 ответов мудрецов, прозвучавших в течение восьми игр, в среднем более 28 ответов будут верными ( 28 7 ˜ 4 ). Но это невозможно, так как каждый мудрец угадывает цвет своего колпака в одном случае из двух, а значит, из 56 ответов в среднем ровно 28 ответов верны. Всего есть 128 различных вариантов распределения колпаков между семью мудрецами. Вероятность выигрыша 7 8 означает, что мудрецы побеждают в 112 вариантах, а проигрывают в 16 вариантах из 128. По аналогии с первой задачей теперь надо как-то выбрать 16 смертельных наборов. Но как это сделать? В предыдущей задаче все наборы из трех колпаков мы расставили по вершинам куба. Теперь колпаков семь, а значит, множество наборов соответствует вершинам семимерного гиперкуба. Представить эту фигуру сложно, однако это не мешает нам порассуждать о ее свойствах. Заметим, что так как мудрецов семеро, то для каждого набора колпаков существует семь соседних наборов, следовательно, каждый 7-мерный шар единичного радиуса с центром в вершине N-мерного куба покрывает ровно 8 точек куба. Поскольку 128 16 ˜ 8, то теоретически для покрытия всех 128 вершин 7-мерного куба как раз должно хватить шестнадцати непересекающихся 7-мерных шаров, в центре каждого из которых мы поместим смертельный набор. Вот только как это сделать на практике? Будем называть расстоянием между двумя наборами число позиций, в которых эти наборы отличаются. Расстояние между соседними наборами равно единице. Теперь сформулируем свойства множества смертельных наборов, которое мы хотим построить.

КОНЕЧНЫХ

ПОЛЕЙ

1. Всего в множестве 16 наборов. 2) Расстояние между любыми двумя наборами не меньше трех (чтобы шары, в центрах которых находятся смертельные наборы, не пересекались). 3) Циклический сдвиг смертельного набора также является смертельным набором (иначе разным мудрецам придется использовать различные стратегии). Интуитивно ясно, что смертельные наборы должны быть равномерно распределены на множестве всех возможных наборов. Можно попробовать представить каждый набор колпаков как двоичную запись некоторого целого числа от 0 до 127, а множество смертельных наборов – как элементы некоторой арифметической прогрессии, однако традиционные арифметические операции плохо подходят для обеспечения нужных нам свойств 2 и 3. Так как традиционная арифметика нам не подходит, воспользуемся «нетрадиционной» арифметикой, а именно, так называемой арифметикой многочленов над полем {0,1}. Прежде всего определим операцию сложения двух наборов колпаков. Сумма двух наборов длины n – это набор длины n, каждый элемент которого равен сумме по модулю 2 соответствующих элементов исходных наборов. Напомним правила сложения по модулю 2: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0. Пример: 00110101 + 11110000 = 11000101. Чтобы определить операции умножения и деления наборов колпаков, удобно записывать наборы в виде многочленов. Набор колпаков $v_{0}, v_{1}, v_{2},^{…}, v n_{1}$ можно записать в виде многочлена от переменной $х:_{0}^{v} v_{1}$ ˜ $x_{2}^{v}$ ˜ $x^{2} …^{v} n_{1}$ ˜ $x^{n} 1$. Таким образом, множество наборов длины n эквивалентно множеству многочленов, степени которых не превышают n – 1. Теперь определим произведение двух наборов как набор, соответствующий мно-

23

«КВАНТ»

ДЛЯ

МЛАДШИХ

ШКОЛЬНИКОВ

Чем круг отличается от квадрата?

С.ВОЛЧЁНКОВ

СПЕРВОГО ВЗГЛЯДА ВОПРОС КАЖЕТ- ся странным. Каждый знает, и что такое круг, и что такое квадрат. И каждый знает, что это разные геометрические объекты. Но в этой статье речь пойдет не столько о геометрии, сколько о комбинаторной геометрии, где геометрические объекты рассматриваются с комбинаторной точки зрения – как элементы конечных множеств. Мы разберем три задачи, в которых круги и квадраты какими-то своими, на первый взгляд незначительными, различиями порождают различные ответы. Задача 1 про круги. На плоскости расположены 5 кругов, каждые два из которых имеют общую точку. Верно ли, что всегда найдутся 3 круга, имеющих общую точку? Ответ: верно. Решение. Обозначим круги (и их центры) буквами $O_{1}, O_{2}, O_{3}, O_{4}, O_{5}$ соответственно. Соединим центры друг с другом отрезками. Какие-то два из проведенных отрезков должны пересечься. Это известный факт (даже если точки пытаться соединять ломаными) – попробуйте доказать его самостоятельно или прочитайте в Приложении в конце статьи. Пусть отрезки $O_{1} O_{2}$ и $O_{3} O_{4}$ пересекаются в точке X (рис.1). Осталось доказать, что верна такая лемма.

Рис. 1

Лемма. Если есть две пары пересекающихся кругов (пара $O_{1}, O_{2}$ и пара $O_{3}, O_{4} ),$ причем отрезки, соединяющие их

DOI: https://doi.org/10.4213/kvant20190403

центры $( O_{1} O_{2}$ и $O_{3} O_{4} ),$ имеют общую точку (X), то какие-то три из этих четырех кругов имеют общую точку. Так как круги $O_{1}$ и $O_{2}$ пересекаются, на отрезке $O_{1} O_{2}$ есть точка F, принадлежащая им обоим. Аналогично, на отрезке $O_{3} O_{4}$ есть точка E, принадлежащая кругам $O_{3}$ и $O_{4}$. Пусть они расположены, как на рисунке 1, причем XE t XF (остальные случаи аналогичны). Тогда $O_{4} E t O_{4} X XF t O_{4} F$, т.е. точка F принадлежит кругам $O_{1}, O_{2}$ и $O_{4}$. Лемма доказана. Задача 1 про квадраты. На плоскости расположены 5 квадратов, каждые два из которых имеют общую точку. Верно ли, что всегда найдутся 3 квадрата, имеющих общую точку?

Рис. 2

Ответ: неверно. Контрпример изображен на рисунке 2. Задача 2 про круги. На плоскости расположены 3 красных и 3 синих круга, причем каждые два разноцветных круга имеют общую точку. Верно ли, что всегда найдутся два одноцветных круга, имеющих общую точку? Ответ: верно. Решение. Соединим центры разноцветных кругов друг с другом отрезками. Какие-то два из проведенных отрезков долж-

24

КВАН T 2019/№4

ны пересечься. Это тоже известный факт, часто называемый «три дома, три колодца» (докажите его самостоятельно или прочитайте в Приложении).Тогда, по лемме из задачи 1, какие-то три круга имеют общую точку. А среди этих трех найдутся два круга одного цвета, что и требовалось. Задача 2 про квадраты. На плоскости расположены 3 красных и 3 синих квадрата, причем каждые два разноцветных квадрата имеют общую точку. Верно ли, что всегда найдутся два одноцветных квадрата, имеющих общую точку? Ответ: неверно. Контрпример изображен на рисунке 3.

всегда можно разрезать на N выпуклых многоугольников, каждый из которых будет содержать ровно одну отмеченную точку? Ответ: верно. Решение. Разобьем точки многоугольника на области с номерами от 1 до N по такому правилу: область с номером k состоит из точек, более близких к точке k, чем к любой другой отмеченной точке (такое разбиение называется диаграммой Вороного). При таком разбиении область с номером k ограничена серединными перпендикулярами отрезков, проведенных из точки k к остальным отмеченным точкам, т.е. является выпуклым многоугольником. Пример такой диаграммы приведен на рисунке 4.

Рис. 4

Рис. 3

Замечание. В задачах 1 и 2 квадраты можно заменить на другие многоугольники, в частности на правильные N-угольники, где N сколь угодно велико. При этом многоугольники становятся почти неотличимыми от кругов. Правда, рисунки 2 и 3 пришлось бы рассматривать под микроскопом, чтобы увидеть на них все пересечения. Задача 3 про круги. В выпуклом многоугольнике расположены N непересекающихся кругов. Верно ли, что многоугольник всегда можно разрезать на N выпуклых многоугольников, каждый из которых будет содержать ровно один из кругов? Прежде чем переходить к решению этой задачи, рассмотрим более простую задачу. Задача 3 про точки. В выпуклом многоугольнике отмечены N точек (с номерами от 1 до N). Верно ли, что многоугольник

А теперь вернемся к задаче 3 про круги. Оказывается, что нужное нам разбиение многоугольника может быть образовано не серединными перпендикулярами, а так называемыми радикальными осями окружностей. Радикальная ось двух непересекающихся окружностей – это геометрическое место точек, касательные из которых, проведенные к двум данным окружностям, имеют равные длины. Нетрудно показать, что радикальная ось двух окружностей любых радиусов с несовпадающими центрами – это прямая (см. Приложение). Если окружности не пересекаются, они будут целиком по разные стороны от радикальной оси. Разобьем тогда точки многоугольника (лежащие снаружи окружностей) на области, состоящие из точек, касательные из которых к одной окружности короче, чем к другим. Аналогично получим, что каждая окружность лежит целиком в одной области и эта область – выпуклый многоугольник.

25

«КВАНТ»

ДЛЯ

МЛАДШИХ

Кстати, в случае «окружностей» нулевого радиуса касательные превращаются в расстояния до центров, и получается предыдущая задача. И последняя задача. Задача 3 про квадраты. В выпуклом многоугольнике расположены N непересекающихся квадратов. Верно ли, что многоугольник всегда можно разрезать на N выпуклых многоугольников, каждый из которых будет содержать ровно один из квадратов? Ответ: неверно. Контрпример изображен на рисунке 5.

ШКОЛЬНИКОВ

гональ будет внутри, другая – снаружи (рис. 6). В результате плоскость разделится на три «треугольника» и бесконечную

Рис. 6

Рис. 5

Пояснение. В пятиугольнике расположены три квадрата. Разрезать пятиугольник на три выпуклые части, каждая из которых содержит один квадрат, невозможно. Точка в центре рисунка не может принадлежать ни одной из частей, так как каждый из трех отрезков, идущих из нее к одной из точек квадратов, будет пересекать контур другого квадрата, т.е. ни один из этих отрезков не будет принадлежать выпуклой фигуре.

Приложение

Пять домов. Докажем, что на плоскости нельзя соединить друг с другом пять домов непересекающимися дорожками так, чтобы каждый дом был соединен с каждым отдельной дорожкой. Допустим, это все-таки удалось сделать. Уберем все дорожки и будем возвращать их последовательно. Сначала добавим четыре дорожки, соединяющие четыре дома по циклу, получится «четырехугольник» из дорожек. Соединим теперь пары противоположных вершин этого четырехугольника (проведем «диагонали»). Одна диа- часть, граница которой тоже будет треугольником (назовем эту часть «бесконечным» треугольником). Пятый дом окажется в одном из этих треугольников, и его можно будет соединить только с тремя вершинами этого треугольника. Противоречие – останется еще один дом, который нельзя соединить с пятым. Три дома и три колодца. Докажем, что на плоскости нельзя соединить непересекающимися дорожками три дома с тремя колодцами так, чтобы каждый дом был соединен с каждым колодцем отдельной дорожкой. Допустим, это все-таки удалось сделать. Уберем все дорожки и будем возвращать их последовательно. Сначала обойдем по замкнутому циклу все дома и колодцы. Так как дорожки не пересекаются, это будет «шестиугольник» из дорожек, причем дома и колодцы в нем чередуются (рис. 7). Осталось провести еще три дорожки, соединяющие противоположные вершины шестиугольника. Хотя бы две из

Рис. 8

27

ЛАБОРАТОРИЯ

«КВАНТА»

Раньше встречался припой в виде гораздо более толстых прутков, и с ними этот эксперимент получался еще эффектнее, только требовалось большее время. Приходилось крепить горизонтальный стержень в начале беседы или лекции и привлекать к нему внимание часа через полтора – металлический стержень чуть ли не в палец толщиной сгибался на пару сантиметров! Очень быстро сгибается под собственной тяжестью совсем тоненький прутик припоя, диаметром около миллиметра. Длина в этом варианте, разумеется, может быть совсем небольшой, примерно 10–15 см. Если под руками есть пруток припоя средней толщины и длиной сантиметров тридцать, то пластичность металла можно проиллюстрировать совсем просто и быстро – достаточно подвесить пруток на нитке за середину или вставить в самую примитив-

Призма ABCD, вделанная в стену; на свободный ее конец действует груз (гравюра из «Бесед» Галилея)

Прекрасная гравюра, воспроизведенная в «Беседах» Галилея, показывает довольно толстую балку, закрепленную одним концом в каменной стенке, тогда как на другой конец действует своей тяжестью некий груз. Между прочим, Галилей написал эту свою последнюю книгу во многом потому, что этой темой ему дозволяли заниматься надзиратели от инквизиции, а он к этому времени совсем осиротел и ослеп. Так что вполне вероятно, сам Галилей этой гравюры и не видел. Сегодня можно изменить этот опыт и показывать студентам и школьникам его простой и эффектный вариант. Для этого берется горизонтальная палочка свинцового припоя для пайки и закрепляется за один конец. Если палочка тонкая, диаметром немного меньше трех миллиметров, а длиной примерно 20–30 см, то она сама собой изгибается под своей тяжестью. Не нужен никакой дополнительный груз, чтобы за четверть часа свободный конец палочки опустился на несколько сантиметров. Это производит большое впечатление на зрителей. Мы просто своими глазами наблюдаем пластическую деформацию металла.

Палочка свинцового припоя в начале эксперимента…

…и в конце эксперимента ную пластинку с отверстием. Через несколько минут будет четко видно, как опустились оба конца прутика. Члены кружка юных техников легко могли бы дополнить эту простейшую экспериментальную установку, скажем, электрическим звонком, или регулятором длины свободной части висящего стержня для сравнения времени деформации.

МАТЕМАТИ Ч ЕСКИ Й КРУ Ж ОК

Где спрятался Ним?

И.КОПЫЛОВ

ВСТАТЬЕ «ПЛЮСЫ–МИНУСЫ И ИГРА НИМ»

(см. «Квант» №7, 8 за 2018 г.) была рассказана стратегия игры Ним, которая играет особую роль в теории игр. Игра Ним состоит в следующем. Имеется m кучек, количество камней в которых равно $a_{1}, a_{2}$, … $, a_{m}$. Двое ходят по очереди; каждый игрок при своем ходе выбирает одну из кучек и берет из нее любое ненулевое число камней. Побеждает тот, кто забрал последний камень. Многие игры сводятся к Ниму. Если в игре удается распознать Ним, то для нее сразу же появляется стратегия, заимствованная из Нима. В данной статье сведем к Ниму несколько разнообразных игр. Игра 1. Пять фишек находятся на клетках горизонтальной полоски из 25 клеток. За каждый ход необходимо передвинуть одну из фишек влево на любую клетку, перепрыгивать через другие фишки разрешается, на одной клетке могут находиться несколько фишек. Выигрывает игрок, после хода которого все 5 фишек окажутся на крайней левой клетке полоски. Игра очевидным образом сводится к Ниму с 5 кучками камней. Занумеруем клетки полоски, начиная с 0, слева направо (рис.1). Тогда фишку, стоящую на клетке с номером n, за 1 ход можно передвинуть на любую из клеток 0, 1, …, n 1 вне зависимости от расположения остальных фишек. Аналогично и в игре Ним количество камней в одной из кучек за ход уменьшается вплоть до 0. Поэтому для сведения к Ниму фишку на клетке n следует заменить кучкой с n камнями. Тогда фишка на самой левой клетке

равносильна пустой кучке. Игра заканчивается, когда все кучки пусты, т.е. все фишки собраны на клетке с номером 0. Итак, если 5 фишек расположены на клетках с номерами a, b, c, d и e, то для чисел a, b, c, d и e составляется Ним-сумма. Напомним, что Ним-сумма вычисляется поразрядно следующим образом: Ним-суммируемые числа записываются в двоичной системе исчисления, и если в данном разряде оказалось нечетное число единиц, то в результирующей сумме в соответствующем разряде ставим 1, если четное – 0. Ним-сумма чисел а, b, с, d, е обозначается a † b † c † d † e. Своим ходом игрок должен обнулить Нимсумму. Рассмотрим пример. Пусть фишки стоят на клетках 5, 10, 14, 16 и 22 полоски (см. рис.1). Вычисление соответствующей Нимсуммы приведено на рисунке 2.

Рис. 2. Вычисление Ним-суммы для определения хода в игре 1

Итак,

5 † 10 † 14 † 16 † 22

$= 101_{2}$ † $1010_{2}$ † $1110_{2}$ † $10000_{2}$ † $10110_{2} 111_{2} 7$.

Ним-сумма отлична от 0. Игрок, делающий ход, должен ее обнулить. Старшая единица в Ним-сумме находится во 2-м двоичном разряде, если считать разряды справа налево, начиная с нулевого. Единицы во втором разряде присутствуют в записи количеств камней в 1, 3 и 5 кучках. Поэтому в рассматриваемом примере у игрока есть 3 варианта хода: либо в первой кучке оставить $10_{2} 2$ камня, т. е. передвинуть фишку с

Рис. 1. Нумерация клеток полоски и расположение фишек в примере

DOI: https://doi.org/10.4213/kvant20190405

(Продолжение см. на с. 34)

34

КВАНТ 2019/№4

клетки 5 на клетку 2, либо в третьей кучке оставить $1001_{2} 9$ камней, т. е. передвинуть фишку с клетки 14 на клетку 9, либо в пятой кучке оставить $10001_{2} 17$ камней, что означает перестановку фишки с клетки 22 на клетку $17. Игра^{2.}$ Гусеница состоит из 20 звеньев. Некоторые звенья гусеницы окрашены в зеленый цвет, остальные – белые. Два игрока по очереди перекрашивают звенья: зеленое звено делают белым, а белое – зеленым. Своим ходом игрок должен перекрасить одно из зеленых звеньев в белый цвет и может перекрасить еще одно звено, расположенное ближе к хвосту относительно перекрашенного. Выигрывает игрок, после хода которого все звенья гусеницы станут белыми. Данная игра представляет собой скрытый Ним. Пронумеруем звенья гусеницы, начиная с хвоста. Хвостовое звено получит номер 1, головное – 20 (рис.3). Зеленое звено

Рис. 4. Вычисление Ним-суммы для определения хода в игре 2

с 7 кучками с 2, 5, 6, 9, 14, 16 и 19 камнями. Так как соответствующая Ним-сумма равна (рис.4)

2 † 5 † 6 † 9 † 14 † 16 † 19

$= 10_{2}$ † $101_{2}$ † $110_{2}$ † $1001_{2}$ † $1110_{2}$ †

$10000_{2}$ † $10011_{2}$ †

101 2

5 и есть кучка с 5 камнями, то игроку, делаю-

Рис. 3. Нумерация звеньев гусеницы

гусеницы с номером k заменим кучкой с k камнями. Игрок при своем ходе перекрашивает зеленое звено с некоторым номером k и может перекрасить еще одно звено с номером, меньшим k. Если игрок перекрашивает только одно звено, то считаем, что он опустошил кучку с k камнями. Если второе перекрашенное звено имеет номер m (m < k) и до хода игрока было белым, то считаем, что игрок из кучки с k камнями забрал k – m камней и оставил в ней m камней. А в том случае, когда второе перекрашенное звено с номером m было зеленым, а стало белым, то будем считать, что игрок в кучке с k камнями оставил m камней. Так как до этого уже была кучка с m камнями, то их стало уже две. А две одинаковые кучки вклад в Ним-сумму дают нулевой. Поэтому далее в игре Ним их можно не рассматривать и исключить из игры. Таким образом, данная игра сводится к Ниму с количеством кучек, равным количеству зеленых звеньев гусеницы. Количество камней в кучке совпадает с номером соответствующего зеленого звена. Например, на рисунке 3 игра с перекрашиванием звеньев гусеницы эквивалентна Ниму щему ход, достаточно обнулить кучку из 5 камней, и Ним-сумма оставшихся кучек станет равной 0. Следовательно, выигрышный ход из состояния на рисунке 3 – перекрасить зеленое звено 5 в белый цвет. $Игра^{3.}$ Два игрока по очереди разламывают плитку шоколада, разделенную бороздками на 8 u 12 частей. Одна из частичек плитки помечена крестом. Игрок при каждом своем ходе разламывает плитку вдоль одной из бороздок и съедает ту часть плитки, которая не содержит частички с крестом. Побеждает игрок, после хода которого от плитки шоколада остается всего лишь одна частичка с крестом. Эта игра – тоже завуалированный Ним. У игрока существует 4 варианта хода: разломить плитку по бороздке выше частички с крестом, правее частички с крестом, ниже ее либо левее ее. Если в начале игры частичка с крестом расположена, например, так, как показано на рисунке 5, то над частичкой с крестом расположено 4 ряда, правее ее – 5 рядов, ниже – 3 ряда, левее – 6 рядов. Ход в каждом из четырех вариантов уменьшает количество рядов соответствующего направления.

35

М АТ ЕМ АТИ Ч ЕС КИ Й

Рис. 5. Вид плитки шоколада с выделенной крестом частичкой

Поэтому игра эквивалентна Ниму с 4 кучками камней. В первой кучке количество камней совпадает, например, с количеством рядов над частичкой с крестом, во второй – с количеством рядов правее частички с крестом, в третьей – ниже и в четвертой – левее ее. В примере на рисунке 5 в начале игры в кучках находится 4, 5, 3 и 6 камней. Игрок при своем ходе выбирает кучку и уменьшает в ней количество камней. Для определения хода составляем Нимсумму. В рассматриваемом примере вычисление Ним-суммы проведено на рисунке 6. Получим 4 † 5 † 3 † $6 100_{2}$ † $101_{2}$ † $11_{2}$ † $110_{2}$

$100_{2} 4$. Как видно из рисунка 6, Ним-сумма отлична от 0. Для ее обнуления необходимо удалить

Рис. 6. Составление Ним-суммы для определения хода в игре 3

одну единицу в старшем двоичном разряде, т.е. удалить 4 камня в одной из кучек 1, 2 или 4. В рассматриваемой игре игрок должен удалить 4 ряда либо над, либо справа, либо слева от клетки с крестом. Игра 4. На пяти клетках горизонтальной полоски из 25 клеток находится по фишке. За каждый ход разрешается передвинуть любую фишку влево на свободную клетку, не перепрыгивая через другие фишки. Проигрывает игрок, который не может сделать ход. Занумеруем клетки полоски слева направо числами от 1 до 25. Фишки на полоске тоже будем нумеровать слева направо. Игрок не

КР У Ж ОК

может сделать ход, когда пять фишек занимают клетки с номерами от 1 до 5. Для поиска стратегии сначала упростим игру. Пусть на полоске находится всего одна фишка. Тогда выигрывает начинающий, поставив фишку на клетку 1. Если фишек на полоске две, то стратегия определяется без особых усилий. Игроку следует разместить фишки на соседних клетках. Соперник сможет сделать ход только фишкой 1. Игрок своим очередным ходом перемещает влево фишку 2 так, чтобы фишки опять оказались на соседних клетках. В итоге после нескольких ходов фишки окажутся на клетках 1 и 2, и соперник не сможет сделать ход. Далее рассмотрим случай игры с тремя фишками на полоске. Для построения стратегии воспользуемся правилами расстановки знаков «+» и «–», приведенными в статье «Плюсы–минусы и игра Ним». Состояние игры задают 3 числа – номера клеток с фишками. Поэтому расставлять знаки необходимо в клетках трехмерной таблицы. Координаты клеток $a_{1}, a_{2}, a_{3}$ удовлетворяют соотношениям

$0 a_{1} a_{2} a_{3}$,

(1) где $a_{1}$ – номер клетки с фишкой $1, a_{2}$ – с фишкой $2, a_{3}$ – с фишкой 3. В результате хода одного из игроков одна из трех координат уменьшается, причем соотношение (1) остается в силе. Заполнять знаками таблицу будем по слоям. В нижнем слое, где $a_{1} 1$, фишка 1 ходить не может. А для двух фишек мы уже установили, что в минусовом состоянии фишки размещаются в соседних клетках полоски. Значит, $a_{2} 1 a_{3}$, и во всех клетках с координатами $1, a_{2}, a_{2} 1, 1 a_{2}$, стоит знак «–», а во всех остальных клетках первого слоя – знак «+». В клетках второго слоя таблицы, где $a_{1} 2$, минусы находятся в клетках с координатами 2,3,5, 2,4,6, 2,5,7, …, т.е. в клетках вида $2, a_{2}, a_{2} 2, 2 a_{2}$. Заполняя знаками «+» и «–» клетки третьего слоя, замечаем, что минусы оказываются в клетках с координатами вида $3, a_{2}, a_{2} 3, 3 a_{2}$. Глядя на заполнение минусами первых трех слоев таблицы, можно предположить, что знаки «–» находятся в клетках с коорди-

36

КВАНТ 2019/№4

натами $a_{1}, a_{2}, a_{2} a_{1}, 0 a_{1} a_{2}$. Или, в другом виде, координаты $a_{1}, a_{2}, a_{3}$ минусовых клеток связаны соотношением a 1

$a_{3} a_{2}$.

(2)

Эта гипотеза доказывается методом математической индукции по $a_{1}$. Перепишем соотношение (2) в виде

$a_{1} 0$ a 3 a 2

(3) и предположим, что к полоске добавили слева еще одну клетку с номером 0, на которой стоит нулевая условная фишка. Тогда расстояние в клетках между первой и нулевой фишками совпадает с расстоянием в клетках между третьей и второй фишками. Если расстановка фишек удовлетворяет соотношению (3), то любой ход соперника

ряют соотношению

a 2 a 1

$a_{4} a_{3}$.

И, наконец, для 5 фишек на полоске введем опять условную неподвижную нулевую фишку, которую поместим на условную нулевую клетку, присоединенную к полоске слева. Игра сводится к Ниму с 3 кучками камней. Количество камней в первой кучке полагаем равным количеству свободных клеток между фишками 0 и 1. Размер второй кучки определяется количеством свободных клеток полоски между фишками 2 и 3. Камней в третьей кучке ровно столько, сколько свободных клеток полоски между 4-й и 5-й фишками. На рисунке 7 показан пример определения размеров трех кучек в эквивалентном Ниме.

Рис. 7. Пример определения количеств камней в игре 4

приведет к его нарушению, и игрок своим ответным ходом должен восстановить выполнение соотношения (3). Наблюдается соответствие Ниму с двумя кучками камней. Количество камней в первой кучке совпадает с количеством свободных клеток между нулевой и первой фишками, а во второй кучке – между второй и третьей фишками. В Ниме с двумя кучками игрок должен каждым своим ходом уравнивать количества камней в кучках. В отличие от Нима в данной игре соперник может, передвинув фишку 2, увеличить количество свободных клеток между фишками 2 и 3, что в игре Ним соответствует увеличению числа камней во второй кучке. В этом случае игрок должен ответным ходом передвинуть фишку 3 влево, вернув прежнее число свободных клеток между второй и третьей фишками. Случай с 3 фишками на полоске разобран. Пусть теперь игра проводится с 4 фишками на полоске. Тогда условная фишка, введенная при рассмотрении предыдущего случая, получает воплощение. Обозначим через $a_{i}$ номер клетки, на которой стоит i-я фишка (i = 1, 2, 3, 4). По аналогии с предыдущим случаем номера клеток с фишками для минусового состояния удовлетво-

В примере количества камней в кучках равны 4, 1 и 5. Для победы игрок должен каждым своим ходом обнулять соответствующую Ним-сумму для трех кучек. Перемещения фишек с нечетными номерами уменьшают количество камней в одной из кучек. Если соперник перемещает фишку 2 или 4, скажем, на k клеток влево, то в кучке 2 или 3 соответственно количество камней увеличивается. В этом случае игрок должен своим ходом восстановить количество камней в кучке, переместив соответствующую фишку с нечетным номером на k клеток влево. В рассматриваемом примере Ним-сумма равна 0 (рис.8). Следовательно, игрок, чья очередь делать ход, проигрывает.

Рис. 8. Вычисление Ним-суммы для 3 кучек в игре 4

Игра 5. Клетки полоски из 10 клеток пронумерованы от 1 до 10. На каждой

38

КВАНТ 2019/№4

Рис. 10. Составление Ним-суммы для чисел в игре 5

следует передвинуть из клетки 9 одну фишку, оставив на ней три фишки. Ним-сумма после такого хода станет нулевой. Игра 6. Игра происходит с 4 ломаными. Количество звеньев у ломаной не превышает 20. Три ломаные прикреплены к неподвижному основанию одним концом, а четвертая – обоими концами (рис. 11). За

Рис. 11. Пример начального состояния игры

каждый ход разрешается удалить одно звено у любой ломаной. Если после хода оказались звенья, оторванные от основания, то все они также удаляются. Выигрывает игрок, после хода которого звенья всех ломаных будут удалены. Сведем игру к Ниму с 4 кучками камней. Пусть ломаные А, В и С прикреплены к основанию одним концом, а ломаная D – двумя. Последовательно занумеруем звенья каждой ломаной. У ломаных А, В и С номер 1 получит звено, прикрепленное к основанию (рис.11). Покажем, что каждую из ломаных А, В и С можно заменить кучкой, количество камней в которой равно количеству звеньев в соответствующей ломаной. Пусть ломаная А, например, содержит k звеньев. При удалении i-го звена ломаной А, 1 d i d k, у нее остается i –1 звено с номерами от 1 до i –1. Тем самым, удаление i-го звена равносильно оставлению в кучке i –1 камня. Ломаную D также заменим на некоторую обобщенную кучку камней. Пусть ломаная

D вначале содержит m звеньев. После удаления одного из ее звеньев, скажем звена i, 1 d i d m, ломаная распадается на 2 ломаные с i –1 и m – i звеньями, каждая из которых прикреплена к основанию одним концом. Покажем, что 2 новые ломаные в игре можно заменить одной кучкой камней в Ниме. Если в ломаной D четное количество звеньев, то после удаления одного звена в полученных двух ломаных будет неравное количество звеньев, и у соперника есть возможность своим ходом уравнять количество звеньев в новых ломаных. Две одинаковые кучки имеют одинаковое двоичное представление и дают нулевой вклад в Нимсумму. Получаем, что и обобщенная кучка, которой мы хотим заменить ломаную D, дает нулевой вклад в Ним-сумму, т.е. является пустой. Отличие обобщенной кучки камней от простой при игре в Ним заключается в том, что даже когда обобщенная кучка является пустой, то возможен ход игрока, переводящий ее в непустую кучку. При этом соперник своим ходом обнуляет ее. И снова игрок должен делать ход, а обобщенная кучка – пуста. Вернулись к состоянию, которое уже было. После каждого хода суммарное количество звеньев у ломаных уменьшается, поэтому бесконечное количество раз возвращаться к одному и тому же состоянию обобщенной кучки невозможно. Рассмотрим теперь случай, когда у ломаной D нечетное количество звеньев. Тогда игрок удалением среднего звена может получить две ломаные с одинаковым числом звеньев, которые дают нулевой вклад в Нимсумму. Покажем, что при удалении любого другого звена ломаной D соперник может после своего последующего хода оставить две ломаные, вклад которых в Ним-сумму такой же, как и от кучки с одним камнем. Ломаная D после удаления одного звена не может распасться на две ломаные, количество звеньев в которых отличается ровно на 1. Но тогда соперник, уменьшая своим ходом количество звеньев у ломаной с большим числом звеньев, может получить в новых ломаных количества звеньев, являющиеся двумя последовательными числами, допустим 2n и 2n + 1, где наименьшее число 2n является четным. Вклад двух таких чисел в

ОЛИМПИАДЫ

Московская физическая олимпиада школьников 2019 года

ИЗБРАННЫЕ ЗАДАЧИ

7 класс

1. Нильс на веточке (1 тур) Рост Нильса Хольгерссона после заклятия гнома уменьшился в 10 раз. Пропорции тела остались прежними. Когда он был большим, то сил рук еле-еле хватало, чтобы подтянуться на турнике. Какой груз маленький Нильс может поднять вместе с собой, подтягиваясь на руках на горизонтальной веточке дерева? Масса большого Нильса 30 кг. Подсказка. Сила мышц пропорциональна площади их поперечного сечения. С.Варламов

2. «Жидкий» песок (1 тур) Если сосуд с песком подвергнуть вибрации (проще говоря, потрясти), то можно наблюдать интересное явление – песок становится похож на жидкость. Тяжелые предметы (с большой плотностью) тонут в этом «жидком» песке, а легкие (например, деревянные) предметы наоборот всплывают на поверхность, даже если изначально они были на дне сосуда. Это происходит потому, что при встряхивании уменьшаются силы трения между песчинками. Рассмотрим опыт. На дне цилиндрического сосуда находится песок. Поверх песка насыпана галька. Сосуд подвергают вибрации, и песок становится «жидким». Галька постепенно опускается на

Рис. 1

дно сосуда, а песок заполняет все пустоты между ее камнями. Чему станет равен уровень содержимого в сосуде после оседания гальки, если изначально уровень песка был $h_{1} = 0,6$ м, а уровень гальки $h_{2} = 1$ м (рис.1)? Плотность камней гальки $U_{0} 2600$ кг $м^{3}$, а ее насыпная плотность $U_{1} 1500$ кг $м^{3}$. М.Ромашка

3. Василий и бетон (2 тур) Василию нужно залить фундамент дачного дома, для чего ему необходимо $9,4 м^{3}$ бетона, при этом бюджет Василия ограничен суммой 50000 рублей. Известно, что для получения бетона необходимо смешать цемент с песком и щебнем, при этом чем больше объемная доля цемента в смеси, тем качественнее получается бетон и тем больше значение марки бетона. В магазине Василий узнал, что цена цемента 180 руб. за 50 кг, цена песка 102 руб. за 50 кг, цена щебня 130 руб. за 40 кг, а соотношения объемов материалов для разных марок бетона указаны в таблице. К сожалению, часть данных в таблице была утеряна.

1. Помогите Василию заполнить пустые ячейки в таблице. Известно, что объем песка в марке бетона М400 в два раза меньше объема щебня. 2) Определите, какую наилучшую марку бетона может позволить себе Василий. Плотность цемента $U_{ц} 1200$ кг $м^{3}$, плотность песка $U_{п} 1600$ кг $м^{3}$, плотность щебня $U_{щ} 2100$ кг $м^{3}$. Н.Трушников

52

К ВАН T 2019/№4

Рис. 8

Рис. 10

Рис. 9

собрано устройство, называемое стабилизатором напряжения, обеспечивающее неизменное напряжение $U_{0}$ на нагрузке (резистор сопротивлением R = 300 Ом) при различных значениях напряжения на входе (между точками A и B). При этом напряжение $U_{AB}$ должно лежать в некотором диапазоне напряжений $U_{1}$ ’ $U d U_{AB} d U_{1}$ ’ U, в противном случае устройство перестает выполнять свою функцию стабилизации напряжения. 1) Чему равны напряжение $U_{0}$ и сопротивление резистора r в данной схеме? 2) Найдите сопротивление резистора $R_{1}$, при котором полуширина диапазона входных напряжений ’ U будет максимально возможной при напряжении середины диапазона $U_{1} = 6$ В. З.Резников

5. Двигатель Стирлинга (2 тур) В задаче рассматривается термодинамическая модель двигателя Стирлинга, схематично изображенного на рисунке 10. Поршни 3 совершают возвратно-поступательные движения, преобразующиеся во вращательные движения с помощью кривошипно-шатунных передач. Рабочий цилиндр 1 нагревают горелкой. В рамках модели считается, что его температура поддерживается постоянной, обозначим ее T. На вытеснительном цилиндре 2 закреплен радиатор 6 для улучшения теплообмена, температура в цилинд- ре считается равной комнатной температуре $T_{0}$. Рабочее тело 4 – воздух – перекачивается из рабочего цилиндра в вытеснительный и обратно по трубке 5. Максимальный объем воздуха в рабочем цилиндре обозначим $V_{01}$, а в вытеснительном – $V_{02}$. Объемом трубки можно пренебречь. В результате компьютерных расчетов были получены диаграммы зависимости относительного давления от относительного объема: для рабочего цилиндра – красная линия на рисунке 11, для вытеснительного – синяя линия. При этом цикл для рабочего цилиндра обходится по часовой стрелке, а для вытеснительного – против часовой стрелки; $V_{02} 1,25 V_{01}$. 1) Определите числовое значение отношения температур T и $T_{0}$. 2) Какая часть общей массы воздуха находится в рабочем цилиндре при давлении $3p_{0}$? 3) Определите отношение работы, совершаемой всем газом за цикл, к работе, совершаемой газом в рабочем цилиндре, если площадь фигуры, ограниченной красной линией, $S_{1} = 1,5$ (относительных единиц), а

Рис. 11

ОТВЕТЫ, УКАЗАНИЯ, РЕШЕНИЯ

«КВАНТ» ДЛЯ МЛАДШИХ ШКОЛЬНИКОВ

ЗАДАЧИ

(см. «Квант» №3)

1. 33. Среди чисел от 1 до 100 единицу в записи содержат ровно двадцать: это сама единица, десять чисел от 10 до 19, числа 21, 31,…, 91 (их восемь) и число 100. Значит, ни одно из этих чисел не было стерто. Аналогично, чисел с двойкой ровно девятнадцать: сама двойка, десять чисел третьего десятка, а также 12, 32, 42,…, 92 (таких восемь). Значит, и из них Миша ни одно не стер. Всего таких чисел 19 + 20 - 2 = 37 (мы вычитаем 2, поскольку числа 12 и 21 посчитаны два раза). Всего осталось 37 + 30 = 67 чисел, а Миша $стер^{100} - 67 =^{33}$ числа. 2. См. рисунки 1 и 2.

Рис. 1

Рис. 2

Комментарий. Решение задачи может стать нагляднее, если вместо обычной сетки с горизонтальными и вертикальными линиями рассмотреть диагональную, изображенную на рисунке 3

Рис. 3

Рис. 4

пунктирными линиями. На диагональной сетке наша фигура имеет площадь 4 клетки, и ее надо разрезать на 4 фигуры площади 1. Аналогичная фигура на обычной сетке изображена на рисунке 4, ее разрезание там проще увидеть, а потом его можно перенести на исходную фигуру. 3. 5. Если Сеня с ошибкой пишет Д, то из букв О, Е, К, А, Э, Р, которые еще входят в ДОДЕКА- ЭДР, он в трех ошибается, а три пишет верно. Но все эти буквы, кроме Е, входят и в ИКОСА- ЭДР, т.е. там он напишет верно как минимум две буквы и никак не сможет $сделать^{7}$ ошибок. Значит, букву Д Сеня пишет правильно. Тогда он неминуемо пишет с ошибкой все остальные буквы слов ДОДЕКАЭДР и ИКОСАЭДР, а в слове ТЕТРАЭДР, таким образом, помимо Д, еще верно пишет букву Т, но ошибается во всех

остальных. Теперь ясно, что в слове ОКТАЭДР Сеня сделает пять ошибок. 4. Пример с пятью дополнительными рейсами показан на рисунке 5. Можно доказать, что добавить меньшее число рейсов невозможно.

Рис. 5

КОНКУРС ИМЕНИ А.П.САВИНА

(см. «Квант» №2) 21. а) Да. Расставим в нечетных вертикалях и горизонталях по 1 фишке, а в четных – по 5 так, как на $рисунке^{6.}$ б) Нет. Допустим, нам удалось найти такую расстановку. Тогда в каждой горизонтали и вертикали либо 1 фишка – назовем такие ряды тощими, $либо^{6}$ – назовем такие ряды толстыми. Толстых $вертика-^{Рис.} 6$ лей, как и толстых горизонталей, 4, поэтому фишек, стоящих в толстой вертикали и толстой горизонтали, не более 16. А фишек, стоящих в толстой вертикали и тощей горизонтали, не более 4 – по одной на каждую горизонталь. Итого в толстых вертикалях получается не более 20 фишек, а должно $быть^{4}$ ◊ $6 =^{24}$. Противоречие. 22. а) Нет. Пусть такая раскраска нашлась. Возьмем три точки A, B, C разных цветов. Они не могут образовывать треугольник, иначе описанная вокруг него окружность содержала бы три цвета. Значит, они лежат на одной прямой. Возьмем теперь любую точку X вне этой прямой. Она совпадает по цвету с одной из точек A, B, C, пусть с A. Тогда X, B, C имеют разные цвета и снова образуют треугольник. Противоречие. б) Да. Выберем три точки на одной прямой и покрасим их в три первых цвета, а все остальные точки плоскости – в четвертый цвет. Так как окружность не может содержать три точки, лежащие на одной прямой, на любой окружности не будет хотя бы одного из первых трех цветов. 23. Пусть O – точка пересечения $A_{1} M$ и $B_{1} K$ (рис.7). Чтобы доказать равенство площадей $MC_{1} KO$ и $B_{1} OA_{1} C$, добавим к каждому них треугольник $OMB_{1}$ и докажем, что площади получившихся многоугольников $MC_{1} KB_{1}$ и