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

2

КВАНТ 2014/№4

Левитирующий магнитный волчок

А.ПАНОВ

ОПРЕДЕЛИМ ЛЕВИТАЦИЮ КАК СВОБОДНОЕ ЗА- висание тел в воздухе. Мы будем рассматриваривать исключительно магнитную левитацию. И в самом деле, магниты кажутся подходящими кандидатами. Чтобы заставить тело левитировать, нужно каким-то образом компенсировать силу тяжести. А магниты, обращенные друг к другу одноименными полюсами, отталкиваются. Если расположить их на определенном расстоянии друг над другом, то магнитное отталкивание как раз сможет уравновесить силу тяжести, и верхний магнит зависнет над нижним. Многие пытались действовать подобным образом, но ничего не получалось. Магниты каким-то образом изворачивались в воздухе, оказывались повернутыми друг к другу разноименными полюсами и притягивались. И на этом все заканчивалось – никакой левитации. Не помогает и замена отталкивающего магнита на целую систему магнитов, расположенных на плоскости или в пространстве, – и в этом случае добиться зависания не удается. Казалось, что левитация невозможна. И этому было мощное теоретическое подтверждение.

Теорема Ирншоу – невозможность левитации

Начнем с двойной цитаты Гейма – Берри из статьи Андрея Гейма «Магнетизм для всех» (http:// www.physics.umd.edu/grt/taj/411c/Everyones Magnetism.pdf, http://www.scientific.ru/journal/ translations/magn_ed.html): «Попробуйте, например, заставить левитировать магнитное тело. Вы, конечно, легко сможете поднять его с помощью подковообразного магнита, но вы не сможете заставить его зависнуть с помощью какой бы то ни было хитроумной конфигурации магнитов. Чтобы понять, в чем здесь дело, нужно вспомнить теорему Ирншоу, которая (как ее недавно переформулировал Майкл Берри) утверждает, что никакой стационарный объект, сделанный из зарядов, магнитов и масс, не может быть подвешен в пространстве с помощью любой фиксированной комбинации электрических, магнитных и гравитационных сил». Эта теорема была доказана английским священиком, математиком и физиком Самуэлем Ирншоу в 1842 году. Она имеет простую формулировку, красивое доказательство и хорошо известна каждому физику. Многие физики считали ее абсолютным запретом магнитной левитации, но оказалось, что существуют обходные пути.

Простой эксперимент Начнем с простого эксперимента, который на первый взгляд представляет собой не больше чем пародию на магнитную левитацию. На рисунке 1 видны два магнита, нанизанные на деревянный стержень, – один неодимовый, другой ферритовый, но это пока не так важно. Главное, что магниты повернуты друг к другу одноименными полюсами и взаимно отталкиваются – верхний висит над нижним. Почему это нельзя назвать левитацией? А потому, что это зависание не является свободным – свободному движению верхнего магнита препятствует деревянная палочка. Нет ли здесь противоречия с теоремой Ирншоу? Нет, потому что кроме Рис.1. Магнит на палочке магнитных и гравитационных сил на верхний магнит действуют упругие силы, возникающие при его взаимодействии с деревянной палочкой. Но все не так плохо. Продолжим анализ нашего эксперимента. Высота зависания верхнего магнита – это та высота, на которой действующие на него сила тяжести и магнитная сила уравновешиваются. Не будем снимать верхний магнит с палочки, а расположим его на этой высоте строго горизонтально и отпустим. Легко убедиться, что в этом случае потенциальная энергия магнита будет уменьшаться не за счет вертикального падения, а за счет его поворота в магнитном поле. Если бы не деревянная палочка, верхний магнит повернулся бы на $180\infty$ – своим противоположным полюсом к нижнему магниту – и притянулся к нему. Палочка препятствует этому. Если бы удалось заменить палочку на что-то менее вещественное, но тоже препятствующее повороту, то возможно, проблема левитации была бы решена. Оказывается, в этом может помочь гироскопический эффект. Именно закрутка кольцевого магнита вокруг оси может воспрепятствовать его опрокидыванию и дальнейшему падению. Это – ключевая идея для того типа левитации, который мы обсуждаем. Но, во-первых, ее не так просто реализовать. А во-вторых, как уже

7

СВЯЖИТЕСЬ

тью мы понимаем набор клеток, по которым жук может путешествовать, не переползая через спички). Ясно, что, убрав спичку, мы можем слить не более двух областей в одну, т.е. уменьшим число областей не более чем на одну. Нам понадобится не менее 63 слияний, и значит, убрать надо не менее 63 спичек. А вот пример (рис.5): уберем все внутренние горизонтальные спички и все внутренние вертикальные спички на нижней горизонтали – как раз 63 спички в сумме. Задача решена.

Теорема о связности графа

Что общего в решениях задач 1 и 2? И там и тут были разрозненные объекты (шарики, клетки), которые мы объединяли в группы (области), а ключом к решению стала идея проследить за количеством таких групп (областей). В обеих задачах есть связи между парами объектов: ребро куба соединяет пару вершин, спичка служит границей между парой соседних клеток. Связи тут очень наглядны, и это облегчает их подсчет. Чтобы по возможности не повторять одни и те же рассуждения в разных ситуациях, математики вводят общие понятия. Структуры, в которых есть связи между парами объектов, называются графами. Наглядное представление графа такое: изображается система точек – вершин графа, где некоторые пары вершин соединены линиями – ребрами графа. При этом не важно, где именно на плоскости расположены вершины, как именно выглядят ребра – в виде отрезков или кривых. Изображая граф, мы также не обращаем внимания на возможные пересечения ребер в точках, отличных от вершин. Можно изготовить модель графа из пуговиц-вершин и нитей-ребер. Раскладывая такую модель на столе или запутывая как угодно, мы граф не изменяем. В модели из пуговиц и нитей хорошо видны связные куски – компоненты: на такие компоненты можно разделить модель, не разрывая нитей. Давайте более строго поговорим о связности в графах. Граф называется связным, если от любой его вершины можно дойти до любой другой вершины, двигаясь по ребрам (т.е. переходя несколько раз из вершины в вершину по ребру). Пусть в произвольном графе зафиксирована вершина A. Множество вершин, в которые можно попасть из данной вершины A, двигаясь по ребрам, назовем компонентой связности вершины A и обозначим K ( A ). При этом считается, что сама вершина A входит в компоненту K ( A ). Если из вершины A в вершину B можно пройти, двигаясь по ребрам, то компоненты связности K ( A ) и K ( B ) совпадают, а в противном случае у них нет общих вершин (докажите это!). Таким образом, мно-

Рис. 6

С

ГРАФОМ

жество всех вершин графа разбивается на компоненты связности (в частности, множество вершин связного графа представляет собой одну компоненту). На рисунке 6 изображен пример графа, у которого всего 4 компоненты связности. Обратим внимание на то, что компонента может состоять и из одной изолированной вершины. Сформулируем важную и часто используемую теорему о связности. Теорема. 1. Пусть дан связный граф с n вершинами. Тогда в нем не менее n – 1 ребер. 2. Пусть граф с n вершинами распадается на k компонент связности. Тогда в нем не менее n – k ребер. Доказательство. (Оно фактически воспроизводит рассуждения из решений уже разобранных нами задач.) Сотрем в графе все ребра. Тогда все его вершины станут изолированными, т.е. граф распадется на n компонент связности. Начнем восстанавливать ребра по одному. Каждое проведенное ребро либо соединяет две компоненты связности в одну, либо никак не меняет разбиение на компоненты. Тем самым, восстановление ребра может уменьшить число компонент не более чем на 1. Поэтому, чтобы уменьшить число компонент с n до k, потребуется провести не менее n – k ребер. В частности, чтобы сделать граф связным (т.е. сделать k = 1), надо провести не менее n – 1 ребер. Попробуем еще раз вернуться к задачам 1 и 2 и проанализировать, какое отношение к ним имеет теорема связности. Картинка на рисунке 1 почти совпадает с наглядным представлением графа, и из теоремы сразу следует, что для сохранения связности нужно оставить не менее 7 ребер. Картинка со спичками на рисунке 4 тоже представляет собой изображение графа, но не того, который нужен для решения задачи. И неудивительно: ведь чтобы создать связь между клетками, мы убираем спичку! Опишем нужный нам граф. Поставим вершины в центры клеток (всего 64 вершины), а ребром будем соединять пары центров соседних клеток, если на границе между ними нет спички. Рассматривая такой граф, мы полностью сводим задачу к ситуации, описанной в теореме. Наверное, идея подсчета числа областей более ясно видна в задаче про спички (и ее решение выглядит даже более просто, чем доказательство теоремы).

Упражнения 1. Шоколадка $4 \times 6$ разделена бороздками на 24 квадратные плиточки. За один ход можно разламывать один любой кусок в любом месте и любом направлении, но обязательно вдоль бороздок. За какое наименьшее число разломов можно полностью разделить целую шоколадку на плиточки? 2. Решите задачу 2 в предположении, что убирать граничные спички можно и жук может выползать за пределы доски (но жук хочет только иметь возможность посещать все 64 клетки). Указание. Можно считать, что вначале у нас есть 65 областей, считая внешнюю. 3. Пусть дан связный граф c n вершинами и k ребрами,

8

КВАНТ 2014/№4

причем k > n – 1. Докажите, что можно удалить ребро так, чтобы граф остался связным. Указание. Можно использовать прием, который мы встречали: удалить сначала все ребра, а затем восстанавливать их по одному.

Из упражнения 3 вытекает, что примеры в задаче 1 всегда можно получить, перекусывая одно за другим 5 ребер, заботясь лишь о сохранении связности.

Упражнение 4 (Д.Храмцов, Всероссийская олимпиада, окружной этап, 1998 г.). Куб со стороной $n \ge 3$ разбит перегородками на единичные кубики. Какое минимальное число перегородок между кубиками нужно удалить, чтобы из каждого кубика можно было добраться до границы куба?

Необычные вспомогательные графы

Понятны типовые ситуации, которые легко описываются на языке графов: это города и соединяющие их дороги (авиалинии), знакомства людей в некоторой компании… Далее мы рассмотрим задачи, в которых применение графов (и конкретно теоремы связности) не столь очевидно, но весьма продуктивно. Намеком на использование графа в решении той или иной задачи могут стать связи между парами объектов или даже просто выделенный набор пар. Задача 3 (по мотивам задачи И.Раскиной). Есть m болельщиков: некоторые из них (возможно, все или никто) болеют за «Спартак», а остальные – за «Динамо». Разрешается спросить у любых двоих, болеют ли они за разные команды, и они честно ответят «да» или «нет». Требуется посадить болельщиков в два автобуса так, чтобы в каждом были болельщики только одной команды. За какое минимальное количество вопросов это наверняка можно сделать? Ответ: m – 1. Решение. Пример. Если задать вопросы первому и второму, первому и третьему, …, первому и m-у, то рассадить будет легко: ответивших «да» сажаем в автобус вместе с первым, а остальных – в другой автобус. Оценка. А теперь рассмотрим ситуацию, когда было задано не более чем m – 2 вопроса. Построим граф вопросов: вершины соответствуют болельщикам, а ребра соединяют пары болельщиков, которым был задан вопрос. В нашем графе m вершин и не более m – 2 ребер, значит, по теореме связности он не связен. Но возможно ли по несвязному графу понять, как правильно разделить болельщиков? Рассмотрим одну из компонент связности A. Множество A делится на два подмножества A¢ и A¢¢ (болельщики «Спартака» и болельщики «Динамо» соответственно). Аналогично, компонента связности B делится на подмножества B¢ и B¢¢. В один из автобусов надо посадить болельщиков из множества A¢, однако неизвестно, какое именно из подмножеств B¢ и B¢¢ к ним нужно добавить. В самом деле, если бы множество B¢ оказалось болельщиками «Динамо», а B¢¢ – «Спартака», на все заданные им вопросы они дали бы в точности те

же ответы (все вопросы были заданы внутри компоненты связности). А рассадка должна была быть другой. Значит, по ответам рассадка однозначно не восстанавливается.

Упражнение 5 (И.Раскина, Турнир имени А.П.Савина, 2011 г.). Решите предыдущую задачу, если дополнительно известно, что m = 2n и что ровно n человек болеют за «Спартак» и n – за «Динамо».

Разберем еще несколько задач про клетчатые фигуры. В следующей задаче, как и в задаче 2, нам поможет граф, иллюстрирующий соседство клеток. Задача 4. На клетчатой бумаге нарисован многоугольник площадью в n клеток. Его контур идет по линиям сетки. Каков наибольший периметр многоугольника? (Сторона клетки равна 1.) Ответ: 2n + 2. Решение. Пример. Прямоугольник n ¥ 1. Оценка. Сумма периметров n клеток равна 4n. Из этих периметров складывается периметр многоугольника и удвоенная сумма длин отрезков сетки внутри многоугольника: ведь к каждому внутреннему отрезку клетки примыкают с двух сторон. Чтобы оценить общую длину внутренних отрезков, построим граф: вершины – клетки прямоугольника, ребра связывают клетки с общей стороной. Этот граф связен: ладья может свободно путешествовать между всеми клетками внутри многоугольника. По теореме, у графа не менее n – 1 ребра, т.е. общая длина внутренних отрезков не менее n – 1. Но тогда периметр многоугольника не более 4 n - 2 ( n - 1 ) = 2 n + 2. Комментарий. Конечно, эту оценку можно доказать и индукцией по числу клеток. Но индуктивное утверждение нужно формулировать умело. На занятиях математического кружка немало школьников пытались опираться на кажущееся очевидным (а по сути близкое к упражнению 3) утверждение: «многоугольник из ( k + 1 ) -й клетки можно получить, добавив одну клетку к какому-нибудь многоугольнику из k клеток», но так и не смогли его доказать… Заметьте, что во многих задачах бывает полезна более общая конструкция «двойственного графа», когда области в некоторой «карте» на плоскости объявляются вершинами, а если у двух областей-вершин есть общая часть границы, то они соединяются ребром.

Упражнение 6 (А.Шаповалов, Турнир имени А.П.Савина, 2009 г.). На клетчатой бумаге нарисован тысячеугольник со сторонами по границам клеток. Из какого наименьшего числа клеток он может состоять?

Задача 5 (X Турнир городов). Тетрадный лист раскрасили в 23 цвета по клеткам (при этом все цвета присутствуют). Пара цветов называется хорошей, если найдутся две соседние клетки, закрашенные этими цветами. Каково минимальное число хороших пар? Путь к решению. Среди всевозможных пар цветов явно выделены хорошие. Это намек на возможность построить граф «цветов» и оценить число ребер в нем! Ответ: 22 пары.

СВЯЖИТЕСЬ

Решение. Пример. Нетрудно построить пример с 22 хорошими парами цветов. Например, 22 хорошие пары получаются, если в «море» первого цвета плавают «островки» каждого из остальных 22 цветов. Здесь хорошие пары цветов – это в точности пары с участием первого цвета. Оценка. Докажем, что меньше чем 22 хорошие пары быть не может. Рассмотрим такой граф Г: каждому цвету сопоставим вершину графа (итого 23 вершины), для каждой хорошей пары цветов соединим ребром соответствующие им вершины. Если доказать, что граф Г связный, то по теореме о связности в нем будет не менее 22 ребер. Возьмем в Г любую пару вершинцветов A, B и на тетрадном листе отметим клетку K цвета A и клетку L цвета B. Будем перемещаться, начиная с клетки K, в соседние по стороне клетки и через несколько ходов придем в клетку L. В соответствии с перемещением по тетрадному листу будем двигаться по вершинам графа Г: если мы на очередном ходу из клетки M цвета C перешли в соседнюю с ней клетку N другого цвета D, то в графе Г мы из вершины C переходим в вершину D (C и D соединены ребром, так как клетки M и N соседние); если цвет клетки не меняется, то в графе Г мы остаемся на месте. Так мы получаем в графе Г путь по ребрам из вершины A в вершину B. Это доказывает связность графа Г.

Упражнение 7. Клетки шахматной доски раскрасили ровно в 33 цвета. Пару разных цветов назовем хорошей, если можно поставить пару бьющих друг друга коней на клетки этих цветов. Найдите наименьшее возможное число хороших пар. Указание. Здесь нас интересуют не пары соседних клеток, а пары клеток, с одной из которых ходом коня можно перейти на другую.

Задача 6 (С.Токарев). Дан клетчатый прямоугольник m ¥ n. Каждую его клетку разрезали по одной из диагоналей. На какое наименьшее число частей мог распасться прямоугольник? Ответ: m + n. Решение. Пример. Можно во всех клетках провести параллельные разрезы (рис.7), тогда количество частей будет m + n. Оценка. Пусть в каждой клетке проведен разрез

Рис. 7

Рис. 8

вдоль одной из диагоналей. Построим граф: вершины будут соответствовать треугольничкам – половинам разрезанных клеток, а ребро между вершинами проведем, если соответствующие треугольнички имеют общий катет. Нетрудно понять, что каждой из частей, на которые распался прямоугольник, соответствует компонента связности нашего графа (пример – на рисунке 8). Число вершин равно удвоенному числу клеток, т.е. 2mn. Число ребер равно числу границ между соседни-

С

ГРАФОМ

9 ми клетками, т.е. m ( n - 1 ) + n ( m - 1 ) = 2 mn - ( m + n ).

Согласно теореме, количество компонент связности в таком графе не меньше чем m + n.

Упражнение 8 (И.Акулич, XXIV Турнир городов). Какое наибольшее число клеток доски 9 ¥ 9 можно разрезать по обеим диагоналям, чтобы доска не распалась на части? Указание. Постройте граф, вершины которого – целые клетки или четвертушки разрезанных клеток (число вершин в нем зависит от числа разрезанных клеток).

Последнее упражнение интересно тем, что вспомогательный граф в нем можно построить многими способами. Кстати, и ответ далеко не очевиден. Теперь приведем решение задачи М2339 «Задачника «Кванта». Задача 7 (В.Мокин, задача М2339, обобщение задачи М1295). Дана доска $m \times n$, разбитая на единичные клетки. Сначала в ( m - 1 ) ( n - 1 ) + 1 клеток ставится по фишке. Пусть в некоторый момент на доске нашлись такие четыре клетки, центры которых являются вершинами прямоугольника со сторонами, параллельными краям доски, что ровно в одной из этих клеток стоит фишка; тогда эту фишку можно снять. Докажите, что хотя бы одну фишку не удастся снять с доски, проделывая только описанные операции. Решение. Построим граф: вершины – вертикали и горизонтали, их всего m + n. Ребро связывает вертикаль с горизонталью, если на их пересечении нет фишки. Изначально свободны mn - ( m - 1 ) ( n - 1 ) - 1 = = m + n - 2 клетки, т.е. число ребер меньше m + n – 1. По теореме наш граф – не связный. Клетку на пересечении горизонтали h и вертикали v будем обозначать ( h, v ), а если эта клетка свободна, то ( h, v ) означает и ребро от h до v. Что произойдет при описанном в условии снятии фишки? Пусть четыре центра клеток расположены в вершинах прямоугольника на пересечении горизонталей p, q и вертикалей r, s, а фишка снимается с клетки ( p, r ). Тогда, по условию, клетки ( p, s ), ( q, s ) и ( q, r ), свободны. Это означает, что в момент перед снятием фишки в графе были ребра ( p, s ), ( q, s ) и ( q, r ). Они образовывали путь из p в r, т.е. p и r лежали в одной компоненте связности. Снимая фишку, мы добавляем в графе ребро ( p, r ), но компонент связности это не меняет. Поэтому граф был и остается не связным. Заметим теперь, что на пустой доске каждая вертикаль связана с каждой горизонталью. Такой граф связен: горизонтали в нем связаны двузвенным путем через любую вертикаль, и наоборот. Но уже доказано, что связный граф мы получить не можем, поэтому все фишки снять нельзя. Путь к решению. Построенный граф кажется необычным. Однако для математиков таблица из нулей и единиц – достаточно привычный способ представления так называемых двудольных графов: в таких графах вершины делятся на два сорта (две доли), а ребра могут связывать только вершины разных сортов. Доска из последней задачи естественно превращается в таблицу из нулей и единиц, если фишки заменить на 0, а пустые

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

Задачи

1. Найдите все возможные решения ребуса

ТЫ + ТЫ + ТЫ + ТЫ + ТЫ = ВЫ.

Фольклор

4. Внутри равностороннего треугольника отметили

На тараканьих бегах 20 тараканов выбегают друг за другом с интервалом в 1 минуту и бегут с постоянными скоростями. Второй догнал первого через 2 минуты после своего старта, третий второго – через 3 минуты после своего старта, …, двадцатый девятнадцатого – через 20 минут после своего старта. Через сколько минут после своего старта двадцатый таракан догнал первого? А.Шаповалов точку, соединили ее с вершинами и разрезали треугольник по этим отрезкам. Можно ли выбрать точку так, чтобы из полученных треугольников без сгибов и наложений удалось сложить другой треугольник? А.Банникова

88x49

5. Из шести монет две более легкие – фальшивые.

Эти задачи предназначены прежде всего учащимся 6–8 классов. Эти задачи предлагались на XX Летнем турнире имени А.П.Савина.

Иллюстрации Д.Гришуковой

У прямой дороги на расстоянии 5 метров стоят два столба. Высота более высокого столба тоже 5 метров. Между верхушками столбов натянут провод. Подул ветер, и маленький столб упал на дорогу в направлении высокого столба, как показано на рисунке. Что стало с проводом: он провисает, он снова натянут или он порвался? М.Раскин, Е.Бакаев

Есть чашечные весы, за каждое взвешивание на которых надо предварительно заплатить одну монету. Если уплаченная монета настоящая, весы показывают правильный результат, а если фальшивая – неизвестно что. Как найти (и не потратить) одну настоящую монету? В.Клепцын, А.Заславский

Многогранники вокруг нас

Знакомство с миром многогранников можно начать, не дожидаясь уроков стереометрии в старших классах. Иногда достаточно взглянуть на некоторые творения архитекторов. Большинство современных многоэтажек имеют форму прямоугольных параллелепипедов. Их иногда несколько небрежно называют коробками (по-английски длинное «rectangular parallelepiped» также часто заменяется на коротокое «box»). Это легко объясняется – строить коробки проще. Правда, и среди коробок есть необычные здания. Согласитесь, не часто встретишь дом практически кубической формы, как городская библиотека города Штутгарта (фото 1)!

вых, выставочных центров и других зданий в форме пирамид. Иногда дизайнеры и архитекторы предлагают перевернуть наши представления о пирамидах (фото 3).

Фото 3. В этом здании располагается мэрия города Тэмпе (Аризона, США)

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

Фото 1

Наиболее известные древние сооружения пирамидальной формы – это египетские пирамиды. Ритуальные пирамиды майя на мексиканском полуострове Юкатан также имеют форму пирамид, или точнее, усеченных пирамид, в основании которых лежит квадрат (фото 2). На сегодняшний день руками людей сделано большое число спортивных, торго-

Фото 4

Фото 2

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

Фото 5. Высотные башни в канадском городе Реджайна

Фото 8

Фото 6. Барселонский «Форум»

любой многоугольник, например треугольник (фото 6). Высотное здание Всемирного торгового центра в Нью-Йорке имеет форму так называемой четырехугольной антипризмы (фото 7). В основаниях антипризмы два равных квадрата, один из которых повернут на 45 градусов относительно другого. Кроме двух оснований у антипризмы есть треугольные боковые грани (сколько их?). А что получится, если антипризму разрезать посередине сечением, параллельным основаниям? Чтобы ответить на этот вопрос, можно воспользоваться фото

8, которое было сделано, когда Всемирный центр был построен наполовину. А завершим нашу небольшую экскурсию в Минске. Здание Национальной библиотеки Белоруссии имеет форму ромбокубооктаэдра (фото 9). В качестве упражнения

Фото 9 можете посчитать, сколько у него вершин, ребер и граней каждого типа. Материал подготовили С.Дворянинов, П.Кожевников

Источники фотографий:

Фото 7

1 – http://www.home-designing.com/ 2 – http://en.wikipedia.org/wiki/Chichen_Itza 3 – http://en.wikipedia.org/wiki/Tempe_Municipal_Building 4 – http://bof.co.uk/project/13 5 – http://www.workopolis.com/ 6 – http://www.pushpullar.com 7 – http://en.wikipedia.org/wiki/New_York_City 8 – http://www.the atlantic.com 9 – http://www.calend.ru

ОЛИМПИАДЫ

XXXV Турнир городов

ЗАДАЧИ ВЕСЕННЕГО ТУРА

Базовый вариант

8–9 классы

1 (3). Даны 100 чисел. Когда каждое из них увеличили на 1, сумма их квадратов не изменилась. Каждое число еще раз увеличили на 1. Изменится ли сумма квадратов на этот раз, и если да, то на сколько? А.Шаповалов

1

2 (4). Мама испекла одинаковые с виду пирожки: 7 с капустой, 7 с мясом и один с вишней, и выложила их по кругу на круглое блюдо именно в таком порядке. Потом поставила блюдо в микроволновку подогреть. Оля знает, как лежали пирожки, но не знает, как повернулось блюдо. Она хочет съесть пирожок с вишней, а остальные считает невкусными. Как Оле наверняка добиться этого, надкусив не больше трех невкусных пирожков? А.Хачатурян

3 (4). См. задачу М2350 «Задачника «Кванта».

4 (5). На стороне BC треугольника ABC выбрана точка L так, что AL в два раза больше медианы CM. Оказалось, что угол ALC равен $45\infty$. Докажите, что AL и CM перпендикулярны. Р.Женодаров

5 (6). На переправу через пролив Босфор выстроилась очередь: первый – Али-Баба, за ним 40 разбойников. Лодка одна, в ней могут плыть двое или трое (в одиночку плыть нельзя). Среди плывущих в лодке не должно быть людей, которые не дружат между собой. Смогут ли все они переправиться, если каждые двое рядом стоящие в очереди – друзья, а Али-Баба еще дружит с разбойником, стоящим через одного от него? А.Шаповалов

10–11 классы

1 (4). У Чебурашки есть набор из 36 камней массами 1 г, 2 г,…, 36 г, а у Шапокляк есть суперклей, одной каплей которого можно склеить два камня в один (соответственно, можно склеить 3 камня двумя каплями и так далее). Шапокляк хочет склеить камни так, чтобы Чебурашка не смог из получившегося набора выбрать один или несколько камней общей массой 37 г. Какого наименьшего количества капель клея ей хватит, чтобы осуществить задуманное? Е.Бакаев

2 (4). В выпуклом четырехугольнике ABCD диагонали перпендикулярны. На сторонах AD и CD отмечены соответственно точки M и N так, что углы ABN и CBM прямые. Докажите, что прямые AC и MN параллельны. А.Полянский

3 (5). См. задачу 5 для 8 – 9 классов.

1 В скобках после номера задачи указано максимальное число баллов, присуждавшихся за ее решение. Итог подводится по трем задачам, по которым достигнуты наилучшие результаты.

4 (5). Натуральные числа a, b, c, d попарно взаимно просты и удовлетворяют равенству ab + cd = ac – 10bd. Докажите, что среди них найдутся три числа, одно из которых равно сумме двух других. Б.Френкин

5 (5). Дан выпуклый четырехугольник ABCD. Пешеход Петя выходит из вершины A, идет по стороне AB и далее по контуру четырехугольника. Пешеход Вася выходит из вершины A одновременно с Петей, идет по диагонали AC и одновременно с Петей приходит в C. Пешеход Толя выходит из вершины B в тот момент, когда ее проходит Петя, идет по диагонали BD и одновременно с Петей приходит в D. Скорости пешеходов постоянны. Могли ли Вася и Толя прийти в точку пересечения диагоналей O одновременно? Б.Френкин

Сложный вариант

8–9 классы

1 (3). Дед Мороз раздал детям 47 шоколадок так, что каждая девочка получила на одну шоколадку больше, чем каждый мальчик. Затем дед Мороз раздал тем же детям 74 мармеладки так, что каждый мальчик получил на одну мармеладку больше, чем каждая девочка. Сколько всего было детей? Е.Бакаев

2 (5). На клетчатой доске $5 \times 5$ Петя отмечает несколько клеток. Вася выиграет, если сможет накрыть все эти клетки неперекрывающимися и не вылезающими за границу квадрата уголками из трех клеток (уголки разрешается класть только «по клеточкам»). Какое наименьшее число клеток должен отметить Петя, чтобы Вася не смог выиграть? А.Шаповалов

3 (6). На квадратном столе лежит квадратная скатерть так, что ни один угол стола не закрыт, но с каждой стороны стола свисает треугольный кусок скатерти. Известно, что какие-то два соседних куска равны. Докажите, что и два других куска тоже равны. (Скатерть нигде не накладывается сама на себя, ее размеры могут отличаться от размеров стола.) Е.Бакаев

4 (7). Царь вызвал двух мудрецов. Он дал первому 100 пустых карточек и приказал написать на каждой по натуральному числу (числа не обязательно разные), не показывая их второму. Затем первый может сообщить второму несколько различных чисел, каждое из которых либо записано на какой-то карточке, либо равно сумме чисел на каких-то карточках (не уточняя, как именно каждое число получено). Второй должен определить, какие 100 чисел написаны на карточках. Если он этого не сможет, обоим отрубят головы; в противном случае из бороды каждого вырвут столько волосков, сколько чисел сообщил первый второму. Как мудрецам, не сговариваясь, остаться в живых и потерять минимальное количество волосков? И.Богданов

5 (7). Даны несколько белых и несколько черных точек. От каждой белой точки идет стрелка в каждую черную, на

44

КВАНТ 2014/№4

каждой стрелке написано натуральное число. Известно, что если пройти по любому замкнутому маршруту из стрелок, то произведение чисел на стрелках, идущих по направлению движения, равно произведению чисел на стрелках, идущих против направления движения. Обязательно ли тогда можно поставить в каждой точке натуральное число так, чтобы число на каждой стрелке равнялось произведению чисел на ее концах? А.Пахарев

6 (9). Из кубиков $1 \times 1 \times 1$ склеен куб $3 \times 3 \times 3$. Какое наибольшее количество кубиков можно из него выкинуть, чтобы осталась фигура с такими двумя свойствами: i со стороны любой грани исходного куба фигура выглядит как квадрат $3 \times 3$ (глядя перпендикулярно этой грани, мы не увидим просвета – видны 9 кубиков фигуры); i переходя в фигуре от кубика к кубику через их общую грань, можно от любого кубика добраться до любого другого? А.Марачев

7 (9). На окружности отмечены 10 точек, занумерованные по часовой стрелке: $A_{1}, A_{2},..., A_{10}$, причем известно, что их можно разбить на пары симметричных относительно центра окружности. Изначально в каждой отмеченной точке сидит по кузнечику. Каждую минуту один из кузнечиков прыгает вдоль окружности через своего соседа так, чтобы расстояние между ними не изменилось. При этом нельзя пролетать над другими кузнечиками и попадать в точку, где уже сидит кузнечик. Через некоторое время оказалось, что какие-то 9 кузнечиков сидят в точках $A_{1}, A_{2},..., A_{9}$, а десятый кузнечик сидит на дуге $A_{9} A_{10} A_{1}$. Можно ли утверждать, что он сидит именно в точке $A_{10}$? Е.Бакаев

10 –11 классы

1 (3). Незнайка хвастается, что написал в ряд несколько единиц, поставил между каждыми соседними единицами знак «+» или знак « $\times$ », расставил скобки и получил выражение, значение которого равно 2014; более того, если в этом выражении заменить одновременно все знаки «+» на знаки « $\times$ », а знаки « $\times$ » на знаки «+», все равно получится 2014. Может ли он быть прав? В.Клепцын

2. Верно ли, что любой выпуклый многоугольник можно по прямой разрезать на два меньших многоугольника с равными периметрами и а) (4) равными наибольшими сторонами; б) (4) равными наименьшими сторонами? А.Шаповалов

3 (6). Царь вызвал двух мудрецов. Он дал первому 100 пустых карточек и приказал написать на каждой по положительному числу (числа не обязательно разные), не показывая их второму. Затем первый может сообщить второму несколько различных чисел, каждое из которых либо записано на какой-то карточке, либо равно сумме чисел на какихто карточках (не уточняя, как именно каждое число получено). Второй должен определить, какие 100 чисел написаны на карточках. Если он этого не сможет, обоим отрубят головы; в противном случае из бороды каждого вырвут столько волосков, сколько чисел сообщил первый второму. Как мудрецам, не сговариваясь, остаться в живых и потерять минимальное количество волосков? И. Богданов

4 (7). См. задачу М2351 «Задачника «Кванта».

5 (8). См. задачу М2354 «Задачника «Кванта».

6 (9). Каждому городу в некоторой стране присвоен индивидуальный номер. Имеется список, в котором для каждой пары номеров указано, соединены города с данными номерами железной дорогой или нет. Оказалось, что, какие ни взять два номера M и N из списка, можно так перенумеровать города, что город с номером M получит номер N, но список по-прежнему будет верным. Верно ли, что, какие ни взять два номера M и N из списка, можно так перенумеровать города, что город с номером M получит номер N, город с номером N получит номер M, но список по-прежнему будет верным? А.Пахарев, М.Скопенков, А.Устинов

7 (10). Многочлен P ( x ) удовлетворяет условиям: $P ( 0 ) = 1 ; 2 ( P ( x ) ) = 1 + x + x^{100} Q ( x )$, где Q ( x ) – некий многочлен. Докажите, что коэффициент при $x^{99}$ в многочлене 100 ( P ( x ) + 1 ) равен нулю. Д.Звонкин

УСТНЫЙ ТУР ДЛЯ 11 КЛАССА

1. В множестве {1, 2, 3,…, 2014} выбрали подмножество A. Оказалось, что никакой квадратный трехчлен, все три коэффициента которого принадлежат A, не имеет действительных корней. Какое наибольшее число элементов могло быть в A? Г.Жуков

2. Дан треугольник ABC. Луч, проведенный из вершины B через середину AC, пересекает внешнюю биссектрису угла A в точке P. Прямая PC пересекает прямую, содержащую внутреннюю биссектрису угла A, в точке Q. Докажите, что BA = BQ. Ф.Ивлев

3. См. задачу М2349 «Задачника «Кванта».

4. В равногранном тетраэдре ABCD точки $A ', B ', C ', D '$ – центры вневписанных сфер. Докажите, что A, B, C, D – центры вневписанных сфер тетраэдра $A ' B ' C ' D '$. (Тетраэдр называется равногранным, если его грани – равные треугольники. Вневписанная сфера – это сфера, которая касается одной из граней и продолжений остальных граней.) А.Заславский

5. В белом клетчатом прямоугольнике, стороны которого больше 10, в черный цвет покрасили K клеток. Далее за ход выбирают ряд (горизонтальный или вертикальный), в котором черных клеток хотя бы 10, и красят в черный цвет все белые клетки этого ряда. После нескольких таких ходов все клетки стали черными. Докажите, что $K \ge 100$. П.Кожевников

6. Докажите, что не существует многочлена от двух переменных P ( x, y ), для которого множеством решений неравенства P ( x, y ) > 0 является квадрант { ( x, y ): x > 0, y > 0 }. Л.Стунжас

Публикацию подготовили С.Дориченко, Л.Медников, А.Семёнов