Квант 2018, №11 · Страницы

4

КВАНТ 2018/№11

Свежий взгляд на задачу позволил ему добиться такого успеха. В работе ди Грея дистанционный граф с хроматическим числом 5 имел 1581 вершину. Сейчас уже найдены графы с 553 вершинами [6]. И есть смельчаки, надеющиеся отыскать графы с хроматическим числом 6! В настоящей статье мы расскажем о том, как получается результат ди Грея.

О пользе свежего взгляда

Посмотрим, как устроены самые простые дистанционные графы с хроматическим числом 4. Это веретено Мозеров, изобретенное братьями Лео и Вильямом

Рис. 5. Подграфы в веретене Мозеров

Рис. 6. Подграфы в графе Голомба

Мозерами, и граф Голомба. В веретене Мозеров есть два подграфа-«ромба», состоящих из двух равносторонних треугольников с общей стороной. При любой раскраске вершин такого подграфа в 3 цвета точки M, N имеют один цвет (рис. 5,а). Значит, в веретене Мозеров точки P, Q, R одного цвета, но Q и R соединены ребром (рис.5,б). Можем ли мы получить противоречие таким же способом, когда цветов не три, а четыре? Другими словами, построить такой граф, что в нем есть пара вершин, цвета которых совпадают при любой правильной раскраске. Тогда было бы доказано, что плоскость не красится в четыре цвета. Но как построить такой граф – непонятно.

Разобьем граф Голомба на два подграфа (рис.6,а). Первый из них – шестиугольник, содержащий шесть равносторонних треугольников. С точностью до перестановок цветов он красится в три цвета единственным образом (рис.6,б) Значит, вершины равностороннего треугольника A c B c C c со стороной 3 раскрашены в этом случае в один цвет. Обозначим здесь и далее $'_{3}$ – множество, состоящее из вершин равностороннего треугольника со стороной 3. При этом расположение треугольника на плоскости может быть любым. Во втором подграфе вершины такого равностороннего треугольника соединены с вершинами равностороннего треугольника со стороной 1 (рис.6,в). При раскраске в три цвета точки X, Y, Z разноцветные. Тогда A cc, B cc, C cc не могут быть одного цвета, поскольку он совпадет с цветом одной из точек X, Y, Z. Таким образом, в графе Голомба к противоречию приводит раскраска двух подграфов: первый из них гарантирует, что вершины $'_{3}$ будут одноцветными, а второй исключает такую возможность. Теперь нас интересует дистанционный граф, который невозможно раскрасить в четыре цвета. Может быть, проще искать не весь граф целиком, а подграфы, раскраска которых приводит к противоречиям? В первом подграфе некоторый набор вершин, «шаблон», при любой правильной раскраске будет одноцветным, а во втором подграфе он всегда разноцветный. Или так: если в первом подграфе найдется хотя бы один одноцветный шаблон, а во втором подграфе его невозможно покрасить в один цвет, то это непременно приведет к противоречию при раскраске плоскости. (С одной стороны, одноцветный шаблон должен где-то обнаружиться, а с другой стороны, он запрещен – ведь к любому его расположению на плоскости можно прикрепить второй граф.) Именно так и действовал ди Грей: он рассматривал в качестве шаблона треугольник $'_{3}$, как в графе Голомба, и перебирал раскраски в 4 цвета двух до-

7

ПРОРЫВ

В

ЗАДАЧЕ

О

треугольника $'_{3}$. Как построить такой дистанционный граф, чтобы на одну вершину в среднем приходилось как можно больше веретен? После ряда неудачных попыток ди Грей пришел к конструкции, при описании которой пригодится следующее определение. Определение. Пусть X, Y – некоторые множества векторов (вообще говоря, X, Y могут состоять из чего угодно, лишь бы была определена операция сложения). Суммой Минковского M = X + Y называется множество, состоящее из всех возможных сумм x + y, где x  X, y  Y (см. пример на рисунке 13).

Рис.13.

Сумма

^ v 1, v 2, v 3 `

Минковского

^ u 1, u 2 `

Иногда мы будем говорить о сумме Минковского дистанционных графов, имея в виду граф, вершины которого – сумма множеств вершин слагаемых, а ребра – всевозможные отрезки единичной длины. На рисунке 14,б совмещены «обычное» веретено Мозеров (рис.14,а) и «тройное»

РАСКРАСКЕ

ПЛОСКОСТИ

Отметим начальную точку и все точки, в которые кузнечик попадает за один прыжок. Таких точек будет 5 ˜ 6 1 31 – это вершины графа V, показанного на рисунке 14,в. Очевидно, точки P, Q, R образуют $'_{3}$. Пусть O – начало координат. При вычислении суммы Минковского V + V каждая точка будет складываться с точкой O, поэтому ^ P, Q, R `  V  V V  V V V.

Упражнение 4. а) Убедитесь, что если кузнечику разрешается сделать не более 2 прыжков, то ему доступны вершины графа W = V + V. б) Докажите, что W содержит веретено Мозеров в качестве подграфа.

Оказывается, что если отметить все точки, в которые кузнечик может попасть за 0, 1, 2 или 3 прыжка V V V и покрасить точки P, Q, R в один цвет, то правильно раскрасить остальные вершины в четыре цвета невозможно! Искомый граф построен, но компьютерный перебор раскрасок затрагивает лишь небольшую часть вершин. Ди Грей не стал спешить с публикацией и попробовал сделать построение более экономным. Опишем вариант, к которому он пришел. Пусть W c состоит из векторов из W, длина которых не превосходит 3. Пусть U – подграф V на 7 вершинах, показанный на рисунке 7.

Упражнение 5. Найдите мощности множеств W и W c.

Рис. 14. Классы эквивалентности ребер. Граф V

веретено – два веретена Мозеров с общим подграфом-«ромбом». Назовем два ребра эквивалентными, если угол между ними кратен 60q. Ребра разобьются на 5 классов, отмеченных цветом (см. рис.14,б). Сопоставим каждому ребру вектор, приписав ему произвольное направление. Теперь представим, что на плоскости сидит кузнечик и он может прыгать на единичное расстояние или в одном из этих направлений, или в любом из них, повернутом на угол, кратный 60q.

Граф H W c U имеет 1345 вершин и является подграфом V + V + V (рис.15). Если раскрасить в первый цвет три точки в вершинах $'_{3}$, выбранных из вершин U, компьютерный перебор показывает, что для раскраски остальных вершин четырех цветов (включая первый) не хватает. Проверить это утверждение без написания программы пока никому не удалось. По сравнению со многими другими «компьютерными» доказательствами объем вычислений невелик: порядка минуты счета на одном ядре современного процессора. Но и этот перебор намного превышает человеческие возможности. А вот провер-

8

КВАНТ 2018/№11

Рис. 15. Граф H на 1345 вершинах

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

но нетрудно указать и конкретный граф, обеспечивающий нижнюю оценку. Прикрепим к каждому из 52 шестиугольников в графе G по экземпляру H. При этом многие вершины совпадут, но это не должно нас беспокоить. Если не существует правильной раскраски графа в четыре цвета без учета их расположения на плоскости и отождествления вершин, то после отождествления ее тем более не будет. Полученный граф P на 20425 вершинах невозможно правильно раскрасить в четыре цвета. Как и при переборе раскрасок H, выясняется, что большую часть вершин можно отбросить. Ди Грею удалось выделить из графа P подграф P c на 1581 вершине, который также не красится в четыре цвета (рис.16). Статья ди Грея привлекла внимание энтузиастов комбинаторной геометрии к нескольким вопросам. Какое наименьшее число вершин может иметь плоский дистанционный граф с хроматическим числом 5 или больше? Нельзя ли найти граф с хроматическим числом 6 или 7, усложняя конструкцию? Существует ли доказательство новой нижней оценки, доступное для непосредственной проверки человеком? Вскоре был найден алгоритмически более простой, хотя, увы, еще менее «человеческий» способ строить графы с хроматическим числом 5 и меньшим числом вершин. Выяснилось, что для этого можно

Плоские дистанционные графы с хроматическим числом 5

В предыдущих разделах мы описали построение графа G, при раскраске которого в 4 цвета хотя бы один из треугольников $'_{3}$ будет раскрашен в один цвет, и графа H, при раскраске которого в 4 цвета фиксированный треугольник $'_{3}$ не может быть одноцветным. Из первого условия следует, что на плоскости, раскрашенной в 4 цвета, найдется одноцветный $'_{3}$, а из второго – что одноцветного $'_{3}$ на плоскости нет. Это уже означает, что

$F R^{2} t 5$,

Рис. 16. Граф P c на 1581 вершине. Не существует правильной раскраски P c в четыре цвета

Механика невидимого

Л.АШКИНАЗИ

Подчинение законам

Все, что мы видим вокруг себя, подчиняется законам механики. Вы легко назовете множество примеров, причем, в соответствии со школьным курсом физики, эти примеры можно разделить на несколько групп. Связанные с движением – небесных тел и транспортных средств; со столкновениями – в технике и спорте; с равновесием – в спорте, технике, строительстве; а также с прочностью и жесткостью вещей и сооружений. Все это мы видим вокруг себя. Но и то, что мы не видим, ведет себя тоже в соответствии с законами механики – силы и механические напряжения в материале лопаток турбин самолетного двигателя и в жестком диске компьютера описываются одними и теми же формулами. Вы вполне можете оценить эти напряжения, если сообщить вам все необходимые (кстати, какие?) параметры. Но то, что быстро вращается и поэтому должно подвергаться действию сил, создающих необходимые ускорения, – это еще далеко не все. Кровь в сосудах, воздух в легких – все это движется под действием соответствующих сил. И отдельные клетки, перемещающиеся внутри наших организмов, – тоже. Более того, у бактерий есть несколько механизмов перемещения, и они не все еще установлены. В этой же статье будет рассказано о применении механики в разнообразных электронных приборах – в счетчиках Гейгера, в механотронах, в мощных электронных лампах, в просвечивающих электронных микроскопах и сканирующих туннельных микроскопах, а также в приборах, для которых еще не придумано и названия. Причем будет рассказано не просто о том, что детали должны быть

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

прочными, а о чем-то более интересном и менее очевидном.

Счетчик Гейгера

Принцип работы этого прибора вы знаете из учебника. В данном случае нам важно, что давление газа внутри существенно меньше атмосферного, поэтому на стенки счетчика действует сила. Нейтронам и J -излучению стенки не помеха, но если мы хотим, чтобы прибор реагировал на E -частицы с относительно малой энергией и на D -частицы, то где-то должно быть сделано окно, которое будет их пропускать, и оно должно быть тонким. Попробуем оценить возможную толщину такого окна. Если атмосферное давление p, а диаметр окна d, то сила, действующая на окно, равна $p S d^{2} 4$. Примем толщину окна равной h и будем считать, что сила приходится на максимальное сечение материала окна, равное S dh. Тогда получается, что напряжение в материале составляет pd 4 h, а минимальное допустимое значение толщины равно h pd 4 V, где V – максимальное допустимое механическое напряжение в материале окна. Полагая p = 0,1 МПа, d = = 1 см, V = 0,3 ГПа, находим h = 1 мкм. Прочность здесь взята для бериллия и слюды, из которых часто и делают окошки. Окошко толщиной в 1 мкм сделать можно, но оно будет работать «на пределе» и надежность у прибора станет недопустимо малой. Поэтому окошко делается толщиной в несколько микрон. На фото 1 и 2 показаны два счетчика Гейгера – с окошком из бериллия и из слюды. Поскольку слюда прозрачна, на окошко положена кнопка – чтобы сделать наглядным присутствие окошка. В данном случае механические свойства материала окна прямо определяют возможности прибора. Чем прочнее материал окна, тем оно может

11

МЕХАНИКА

НЕВИДИМОГО

Окно для энергии

Фото 1. Счетчик Гейгера с окошком из бериллия

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

Фото 3. Электронно-вакуумный прибор с окошком из слюды

Фото 2. Счетчик Гейгера с окошком из слюды быть больше – это увеличивает чувствительность прибора или тоньше – это расширяет диапазон энергий регистрируемых частиц в сторону меньших энергий. Потому что чем меньше энергия, тем меньше глубина проникновения частицы в материал. С этой проблемой мы скоро встретимся – в электронном микроскопе. А пока что вернемся к окнам.

это обычно керамика (фото 4). Вытянутая вдоль волновода форма керамики (верхний объект на фото 4) используется для уменьшения отражения электромагнитной волны. Кстати, насчет того, что «снаружи присутствует атмосфера». Когда начались полеты в космос, некоторые вздохнули облегченно – проблемы с созданием вакуума в электронных приборах и выводом энергии решены! Ан нет: оказалось, что

12

КВАНТ 2018/№11

Фото 4. Электронно-вакуумный прибор с керамическим окошком вакуум в ближнем космосе гораздо хуже того, который должен быть в электронном приборе (от $10^{7}$ до $10^{15}$ атм), и баллон прибору все равно нужен. Про Луну и Марс и говорить не стоит – вокруг Луны летает пыль от ударов о ее поверхность микрометеоритов, а что происходит на Марсе, знаете сами. Или посмотрите в учебнике или интернете. Так что в вакуумных приборах чистота, как в дальнем космосе.

Опять окно – для микроскопа

В просвечивающем электронном микроскопе электронный пучок должен распространяться, не рассеиваясь, поэтому в приборе нужен вакуум. И пучок должен проходить через наш образец насквозь – поэтому образец обязан быть тонким. Причем образец не должен портить вакуум, а вакуум не должен портить образец. Первая проблема решается легко: образец маленький, и то, что он выделяет, насосы микроскопа откачают, а со второй проблемой дело обстоит сложнее. Из-за этого в электронном микроскопе нельзя просто так исследовать биообъекты, например живые клетки, – вода мгновенно испаряется, и клетка гибнет.

Однако не будем затрагивать биологию, а обратим свое внимание на компьютеры, роутеры, камеры, смартфоны и прочие гаджеты. Во всех них есть источник энергии – батарейка или аккумулятор. Рассказывать, как и почему важен запас энергии, не надо – это знает каждый, кто срочно искал, куда бы воткнуть зарядное устройство. Поэтому исследования в области улучшения параметров аккумуляторов ведутся непрерывно. Очень важно, например, понять, как изменяется в процессе заряда и разряда аккумулятора структура его материалов. Возникает нетривиальная задача: сделать аккумулятор толщиной в микроны, чтобы пучок прошил его насквозь. Но это еще не все – в аккумуляторе есть электролит, а в вакууме он (как и жидкость из клетки) мгновенно испарится, и аккумулятор (как и клетка) погибнет. Решение нашла группа под руководством А.М.Абакумова (МГУ, Сколтех) – в их приборе электронный пучок проходил через окно толщиной в доли микрона, сделанное из соединения $Si_{3} N_{4}$. Торможение электронов в твердом теле зависит от концентрации в нем своих электронов, поэтому пробег тем больше, чем меньше атомные номера элементов, из которых состоит преграда. Заметьте, что Si, N, Be и то, из чего состоит слюда, чаще всего мусковит $KAl_{2} > AlSi_{3} O_{10}$ @ $OH_{2}$, это все верх Периодической таблицы. Разумеется, важно еще, можно ли из такого материала сделать микронную пластинку, какова будет ее прочность и как ее соединить с остальным корпусом. По сравнению со счетчиком Гейгера в случае электронного микроскопа проблема немного облегчается тем, что от площади окна чувствительность метода не зависит, поэтому окно можно сделать поменьше. Но, с другой стороны, в счетчике важно, чтобы частица просто попала внутрь, а в микроскопе важно еще, чтобы электронный луч не рассеивался в материале окна.

Выпусти электрон на волю

Пробег электрона в веществе зависит от количества встреченных по дороге электронов. Но оно зависит не только от атом-

13

МЕХАНИКА

ного номера элементов, а еще и от концентрации атомов в пространстве. Поэтому в атмосфере, т.е. в газе, пробег электронов должен быть относительно велик. Действительно, в воздухе при нормальных условиях и при энергии электронов 20 кэВ их пробег составляет около 2 см, а при энергии 20 МэВ – 100 м. Этот диапазон энергий примерно соответствует энергиям электронов при E -распаде. То, что электроны могут преодолевать заметные расстояния в воздухе, наводит на мысль о возможности их применения для инициирования химических реакций, для обработки материалов, для сварки и т.д. Действительно, такие возможности имеются. Однако, для того чтобы ими воспользоваться, надо сначала отделить электроны от прочих компонентов вещества, потом ускорить, т.е. сообщить им энергию. Добыть электроны можно посредством термоили автоэлектронной эмиссии (с этим мы еще встретимся) из твердого тела или жидкости, а можно извлечь их из плазмы газового разряда. Ускорять электроны удобно в вакууме, и тут же возникает проблема выпуска электронного потока в атмосферу. Естественно, выпускают пучок через фольгу из титана (Ti) толщиной в десять и более микрон. Поскольку пучок изначально ускоряется до энергий в сотни килоэлектровольт, его пробег в титане составляет величину порядка сотен микрон, поэтому фольга толщиной в десятки микрон хотя и будет перехватывать часть пучка и греться, но большая часть пучка пройдет через фольгу. Применение именно титана, а не, скажем, бериллия связано с доступностью фольги из титана – она намного дешевле. А что произойдет при попытке пропустить поток электронов через слюду, при том что слюда все-таки перехватит часть электронов, подумайте сами. А пока обратимся к микроскопам – но к другим.

Сколько атомов может поместиться на острие иглы?

Если спросить вас, что такое микроскоп, вы ответите, что это нечто такое, посредством чего мы видим что-то маленькое,

НЕВИДИМОГО

которое иначе не увидеть. Это правильно, но мы получаем информацию не только при помощи зрения, почему же микроскоп в этом смысле дискриминировали? А если он сообщит нам какую-то информацию о маленьком объекте не в виде оптического сигнала? Ограничение связано только с традицией, мы привыкли «видеть» объекты – их расположение, форму, рельеф поверхности и ее «оптические» свойства, т.е. цвет, коэффициент отражения, блеск и т.д. Перечисленные параметры не независимы, они связаны сложно и интересно; например, подумайте, что такое «блеск» и от чего он зависит. Но сейчас нам важно другое: каким бы способом микроскоп не получал информацию об объекте, он должен представить ее в виде картинки, на которую мы посмотрим. Картинка эта плоская, но часто создающая у нас в мозгу объемное изображение; возможен и микроскоп, который создает настоящее объемное изображение. А вот на этап, как говорится, «визуализации» надо посмотреть внимательнее. Ибо то, что нам показывает микроскоп, а именно расположение, форма, поверхность объекта, далеко не всегда то, что мы бы увидели, если бы объект увеличился в миллион или миллиард раз. Например, потому, что в области нанометров изменяется смысл понятий «форма» и «поверхность», а понятия «цвет» и «блеск» вообще пропадают. Даже когда привычный электронный микроскоп (человек работает с ним с 1931 года) показывает нам картинку, надо понимать и помнить, как он ее получал и преобразовывал. (Если мы вообще хотим что-то понять, а не просто поахать и поохать.) Ионный проектор – вещь, в принципе, простая. Поместим в вакуум металлическую иглу и подадим на нее высокое напряжение. Рядом с острием напряженность поля такова, что оставшиеся в вакууме атомы газа ионизируются, а ионы ускоряются полем, летят до люминесцентного экрана и создают изображение. Ионизация происходит тем чаще, чем выше напряженность поля, а она выше рядом с отдельными атомами, торчащими из ост-

14

КВАНТ 2018/№11

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

Вакуумный пробой

Когда говорят об электрическом пробое диэлектрика, имеется в виду следующее. Берем кусок диэлектрика, прикладываем к нему электрическое напряжение и начинаем это напряжение увеличивать. Идеальных диэлектриков не бывает, поэтому появляется ток – поначалу маленький. А раз есть ток и напряжение, значит, есть мощность. Если мощность умножить на время, получим энергию – значит, в диэлектрике должно что-то происходить. И действительно, в какой-то момент ток скачком возрастает, диэлектрик перестает быть диэлектриком. Причем что-то происходит с самим материалом диэлектрика, с веществом. Но в вакууме вещества нет! И то, что происходит при вакуумном пробое, может происходить только с материалом

электродов. А как материал электродов попадает в зазор? Собственно, путь для этого один – испарение и заполнение парами материала электродов вакуумного зазора. А уж в этом паре происходит пробой, зажигается разряд (если хватает мощности, горит дуга), прибор разрушается. Осталась мелочь – понять, кто испаряет материал электрода. Для этого есть два механизма. Первый механизм состоит в следующем. При высокой напряженности поля начинается автоэлектронная эмиссия одного из электродов. Вылетевшие из него электроны достигают противоположного электрода и выделяют на нем свою энергию. Напряженность поля выше всего на остриях, вот почему полируют электроды высоковольтных вакуумных конденсаторов. Второй механизм таков: электрическое поле отрывает кусок материала от электрода (поскольку его поверхность заряжена), этот кусок летит через зазор, всю дорогу ускоряясь (второй закон Ньютона в действии), и отдает свою энергию другому электроду, а далее – нагрев, испарение и пробой в парах. Поэтому электроды стараются делать из прочных металлов. Между прочим, вакуумные конденсаторы – далеко не единственная и даже не основная ситуация, когда мы имеем вакуум и высокое напряжение. Так происходит почти во всех мощных электровакуумных приборах – а это и космическая связь, и радиолокация, и ускорительная техника, и телевидение… Даже токамак без таких приборов не заработает!

Еще два микроскопа: сканирующий туннельный и атомно-силовой

Преимущество этих двух микроскопов в том, что им не нужен вакуум, который разрушает многие интересные объекты (например, биологические). Если поднести к поверхности объекта на маленькое расстояние иглу и подать на нее напряжение, между иглой и поверхностью (если она хотя бы плохой, но проводник) начнет протекать ток – тот самый автоэлектронный ток, с которого иногда начинается вакуумный пробой. Чем игла острее, тем

15

МЕХАНИКА

выше пространственное разрешение, и оно может достигать десятых долей межатомного расстояния в решетке! Возникающий ток очень сильно зависит от расстояния между поверхностью и иглой, и мы можем измерить это расстояние с высокой точностью. Но расстояние до чего именно – мы ведь ни в каком смысле не касались атомов? Это будет как раз «расстояние до электронов», т.е. мы получим профиль электронной плотности над поверхностью. Пример для кремния показан на фото 6.

Фото 6. Профиль электронной плотности над поверхностью кремния

Но, как вам известно, между атомами действуют силы – притяжения на большом расстоянии и отталкивания на малом. Атомы в молекуле располагаются в среднем на таком расстоянии друг от друга, когда сумма этих сил равна нулю. Поэтому, если мы будем подводить иглу к поверхности, на нее начнет действовать сила. Эту силу измеряют по изгибу «кантилевера» – балки, на которой закреплена игла. А это как раз и есть механика, причем основы теории изгиба балок заложили не абы кто, а Эйлер и Бернулли в XVII–XVIII веках. Заметим, что атомно-силовые микроскопы XXI века работают хитрее. Они приближаются к поверхности, слегка вибрируя, а на параметры этих колебаний и влияют силы, действующие на подползающую к поверхности иглу… Вот это уже современная механика на самом переднем крае наук о поверхности, как сейчас модно говорить – нанонаук. О них мы еще поговорим.

НЕВИДИМОГО

Механотрон

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

Фото 7. Механотрон

16

КВАНТ 2018/№11

ном анодном напряжении. Соответствующая лампа называется «механотрон» (фото 7), ее стеклянный баллон спаян с металлической рамкой, в рамку впаяна мембрана (ее край виден на снимке), а к мембране изнутри и прикреплен анод. При нажатии на мембрану анод перемещается. Параметры лампы как преобразователя силы в ток зависят от жесткости мембраны, а как преобразователя перемещения в ток – не зависят. Понимаете, почему это так?

Изотопный мотор

Один из экзотических источников электроэнергии – изотопная батарея. Простейший вариант – конденсатор в вакууме, от его пластин сделаны выводы, на одну из пластин нанесен E -активный изотоп. Электроны вылетают, попадают на противоположную пластину и через нагрузку возвращаются обратно. А что происходит, если нагрузка не присоединена? Представим себе ситуацию, когда внешней нагрузки нет, но зато одна из пластин сделана гибкой. Тогда по мере увеличения заряда на ней эта пластина начнет изгибаться, и, если она сумеет коснуться другой пластины, конденсатор разрядится, пластина выпрямится, и все начнется сначала. Параметры такого мотора зависят, естественно, от энергии электронов и их тока, от геометрии системы (размеров пластины и зазора) и параметров материала (модуля Юнга). Можете на досуге попробовать решить эту задачу. Вполне возможно, что когда-нибудь такие микроили, скорее, нанодвигатели будут применяться. Тем более, что начали появляться идеи использования этих движений для генерации электроэнергии – например, сделав пластину из сегнетоэлектрика. Впрочем, обычная изотопная батарея и так уже является источником электроэнергии.

Нано: электроника и трение

Законы физики одинаковы на всех уровнях – от межатомных расстояний в твердом теле, до межгалактических у нас над головой. Но проявляются они по-разному. И то, на что мы привычно не обращаем

внимания, размышляя о процессах в твердом теле и при контакте твердях тел, становится определяющим в космосе – например, гравитация. А что-то остается столь же важным – например, диффузия в твердим теле и диффузия излучения в звездах. Правда, это диффузия чего-то другого… Опускаясь в мир нанорасстояний, мы не должны забывать про механику, но относительная роль разных ее аспектов может измениться. Простейший пример: объем тела зависит от его линейных размеров в кубе, а поверхность – в квадрате, поэтому роль поверхностных эффектов, например трения, возрастает. И вообще, начинает происходить странное: незаряженные поверхности притягиваются, звук передается через вакуум, иначе передается тепло, возникает бесконтактное трение… Но не спешите выкидывать школьные учебники. Все это становится существенным только на расстояниях, сравнимых с межатомными, и только тогда, когда вы займетесь Серьезной Физикой.

Тут продвинутый школьник…

…который днюет не выпуская из рук кодификатор ЕГЭ, а ночует в обнимку с университетским курсом физики, спросит: а зачем мне было это читать? Я это и так все знаю. Ну, почти все… На это есть два ответа – один обидный, а другой – по существу. Обидный ответ вот: это вам так кажется, что знаете. А преподаватель задаст два-три вопроса, и вы сами поймете, что умение делать умные глаза и кивать в нужных местах – это не знание. Ответ по существу вот: написано это было мною, а прочитано вами для того, чтобы вы поняли – мир не делится на механику, термодинамику, электричество и далее по списку. Физику надо знать всю. Точнее – всю ширину, а в глубину – в пределах школьного, потом и серьезного университетского курса. А электронные приборы – еще не самое страшное. Исследование элементарных частиц и поведение звезд и галактик – так и там рулит Ньютон. Прямо из своего XVII века.

ЗАДАЧНИК «КВАНТА»

Задачи по математике и физике

Этот раздел ведется у нас из номера в номер с момента основания журнала. Публикуемые в нем задачи нестандартны, но для их решения не требуется знаний, выходящих за рамки школьной программы. Наиболее трудные задачи отмечаются звездочкой. После формулировки задачи мы обычно указываем, кто нам ее предложил. Разумеется, не все эти задачи публикуются впервые. Решения задач по математике и физике из этого номера следует отправлять по электронным адресам: [email protected] и [email protected] соответственно или по почтовому адресу: 119296 Москва, Ленинский проспект, 64-А, «Квант». Условия каждой оригинальной задачи, предлагаемой для публикации, вместе с Вашим решением этой задачи присылайте по тем же адресам. Задачи М2534-М2537 предлагались на XL Турнире городов.

Задачи М2534–М2537, Ф2541–Ф2544

M2534. На острове живут рыцари, лжецы и подпевалы; каждый знает про всех, кто из них кто. В ряд построили всех 2018 жителей острова и попросили каждого ответить «Да» или «Нет» на вопрос: «На острове рыцарей больше, чем лжецов?» Жители отвечали по очереди и так, что их слышали остальные. Рыцари отвечали правду, лжецы лгали. Каждый подпевала отвечал так же, как большинство ответивших до него, а если ответов «Да» и «Нет» было поровну, давал любой из этих ответов. Оказалось, что ответов «Да» было ровно 1009. Какое наибольшее число подпевал могло быть среди жителей острова? М.Кузнецов

M2535. Требуется записать число вида 77…7, используя только семерки (их можно писать и по одной, и по нескольку штук подряд), причем разрешены только сложение, вычитание, умножение, деление и возведение в степень, а также скобки. Для числа 77 самая короткая запись – это просто 77. А существует ли число вида 77…7, которое можно записать по этим правилам, используя меньшее количество семерок, чем в его десятичной записи? С.Маркелов

$М2536^{*}$. Изначально на белой клетчатой плоскости конечное число клеток окрашено в черный цвет. На плоскости лежит

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

$М2537^{*}$. На числовой оси отмечено бесконечно много точек с натуральными координатами. Когда по оси катится колесо, каждая отмеченная точка, по которой проехало колесо, оставляет на нем точечный след. Докажите, что можно выбрать такое действительное R, что если прокатить по оси, начиная из нуля, колесо радиуса R, то на каждой дуге колеса величиной в $1 ^\circ$ будет след хотя бы одной отмеченной точки. И.Митрофанов

Ф2541. С вершины горизонтального цилиндра без начальной скорости скатывается небольшой обруч (отношение радиуса обруча к радиусу цилиндра – малая величина). Коэффициент трения между поверхностями цилиндра и обруча P 1. При

24

КВАН T 2018/№11

Отсюда искомые величины сопротивлений резисторов будут иметь вид

Таблица 1

X i ◊ Â R j

$R_{i} =$

$j \pi i$

 R j - X i

.

$j \pi i$

Полученную формулу будем использовать в режиме последовательного численного приближения. В нулевом приближении считаем

$R_{i} 0 = X_{i}$.

Далее вычисляем величины сопротивлений в первом приближении:

X i ◊ Â X j

$R_{i} 1 =$

$j \pi i$

 X j - X i

$j \pi i$ и во втором» приближении:

$X_{i}$ ◊ $Â R_{j} 1$

R i 2 =

$j \pi i$

$Â R_{j} 1 - X_{i}$

.

$j \pi i$

Продолжаем итерационный процесс вычислений, пока получаемые величины не перестанут значимо изменяться. В качестве примера приведем результаты расчетов при значениях сопротивлений, равных номеру резистора. В таблице 1 слева записаны значения сопротивлений резисторов кольца. Столбцы правой части таблицы содержат соответствующие приближения этих величин. Первый столбец моделирует измеренные величины, т.е. нулевое приближение. Последующие столбцы моделируют приближения возрастаю-

щего порядка. Так, четвертый столбец содержит расчетные величины сопротивлений в третьем приближении. Видно, что погрешность вычисления этого приближения уже только порядка 1,5 % (для резистора сопротивлением в 6 Ом). Число итераций, при котором достигается необходимая точность расчета, зависит от отношения величин сопротивлений резисторов кольца. Пример медленной сходимости иллюстрирует таблица 2, в которой сопротивление шестого резистора увеличено в десять раз. Дополнительно отметим следующее. В некоторых случаях итерационного расчета искомая величина сходится по спирали (завышенные и заниженные значения расчетной величины чередуются). Наш пример относится к этому варианту. Использование среднего для пары итераций позволяет построить быстрый алгоритм расчета.

Ф2532. Каково соотношение между высотой горы h и глубиной шахты H (рис.1), если периоды малых колебаний математического маятника на вершине горы и на дне шахты одинаковы? (Считайте, что Земля – однородный не вращающийся шар.)

Таблица 2

27

«КВАНТ»

ДЛЯ

МЛАДШИХ

ШК О ЛЬНИК О В

Геометрия клетчатой бумаги

А.ОНОПРИЕНКО

МЫ РАССКАЖЕМ ОБ ОДНОМ ИНТЕ- ресном сюжете, подготовленном по материалам математических кружков при Московском педагогическом государственном университете $(МПГУ).^{1}$ Обычный листочек в клетку таит в себе много неожиданностей. Мы обсудим несколько задач, построения в которых производятся на клетчатой плоскости. Как и в стандартных задачах на построение, можно пользоваться линейкой без делений, чтобы проводить прямые, но циркуль нам совершенно не понадобится. Как правило, именно циркуль, а не линейка, позволяет в задачах на построение «измерять» отрезки (не находить их длину, а строить отрезок, равный данному, например). Здесь же измерительным инструментом является сама плоскость! Заглавными буквами A, B, C, … во всех задачах обозначены узлы клетчатой бумаги. Сторону одной клетки принимаем за 1. Начнем наше путешествие с одной простой задачи-исследования. Задача 1. а) На клетчатой бумаге проведен отрезок AB, не проходящий по сторонам клеток, и отмечена точка C. Отметьте узел D такой, что AB = CD. б) Постройте все такие отрезки. Сколько их получилось? На рисунке 1 представлены разные варианты отрезков AB. Постарайтесь решить задачу для каждого из этих вариантов. Точку C можете выбирать в каком угодно узле (из нашего решения будет следовать, что ее расположение не важно).

Рис. 1

Решение. a) Построим прямоугольный треугольник по сторонам сетки, одна из сторон которого – отрезок AB (вообще говоря, это можно сделать двумя способами, но зафиксируем один из них). Затем перенесем этот треугольник в точку C. Та сторона этого треугольника, которая не идет по сторонам сетки, будет равна отрезку AB, так как треугольники равны по двум катетам. Это и будет искомый отрезок CD (рис.2,а). Это же решение годится для любого другого отрезка AB. б) Вообще говоря, в пункте а) можно было бы не строить треугольник, а внимательно рассмотреть отрезок AB. Для того чтобы попасть в точку B, мы должны от точки A пройти на 5 клеток вправо и на 2 клетки вверх (эти числа приведены для первого отрезка, для других отрезков количество клеток будет другим). Если пройти от точки C на 5 клеток в одном направлении и на 2 клетки в перпендикулярном

1 Кружки открыты с 2016 года, а в этом году они получили поддержку Департамента образования города Москвы в рамках мероприятия «Детский университет МПГУ (организация работы кружков для московских школьников на базе МПГУ)». Более подробная информация о кружках есть на сайте mathcircles.mpgu.org

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

Рис. 2

30

КВАН T 2018/№11

случай д): 6 ˜ 5 1 ˜ 2 –

2 ˜ 4 1 ˜ 4 5 ˜ 6 2 2 2

Задачи для самостоятельного решения

5. На клетчатой бумаге проведен отрезок AB, не проходящий по сторонам клеток. Постройте наибольшее число равнобедренных треугольников ABC с основанием AC. Решите задачу для двух отрезков, изображенных на рисунке 8. 6. На клетчатой бумаге проведен отрезок AB, не проходящий по сторонам клеток. Постройте угол ABC, равный 45q. 7. На клетчатой бумаге в ее узлах отмечены две точки. Постройте квадрат, для которого данные две точки являются противоположными вершинами.

Рис. 8

8. а) Опираясь на построение предыдущей задачи, постройте серединный перпендикуляр к данному отрезку. б) Как построить центр окружности, описанной вокруг данного треугольника? 9. Нарисуйте квадрат с вершинами в узлах сетки площадью: а) 10; б) 17; в) 26 клеток.

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

Мы продолжаем очередной конкурс по решению математических $задач.^{Они}$ рассчитаны в первую очередь на учащихся 7–9 классов, но мы будем рады участию школьников всех возрастов. Конкурс проводится совместно с журналом «Квантик». Высылайте решения задач, с которыми справитесь, электронной почтой по адресу: [email protected] или обычной почтой по адресу: 119296 Москва, Ленинский проспект, 64-А, «Квант» (с пометкой «Конкурс имени А.П.Савина»). Кроме имени и фамилии укажите город, школу и класс, в котором вы учитесь, а также обратный почтовый адрес. Мы приветствуем участие в конкурсе не только отдельных школьников, но и команд (в таком случае присылается одна работа со списком участников). Участвовать можно, начиная с любого тура. Победителей ждут дипломы журнала «Квант» и призы. Задания, решения и результаты публикуются на сайте sites.google.com/view/savin-contest Желаем успеха!

9. Электронные часы показывают часы и минуты. Вася подошел к часам и заметил, что сейчас на них палиндром – время выглядит как AB:BA. Он решил подождать, когда это повторится, но, просидев 4 часа, так и не увидел второго палиндрома. А сколько ему еще осталось ждать? Ю.Маркелов

10. Докажите, что любое целое число, не меньшее 12, можно записать как сумму двух составных чисел. И.Митрофанов

11. На столе лежит картонный треугольник ABC. С ним несколько раз делают следующую операцию. Выбирают его вершину, обозначим ее X, переворачивают треугольник и кладут его так, чтобы точка X попала на том же место, что и раньше, и угол X треугольника совпал со своим предыдущим положением. Обозначим такую операцию $P_{X}$. Докажите, что после последовательности операций $P_{A}, P_{B}, P_{C}, P_{A}, P_{B}, P_{C}$ треугольник займет первоначальное положение. В.Расторгуев

12. В клетки прямоугольника 2 ¥ n записывают числа 1, 2, …, 2n (в каждую клетку – по одному числу). Сначала в левую нижнюю угловую клетку записывают число 1, затем в одну из соседних клеток – число 2, потом в одну из соседних с ранее занятыми – 3 и т.д.; все последующие числа записывают в клетки, соседние с ранее занятыми. Докажите, что существует ровно $2^{n} -^{1} n$! способов заполнить таблицу. В.Расторгуев

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

Окружность десяти точек вписанного четырехугольника

ЗВЕСТНО, ЧТО В ЛЮБОМ ТРЕУГОЛЬНИ - ке середины сторон, основания высот и середины отрезков, соединяющих вершины треугольника с его ортоцентром, лежат на одной окружности, которая называется окружностью Эйлера или окружностью девяти точек треугольника. Аналогом окружности девяти точек для вписанного четырехугольника можно назвать окружность, о которой говорится в следующей задаче, предложенной в 2011 году на VII Международной Жаутыковской олимпиаде (Казахстан):

Диагонали вписанного четырехугольника ABCD пересекаются в точке K, точки M и N — середины диагоналей AC и BD соответственно. Описанные окружности треугольников ADM и BCM пересекаются в точках M и L. Докажите, что точки K, L, M и N лежат на одной окружности (все эти точки предполагаются различными). В данной статье мы покажем, что на этой окружности, в дальнейшем будем обозначать ее P, помимо точек K, L, M и N лежат еще шесть точек. Это позволяет назвать ее окружностью десяти точек вписанного четырехугольника. В дальнейшем будем использовать следующие обозначения: Z ABC – описанная окружность треугольника АВС; S X – степень $точки^{X}$ (см. [2]) относительно $Z^{ABC}$. Основная теорема. Пусть ABCD – вписанный четырехугольник (см.рисунок), M и N – середины его диагоналей, K – точка пересечения его диагоналей, О – центр описанной окружности ABCD. Пусть точки F, G, H – вторые точки пересечения

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

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

М.НСАНБАЕВ

36

КВА НT 2018/№11

Рис. 1

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

Рис. 2

Рис. 3

прикрывая в разной степени отверстия в пластиковой вставке. Можно сказать, что случайный слабый звук, попавший в микрофон, усиливается электрической системой компьютера и колонок, снова приходит в микрофон, еще проходит по тракту усиления, а одна из частот в этом звуке усиливается особенно существенно, совпадая с некоторой собственной частотой системы. При резонансе сигнал становится очень громким. Это – положительная обратная связь. Но для качественного звучания любого инструмента конструкция должна иметь и отрицательную обратную связь – для предотвращения лишних резонансов, иначе звук будет только раздражать ухо. В сущности, это предельно упрощенная модель чудесного изобретения Льва Сергеевича Термена (1896–1993), которое так и называлось «терменвокс», только в этом приборе обратная связь осуществлялась электрическим путем. Приближение руки исполнителя изменяло емкость колебательного контура в генераторе, и его частота повышалась или понижалась. Затем это переводилось в звук, и на инструменте (не прикасаясь к нему!) удавалось воспроизводить мелодии с уникальным звучанием. Короче говоря, предлагаемый опыт представляет широкое поле возможностей для школьника – например, выбирающего тему для проекта и доклада на ученической конференции.

ОЛИМПИАДЫ

XLIX Международная физическая олимпиада

В этом году Международная физическая олимпиада (МФО) проходила в Лиссабоне – столице Португалии. В соревновании участвовал 431 школьник из 87 стран. Сборную команду России представляли: Григорий Бобков – Черноголовка Московской области, Москва, школа 1589, Вячеслав Кузнецов – Москва, школа 192, Станислав Цапаев – Москва, школа 1589, Алексей Шишкин – Москва, школа 1589, Захар Яковлев – Санкт-Петербург, Академический лицей «Физико-техническая школа». Команду России возглавили преподаватели Московского физико-технического института (государственного университета) А.А.Воронов (руководитель команды), М.Н.Осин, В.А.Шевченко и Ф.М.Цыбров. Отбор кандидатов начался за год до олимпиады. Кандидатами в сборную стали более 30 десятиклассников – победителей и призеров заключительного этапа Всероссийской олимпиады школьников по физике прошлого года. Подготовка команды и отбор окончательного состава проходили в течение года на базе МФТИ и образовательного центра «Сириус». На сборах отрабатывались навыки экспериментальной работы на сложном оборудовании, изучались темы, которые не входят в школьную программу по физике, но необхо-

димы для участия в МФО. Сложившаяся за прошлые годы система подготовки включает в себя также участие в международных олимпиадах. Возможность попробовать себя в «боевых» условиях олимпиады – важный этап психологической подготовки к решающему соревнованию. Ребята участвовали в Европейской олимпиаде «Romanian Masters of Physics», в Международной экспериментальной олимпиаде по физике и в Азиатской олимпиаде по физике. На олимпиаде в Лиссабоне участникам были предложены три теоретические задачи и два экспериментальных задания. Представленные задачи отражают современное развитие науки и технологий, раскрывают связь между естественными науками. Например, в первой теоретической задаче участникам предстояло обработать данные эксперимента LIGO по обнаружению гравитационных волн. Темой третьей теоретической задачи были физика живых систем и модель роста опухоли. В эксперименте участники исследовали полевой TFT транзистор, «напечатанный» на бумаге. Максимальное количество баллов, которое мог набрать каждый из школьников, равнялось 50. Члены сборной России показали следующие результаты: Г.Бобков – 42,5 балла и золотая медаль,

Сборная команда России и ее руководители. Слева направо: А.А.Воронов, М.Н.Осин, С.Цапаев, Г.Бобков, З.Яковлев, В.Кузнецов, А.Шишкин, Ф.М.Цыбров, В.А.Шевченко

45

ОЛИМПИАДЫ

Команда России и ее руководители. Слева направо: Н.Х.Агаханов, Е.Рябов, С.Лучинин, С.Крымский, В.Петров, М.Абдрахманов, А.Герасименко, К.А.Сухов, М.Я.Пратусевич оценивалась из 7 баллов) и результаты первых 20 стран в командном рейтинге. Полная информация о результатах на международных математических олимпиадах имеется на официальном сайте олимпиады www.imo- official.org. Помимо огромного вклада каждого из наших участников, одной из причин уверенного выступления, возможно, стали некоторые изменения в системе отбора команды и работы с кандидатами в команду. В отличие от предыдущих лет, завершающий отбор команды происходил не на Всероссийской олимпиаде, а на дополнительных сборах в мае. В 2017/18 учеб-

ном году члены команды России отбирались из группы кандидатов в конкурентной борьбе по формальным показателям, которые суммировались за несколько предыдущих испытаний: зимние сборы (декабрь 2017), международная олимпиада Romanian Masters (февраль 2018), Всероссийская олимпиада (апрель 2018), майские сборы (май 2018). По сравнению с предыдущими годами было проведено несколько новых очных и дистанционных учебных мероприятий, адресованных кандидатам в команду. В разных мероприятиях по подготовке команды работала довольно большая группа математиков и педагогов (в которую

51

ЭКЗ АМЕ Н АЦИО НН ЫЕ

имя файла, удовлетворяющее всем указанным шаблонам. Регистр не важен. Справка: «*» в шаблонах имен означает любое (в т.ч. 0) количество любых символов, «?» в шаблонах имен означает ровно один любой символ. 5. Слово МУЛЬТИЗАДАЧНОСТЬ зашифровали с помощью шифра Виженера (не знакомы? Гугл в помощь!). Получилось НУФОУИРТЕААЯПСЫО. Найдите словоключ. Известно, что слово-ключ имеет отношение к обработке информации. 6. При регистрации на олимпиаду «IT- планета» команде политехников предложили выбрать для себя 5-значный номеридентификатор. Это оказалось непростым делом, так как у разных участников были совершенно разные предпочтения в мире натуральных чисел. Аркадий любил даты – например, годы, связанные с важными историческими событиями. Белла любила степени двойки. Валерий считал счастливыми для себя числа, в которых много троек. Геннадий просто любил большие числа – чем больше, тем лучше. Дмитрий тоже много что любил, но, будучи юношей практичным, он предложил вариант, который устроит всех: возводим двойку в степень, равную 1703 (год основания Петербурга), а затем возводим число 33 в степень, равную тому, что получилось перед этим, и в качестве номера берем последние 5 цифр результата. Каким в итоге оказался номер команды? 7. Когда-то давно студенты играли на лекции в «балду»: один называет букву, второй присоединяет к ней следующую, первый добавляет еще и т.п. Проигрывает тот, после хода которого получилось законченное слово, или же тот, кто сделал ход, после которого построение слова невозможно. Пример партии. Первый называет Ш (почему бы и нет?). Второй делает ШЛ (возможно много разных продолжений). Первый: ШЛА (рассчитывает на ШЛАК). Второй: ШЛАН (у него есть выигрышный вариант). Первому остается либо проиграть, назвав ШЛАНГ, либо назвать другую букву и проиграть изза непродолжаемого слова. В «балду» можно играть на любом языке. Предположим, вы оказались гостем племени Бдыщ (словарь племени приведен ниже). Если вы выиграете в «балду» у вождя племени – сохраните статус гостя, в противном случае получите

МАТЕ Р ИАЛЫ

статус завтрака. Вам предоставлено право первого хода. Какую букву следует назвать, чтобы наверняка не стать завтраком? БДЫЩ ДУ ЫЩ БАБАК АЫК КУЩА ДЫК АЫКА КЫК БДЫКА БУ БАЩ КЫ- ДАК ДЫДЫК ДА ЫКУД АЩАБЫКА КЫБЩ ЫКУБА ЫКА ЫКУКА ЫЩУБ УЩ УЩУЩ УЩУЩУЩ УКЫКА ЫЩА ДУД ДУДАК ЫЩАБАК УБО ДЫЩАБ 8. Блоха умеет прыгать по координатной плоскости, выполняя команды ВверхНа N, ВнизНа N, ВправоНа N и ВлевоНа N. Кроме того продвинутое насекомое знакомо с псевдокодом, в частности с операциями цикла. Где окажется блоха, сидящая сейчас в точке (300, 300) после выполнения описанного на рисунке 5 алгоритма?

Рис. 5

9. В ячейках А1:А10 (рис.6) цвет шрифта совпадает с цветом заливки. Формула из В1 (она видна в строке формул) с помощью

Рис. 6

автозаполнения растиражирована на ячейки В2:В10. Найдите сумму значений в ячейках А2:А10. 10. А и В – 16-разрядные целочисленные переменные без знака. С переменной А выполнили несколько операций циклического сдвига вправо, а с переменной В – несколько

52

КВ А НT 2018/№11

операций циклического сдвига влево («несколько» – это от нуля до бесконечности, у А и В «несколько» могли быть разными). С тем, что получилось, выполнили поразрядную операцию XOR (исключающее ИЛИ). Каким мог быть максимальный возможный результат этой операции при А = 34770 и В = 49877? Справка: Циклический сдвиг – операция, при которой двоичные разряды числа сдвигаются на одну позицию в указанном направлении, а «вытесненный» разряд занимает «освободившееся» место. Например, результатом циклического сдвига байта, содержащего число 13 (00001101), вправо будет число 134 (10000110), а влево будет число 26 (00011010).

Заключительный тур

1. Задуманное число (10 баллов). Задумано натуральное число, не превосходящее Х. Найдите значение Х, если сообщение «Задуманное число меньше 21» несет на 2 бита меньше информации, чем «Задуманное число больше 47». 2. Гирлянда (9 баллов). Кот Бейсик зачарованно смотрел на гирлянду из 8 светодиодов, ежесекундно меняющую свое состояние. «8 элементов с двумя состояниями… байт!» – понял продвинутый кот, и стал вслух интерпретировать состояния гирлянды как числа в формате беззнакового байта, постепенно понимая закономерность:

113, 37, 39, 35, 41, 57, 17, 85, 127… Назовите следующие 3 числа, которые произнесет Бейсик. 3. Шифровка (8 баллов). Перехвачены файлы с зашифрованными числовыми данными. Для некоторых чисел известна их расшифровка: так, 34202215731 расшифровывается как 28881637447, а 077713 – как 913507. Известно, что ключом является год некого важного события, связанного с информационными технологиями. Найдите ключ. 4. Схема раскладки яблок (15 баллов). Делфтский Яблокоед (ДЯ) по-прежнему фигурирует в задачах Политехнической олимпиады и, как и раньше, живет в двумерном стеллаже-массиве размером N на N ячеек (N – гарантированно четное). Для нормальной жизнедеятельности яблокоед должен много двигаться и хорошо питаться (яблоками, естественно). Каждые 4 дня профессор Ог-

Рис. 7

рызков выдает лаборантам схему раскладки яблок на стеллаже. В первый день лаборанты кладут схему заголовком вверх и кладут в каждую ячейку указанное количество яблок. На второй день схему переворачивают заголовком вправо и вновь раскладывают яблоки. На третий день схему кладут заголовком вниз, на четвертый – заголовком влево. За день ДЯ съедает все выложенные яблоки, оставляя на их месте огрызки. Профессор решил создать генератор схем раскладки яблок. Главное требование к схеме: через 4 дня в каждой ячейке стеллажа должен оказаться ровно 1 яблочный огрызок. Вот (рис.7) алгоритм, разработанный профессором для N=8 и заполняющий целочисленный массив из 8 строк и 8 столбцов Y[8][8] количествами яблок в каждой ячейке. Известно, что он содержит ошибки. Вам предстоит их выявить. В ответе про каждую ошибку укажите номер неверной строки и правильный вариант ее написания. 5. Минимакс (8 баллов). В выражение Max (Min (Max(, ),Max(,)), Min (Max(,), Max(,))) вместо прочерков расставили в случайном порядке пере-

53

ЭКЗ АМЕ Н АЦИО НН ЫЕ

менные A, B, C, D, E, F, G, H. Перечислите в порядке возрастания все возможные значения выражения, если A=5, B=11, C=2, D=8, E=4, F=7, G=13, H=6. 6. Кирпич-1 (5 баллов). «Кирпич размером А на В на С см (А, В, С – натуральные числа) разрезали на кубики со стороной 1 см. Внутри кирпич желтый, снаружи покрыт красной глазурью. Сколько получилось кубиков с 0, 1, 2, … и т.д. (все возмож-

Рис. 8

ные варианты) красными гранями?» Студент Вася разработал следующий алгоритм решения этой задачи (рис.8). Приведите пример входных значений, при которых программа Васи работает некорректно. 7. Кирпич-2 (20 баллов). Попробуйте решить предыдущую задачу средствами MS Excel. В качестве ответа приведите таблицу в режиме отображения формул. Исходные данные – в ячейках А2:С2 (рис.9). Значения

МАТЕ Р ИАЛЫ

Число же N формируется так: на первом шаге оно равно весу попрыгунчика V, выраженному натуральным числом; на каждом следующем шаге к нему прибавляется одно и то же число L – количество лапок попрыгунчика. Сколько существует точек плоскости, удаленных от начала координат не более чем на 10, для которых можно подобрать такие значения V и L, чтобы попрыгунчик достиг этой точки? 9. Система счисления (8 баллов). Определим функцию MinSum от двух целочисленных аргументов N и B следующим образом: это минимальная сумма цифр числа N при записи его в системе счисления с основанием, не превышающим B. Найдите количество таких N в интервале от 111 до 222, для которых MinSum (N, 16) минимальна на данном интервале. 10. Графические форматы (7 баллов). Восемь точечных рисунков одинакового размера преобразовали в формат .PNG (рис.10). Упорядочите файлы по возрастанию размера.

Рис. 10

Рис. 9

должны верно рассчитываться при любых натуральных А, В и С. Рекомендуется проиллюстрировать идею расчета блок-схемой. 8. Попрыгунчик (10 баллов). Попрыгунчик начинает движение в начале координат (оси – как в математике, а не как на экране). Траектория его движения состоит из шагов длины 1. Направление движения на каждом шаге определяется последними двумя цифрами двоичного представления числа N: 00 – вверх, 01 – вправо, 10 – вниз, 11 – влево.

Публикацию по математике подготовили И.Комарчев, А.Моисеев, А.Одинцов, С.Преображенский; по физике – Т.Андреева, С.Старовайтов; по информатике – Н.Иванова, Е.Крылова, А.Щукин

64

КВАНТ 2018/№11

Рис. 16

5. n =

$( 2 S NE )^{2} + 1 = 1,37$.

( v x B ) 6. Предмет нужно переместить ближе к линзе на ’ $d =^{2} F =^{20}$ см.

2

надо Q := 16. Вместо Y[M][K] := 2 надо Y[9– K][9–M] := 2. 5. 6, 7, 8, 11. 6. Когда хотя бы по одному из измерений размер 1. 7. Решение приведено в таблице (рис.16). 8. 45. 9. 7. 10. ДБЖЗАВГЕ.

ИНФОРМАТИКА

ОТБОРОЧНЫЙ ТУР

1. Б. 2. 450. 3. Верны 1, 2, 5, 10. 4. POSTUPI_V.VUZ. 5. БАЙТ. 6. 98241. 7. К. 8. (100, 500). 9. 17. 10. 65526.

ЗАКЛЮЧИТЕЛЬНЫЙ ТУР

1. X=52. $2. 63,^{31,} 79. 3. 1642. 4.$ Вместо Q := 8

КВАНТ

12+

НОМЕР ПОДГОТОВИЛИ

Е.В.Бакаев, Е.М.Епифанов, А.Ю.Котова, С.Л.Кузнецов, В.А.Тихомирова, А.И.Черноуцан

НОМЕР ОФОРМИЛИ

М.Н.Голованова, Д.Н.Гришукова, А.Е.Пацхверия, М.Н.Сумнина

ХУДОЖЕСТВЕННЫЙ РЕДАКТОР

Е.В.Морозова

КОМПЬЮТЕРНАЯ ГРУППА

М.Н.Грицук, Е.А.Митченко

Журнал «Квант» зарегистрирован в Комитете РФ по печати. Рег. св-во ПИ №ФС77–54256 Тираж: 1-й завод 900 экз. Заказ № Адрес редакции: 119296 Москва, Ленинский проспект, 64-А, «Квант» Тел.: +7 916 168-64-74 Е-mail: [email protected], [email protected]

Отпечатано в соответствии с предоставленными материалами в типографии ООО «ТДДС-СТОЛИЦА-8» Телефон: +7 495 363-48-86, htpp: //capitalpress.ru