Квант 2017, №6 · Страницы

4

КВАНТ 2017/№6

ми данными для него не являлись аргументом в пользу их правильности: теоретическая работа должна была быть строго выверена согласно канонам школы Ландау. Когда в 70–80-е годы Алексей Алексеевич появлялся на заседании кафедры теоретической физики на седьмом этаже главного корпуса МИСиСа, он быстро разбирался с текущими делами и начиналось самое интересное – А.А. пускался в рассказы. Он был блестящим рассказчиком, которого можно было слушать часами. Казалось, мир большой физики открывался за пыльным окном, за которым только что шумел Ленинский проспект. Разговоры о физике были неотъемлемой частью нашего общения с А.А. и в холле Института физических проблем, где он традиционно назначал встречи своим студентам, и с лыжами в руках в очереди на подъемник в Бакуриани, где проходили зимние симпозиумы по физике низких температур, и на пляже во время одесских конференций по теоретической физике. Из этих разговоров, из прослушанных докладов рождались новые задачи. Алексей Алексеевич всегда был чрезвычайно внимателен к эксперименту и имел удивительное чутье на новые явления. Так, после доклада французского экспериментатора Дени Джерома об удивительных свойствах только что синтезированных органических сверхпроводников, А.А. посоветовал мне заняться исследованием природы наблюдаемой в них псевдощели. Это послужило основой для цикла работ, пригодившихся впоследствии и при изучении свойств высокотемпературных сверхпроводников. После доклада на бакуриан-

ском симпозиуме экспериментатора из Курчатовского института Валерия Егорова, посвященного аномальным транспортным свойствам сплавов $Li_{1} x Mg_{x}$ при низких температурах, А.А. обратил мое внимание на противоречия в существующем теоретическом понимании этих явлений. В результате была развита теория переходов Лифшица в сплавах при конечных температурах. Интерес к этой деятельности в связи с исследованием новых сверхпроводящих материалов, систем тяжелых фермионов, модификаций графена не иссякает и сегодня. Нужно отметить, что сам А.А., если он лично не проделал соответствующих вычислений, никогда не подписывал работу, сделанную по его идее. В 1993 году мы с А.И.Буздиным работали в теоретическом отделе Аргонской национальной лаборатории, который в то время возглавлял А.А.Абрикосов. Это было время интенсивных исследований высокотемпературных сверхпроводников, в которых все мы активно принимали участие. А.А. часто заходил к нам в кабинет и начинал обсуждать их необычные, противоречащие сложившимся представлениям традиционной теории сверхпроводимости свойства. И вновь все окружающее нас – серая военного образца годов атомного проекта мебель, освещенные неоновыми лампами стены – уходило вдаль: благодаря силе таланта и красноречию Алексея Алексеевича мы попадали в мир вихрей его имени и куперовских пар, резонансного туннелирования электронов и особенностей ван Хова, в мир, в котором он жил и был счастлив.

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

5

СВЕРХПРОВОДИМОСТЬ…

Сверхпроводимость:

история, современные представления, последние успехи

А.АБРИКОСОВ

ЯВЛЕНИЕ СВЕРХПРОВОДИМОСТИ БЫ- ло открыто голландским физиком Камерлинг-Оннесом в 1911 году. Камерлинг- Оннесу первому удалось получить жидкий гелий, и он использовал его для создания криостатов – приборов, в которых можно поддерживать очень низкую температуру. В частности, он решил проверить правильность существовавших в то время представлений о поведении электрического сопротивления при низких температурах. Измеряя сопротивление ртути, Камерлинг- Оннес обнаружил, что оно скачком обращается в ноль при температуре около 4 К. Это явление было названо сверхпроводимостью, а температура перехода в сверхпроводящее состояние – критической. В настоящее время известно много сверхпроводников с самыми разными критическими температурами, от долей градуса до примерно 100 К. Но о последних я скажу позже. Последующие исследования сверхпроводников позволили обнаружить многие их замечательные свойства. Так, оказалось, что сверхпроводимость разрушается магнитным полем. Критическое поле, при котором это происходит, зависит от температуры. Далее обнаружилось, что сверхпроводимость исчезает и в том случае, когда по образцу пропускают достаточно большой ток. Наконец, был обнаружен так называемый эффект Мейснера, суть которого заключается в следующем. Если поместить металл в не очень сильное магнитное поле и понижать температуру, то при переходе металла в сверхпроводящее состояние линии поля вытол-

Опубликовано в «Кванте» №6 за 1988 год.

кнутся из него. Последующее изучение показало, что на самом деле при таком переходе у поверхности сверхпроводника возникает небольшой слой, толщиной $10^{5} 10^{6}$ см, в котором циркулируют токи, полностью экранирующие внутренние области образца от внешнего поля. Толщина этого слоя называется глубиной проникновения. Я не буду перечислять все факты, свидетельствующие о свойствах сверхпроводников. Их было обнаружено много. Но, тем не менее, само явление оставалось таинственным. Более того, существовало некое принципиальное обстоятельство, которое, как казалось, делало сверхпроводимость невозможной. В 1937 году П.Л.Капица открыл явление сверхтекучести жидкого гелия – его способность протекать по узким капиллярам без всякого трения. Через четыре года Л.Д.Ландау сумел объяснить это явление. В теории Ландау был выведен так называемый критерий сверхтекучести, согласно которому вязкость могла возникать при движении со скоростью, превышавшей некоторую критическую. Опишу это качественно. Торможение гелия означает изменение его энергии и импульса. Однако жидкий гелий является квантовой жидкостью и может менять энергию и импульс, поглощая и излучая определенные кванты, названные квазичастицами. Эти квазичастицы ведут себя в объеме тела как настоящие частицы, правда с необычной связью между энергией и импульсом. Различие между ними и обычными частицами – электронами, фотонами – заключается в том, что вне тела квазичастицы существовать не могут. В

8

КВАНТ 2017/№6

массивному сверхпроводнику не разбиться на тонкие слои нормального и сверхпроводящего металла и не сохранить сверхпроводимость до гораздо больших полей? Ведь критическое поле для тонкого слоя выше, чем для массивного сверхпроводника. Разбиение на слои не происходит потому, что во всех чистых сверхпроводниках, состоящих из одного металла, существует особая поверхностная энергия, возникающая на границах между нормальной и сверхпроводящей фазами. Эта энергия, подобно поверхностному натяжению, стремится уменьшить поверхность границ. Микроскопическая теория объяснила ее происхождение. Оказалось, что она связана с конечным размером куперовских пар. Если уменьшать этот размер, то поверхностная энергия может изменить знак и сделаться отрицательной. Тем самым возникает естественное разделение сверхпроводников на сверхпроводники первого рода – с положительной поверхностной энергией и сверхпроводники второго рода – с отрицательной поверхностной энергией. Надо заметить, что сверхпроводники второго рода являются гораздо более распространенными, чем сверхпроводники первого рода. Мало того: любой сверхпроводник первого рода можно перевести во второй род. Для этого достаточно ввести в него некоторое количество атомов примеси или как-нибудь иначе испортить кристаллическую решетку. Электроны начинают рассеиваться на этих дефектах. Характер движения электронов меняется, и размер пар становится меньше. При достаточной концентрации дефектов сверхпроводник первого рода обязательно переходит во второй род. Теперь я немного расскажу о свойствах сверхпроводников второго рода. Поскольку поверхностная энергия в них отрицательна, то ничто не препятствует бесконечному расщеплению их объема на нормальные и сверхпроводящие области. Поэтому сверхпроводимость в них с увеличением внешнего магнитного поля вытесняется постепенно, начиная с некоторого значения поля $B_{кр1}$. Переход в нормаль-

ное состояние осуществляется в верхнем критическом поле $B_{кр2}$. Физический смысл $B_{кр2}$ заключается в следующем. В магнитном поле электроны, будучи заряженными частицами, движутся по спиральным траекториям и радиус спирали обратно пропорционален В. Если радиус спирали становится меньше размера пары, то пара уже не может существовать и разваливается. Если же внешнее магнитное поле ниже $B_{кр2}$, но выше $B_{кр1}$, то оно частично проникает в сверхпроводник. Происходит это за счет возникновения в сверхпроводнике вихревых токов. Оказывается, что эти вихри являются квантовыми объектами. Каждый из них несет квант магнитного потока. Если хотите, можно сказать, что число силовых линий, проходящих в каждом таком вихре, строго определенное. Квант потока является очень малой величиной и равен

0 ℏ e

$2 10^{15}$ Вб.

При уменьшении внешнего поля вихри расходятся и в поле $B_{кр1}$ исчезают из сверхпроводника совсем. Фактически поле $B_{кр1}$ – это то поле, при котором один вихрь еще может существовать в сверхпроводнике. Область между полями $B_{кр1}$ и $B_{кр2}$ называется смешанным состоянием. В этом состоянии сверхпроводник пронизан вихревыми нитями – миниатюрными соленоидами, расположенными в правильном порядке. В поперечном срезе они образуют треугольную решетку. Каждый вихрь имеет сердцевину, размер которой равен размеру куперовской пары; эту сердцевину можно считать областью нормального металла.

(Продолжение следует)

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

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

Этот раздел ведется у нас из номера в номер с момента основания журнала. Публикуемые в нем задачи нестандартны, но для их решения не требуется знаний, выходящих за рамки школьной программы. Наиболее трудные задачи отмечаются звездочкой. После формулировки задачи мы обычно указываем, кто нам ее предложил. Разумеется, не все эти задачи публикуются впервые. Решения задач по математике и физике из этого номера следует отправлять по электронным адресам: math@kvant.ras.ru и phys@kvant.ras.ru соответственно или по почтовому адресу: 119296 Москва, Ленинский проспект, 64-А, «Квант». Условия каждой оригинальной задачи, предлагаемой для публикации, вместе с Вашим решением этой задачи присылайте по тем же адресам. Задачи М2366 – М2369 предлагались на заключительном этапе XLIII Всероссийской олимпиады школьников по математике.

Задачи М2466–М2469, Ф2473–Ф2476

M2466. Дана равнобокая трапеция ABCD с основаниями BC и AD (см.рисунок). Окружность проходит через вершины B и C и вторично пересекает сторону AB и диагональ BD в точках X и Y соответственно. Касательная, проведенная к окружности в точке C, пересекает луч AD в точке Z. Докажите, что точки X, Y и Z лежат на одной прямой. А.Кузнецов

M2467. а) Пусть P ( x ) – многочлен степени $n \ge 2$ с неотрицательными коэффициентами, а a, b и c – длины сторон некоторого треугольника. Докажите, что числа n P

$( a ),^{n} P ( b ) и^{n} P ( c )$ также являются длинами сторон некоторого треугольника. б) Та же задача, где «трeугольник» заменен на «остроугольный треугольник». Н.Агаханов

M2468. Каждая клетка доски 100 ¥ 100 окрашена либо в черный, либо в белый цвет, причем все клетки, примыкающие к границе доски, – черные. Оказалось, что нигде на доске нет одноцветного клетчатого квадрата 2 ¥ 2. Докажите, что на доске найдется клетчатый квадрат 2 ¥ 2, клетки которого окрашены в шахматном порядке. М.Антипов

M2469 *. На доске выписаны в ряд n положительных чисел $a_{1}, a_{2},^{…} a_{n}$. Вася хочет выписать под каждым числом $a_{i}$ число $b_{i} \ge a_{i}$ так, чтобы для любых двух из чисел $b_{1}, b_{2},^{…}, b_{n}$ отношение одного из них к другому было целым. Докажите, что Вася может выписать требуемые числа так, чтобы выполнялось неравенство n - 1

$b_{1} b_{2}^{…} b_{n}$ £ $2^{2} a_{1} a_{2}^{…} a_{n}$. Ф.Петров

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

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

Задачи

Юные математики Антон, Боря, Вася, Гриша, фамилии которых Антонов, Борисов, Васильев и Григорьев, два раза пили чай за круглым столом. Первый раз Антон сидел напротив Антонова, а Боря сидел рядом с Васильевым. Второй раз Гриша сидел напротив Борисова, а Васильев – рядом с Антоном. У кого какая фамилия, если известно, что никакие двое юных математиков не сидели два раза друг напротив друга? Объясните, как вы получили ответ. Н.Чернятьев

Инопланетянин встретил мальчика и попытался угадать, как его зовут. Он перебрал такие варианты имени: Пуля, Мышь, Диск, Дыня, Липа, Морс, но не угадал. Зато оказалось, что в каждом из вариантов он угадал хотя бы одну букву (причем эта буква стоит на том же месте, что и в имени мальчика, которое тоже состоит из 4 букв).

Эти задачи предназначены прежде всего учащимся 6–8 классов. Эти задачи предлагались на Костромском областном турнире юных математиков.

Как могли звать этого мальчика? (Достаточно привести одно подходящее имя.) Е.Бакаев, Н.Чернятьев

Паша расставил по кругу в некотором порядке 15 плюсов и 15 минусов. Витя хочет заменить некоторые из знаков на противоположные так, чтобы не было двух рядом стоящих одинаковых знаков. Докажите, что в любом случае он может добиться этого, сделав не более 14 исправлений. Н.Чернятьев

У Веры есть восемь золотых шариков: четыре по 1 грамму и четыре по 2 грамма. Все шарики выглядят одинаково и на ощупь не различимы. Вера не помнит, какой из них какой. Ей нужно разделить шарики на две кучки одинаковой массы. В распоряжении Веры есть электронные весы, которые показывают вес груза, который на них положили. Но в весах практически села батарейка, и ее может хватить только на 2 взвешивания. Помогите Вере справиться с задачей. Н.Чернятьев

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

21

«КВАНТ»

ДЛЯ

МЛАДШИХ

ШКОЛЬНИКОВ

Знание – сила!

С.КУЗНЕЦОВ

ВЭТОЙ СТАТЬЕ МЫ ОБСУДИМ НЕСКОЛЬКО задач, слегка необычных с математической точки зрения. В этих задачах нам будет интересно не только истинны или ложны некоторые высказывания, но и знают ли об истинности этих высказываний персонажи, действующие в задачах. Задача 1. Илье Муромцу, Добрыне Никитичу и Алеше Поповичу за верную службу дали 6 монет: 3 золотых и 3 серебряных. Каждому досталось по две монеты. Илья Муромец не знает, какие монеты достались Добрыне, а какие Алеше, но знает, какие монеты достались ему самому. (Также Илья знает, что монет всего 6, по 3 каждого металла, и что каждому досталось по две монеты.) Требуется задать Илье Муромцу один вопрос, предполагающий ответ «да» или «нет», и по ответу на этот вопрос выяснить, какие монеты ему достались. С виду кажется, что задача неразрешима: вариантов того, какие монеты у Ильи, три (две золотые, две серебряные, золотая и серебряная), а вариантов ответа всего два, «да» или «нет». Но есть и третий возможный ответ – «не знаю». Чтобы получить его, нужно спрашивать не о монетах Ильи, а о монетах других богатырей. Однако тогда может показаться, что ответ будет всегда «не знаю»: ведь даже в условии прямо сказано, что Илья Муромец не знает о монетах Добрыни и Алеши. Тем не менее, некоторую информацию об этих монетах Илья может вычислить, зная только свои монеты. Например, если у Ильи Муромца две золотые монеты, то он знает, что осталась только одна золотая монета. Значит, ни у Добрыни, ни у Алеши не может оказаться двух золотых монет. Зато заведомо у кого-то из них обе монеты серебряные. Это соображение и приводит нас к ответу: нужно задать вопрос «Верно

ли, что у кого-то их двух других богатырей обе монеты – серебряные?» Запишем возможные ситуации коротко: буква «З» означает золотую монету, «С» – серебряную. Сначала идут монеты Ильи, потом Добрыни, потом Алеши. Например, «ЗЗ;СС;ЗС» означает, что у Ильи 2 золотые монеты, у Добрыни 2 серебряные, а у Алеши 1 золотая и 1 серебряная. На рисунке 1 возможные ситуации разделены на

Рис. 1

три группы. В каждой группе ситуации неразличимы с точки зрения Ильи Муромца: он-то видит только свои монеты. Кроме того, ситуации расцвечены: зеленым цветом обозначены те, в которых истинный ответ на наш вопрос «да»; красным – в которых ответ «нет». Теперь видно, что в средней группе, когда у Ильи золотая и серебряная монеты, есть как «красные», так и «зеленые» ситуации. Значит, Илья даже теоретически не может, опираясь на знания о своих монетах, ответить на вопрос, и он скажет «не знаю». В верхней группе обе ситуации «зеленые», и Илья, проведя такое же рассуждение, как и мы сейчас, ответит «да». В нижней группе, наоборот, обе ситуации «красные», и ответ будет «нет». Чтобы наши рассуждения имели силу, нужны два предположения о богатыре, которого мы спрашиваем: 1. Богатырь честен, т.е. отвечает на наши вопросы правдиво.

22

КВАНТ 2017/№6

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

(хотя бы у одного) из них лица перепачканы грязью. Каждый ребенок видит лица других детей, но не свое собственное. Папа спрашивает, знает ли кто-нибудь из детей, что он сам чумазый. Дети отвечают «нет». Потом папа задает тот же вопрос еще раз, потом еще раз… Поймет ли кто-то из детей, что он сам чумазый? Казалось бы, ничего не меняется, и дети всегда будут говорить «нет». Однако каждый раз ребенок получает знание о незнании других, и эта информация может помочь ему догадаться, чумазый ли он сам. Чтобы лучше понять, что происходит, рассмотрим случай, когда детей всего трое и два из них – второй и третий – чумазые, а первый чист. Кто чумазый, а кто чистый, знаем мы (и папа), но не сами дети. Поэтому нужно рассматривать все потенциально возможные ситуации, и мы будем для краткости обозначать чумазого ребенка цифрой 1, а чистого – цифрой 0: например, 010 означает, что первый и третий чисты, второй чумаз. Возможные случаи удобно изобразить в виде куба (рис. 2). Здесь две ситуации соединены красным $отрез-_{Рис.} 2$ ком, если они неотличимы с точки зрения первого ребенка (он не знает, чумаз ли он сам, поэтому не может отличить, например, 001 от 101). Зеленые отрезки соединяют ситуации, неотличимые вторым, синие – третьим ребенком. Одной вершины в этом кубе недостает: раз сказано, что чумазые есть, случай 000 невозможен. Посмотрим теперь, что изменится после первого вопроса. В ситуациях, когда чумазый ребенок ровно один (например, 100), этот ребенок сразу понимает, что он чумазый. Значит, если все ответили «нет», то эти ситуации невозможны и, что нам особенно важно, об этом теперь знают все дети! Получается картинка, изображенная на рисунке 3.

24

КВАНТ 2017/№6

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

второй и третьей второй мудрец не знает ответа, но при этом он лжец и тоже говорит «знаю». Таким образом, ответ второго мудреца не дает ни нам, ни третьему мудрецу никакой новой информации. Наконец, с точки зрения третьего мудреца неотличимы ситуации ППЛ и ПЛЛ, но его король просит назвать хотя бы одного лжеца, и он мог бы назвать себя. Значит, сказав «да, смогу», он сказал правду, что противоречит тому, что он лжец. Значит, имеет место ситуация ПЛП: первый и третий мудрецы говорят правду, второй лжец. Задачи, о которых говорилось в этой статье, относятся к ведомству модальной логики – таким образом, мы познакомились с азами этой науки.

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

Итоги конкурса 2016/17 учебного года

Лучших результатов добились следующие школьники:

Бирюлин Алексей – Москва, школа 1363, 4 кл., Павлова Деница – Болгария, София, Софийская математическая гимназия, 9 кл.

Жюри конкурса также отмечает хорошие работы следующих школьников: Антоненко Екатерина – Костромская область, деревня Кузьмищи, Кузьмищенская средняя школа, 8 кл., Данилин Иван – Москва, школа 179, 7 кл., Коноплев Максим – Москва, школа 1329, 6 кл., Красиков Антон – Украина, Киев, лицей 142, 7 кл., Олжабаев Асылбек – Казахстан, Алматы, Назарбаев Интеллектуальная школа физико-математического направления, 8 кл., Тимонина Мария – Краснодар, гимназия 92, 9 кл.

Среди команд лучший результат показали участники математического кружка Гатчинского и Лужского районов Ленинградской области (руководитель Павлов Сергей Павлович):

Иванов Олег – Луга, школа 3, 5 кл., Еремеев Семен – Гатчина, лицей 3, 6 кл., Иванов Илья – Луга, школа 6, 7 кл., Забиякин Сергей – Гатчина, школа 9, 9 кл., Лукашов Никита – Сиверская гимназия Гатчинского района, 9 кл., Морозова Екатерина – Гатчина, лицей 3, 9 кл., Сычикова Мария – Сиверская гимназия Гатчинского района, 9 кл.

Поздравляем!

Победителям и призерам будут высланы дипломы журнала «Квант», а также призы от издательства МЦНМО и фонда «Математические этюды».

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

Счетчики и расстояния в графах

П.КОЖЕВНИКОВ

ВЭТОЙ СТАТЬЕ МЫ ОБСУДИМ НЕКОТО- рые подходы к комбинаторным задачам об оценке количества операций. Вначале рассмотрим следующие задачи. Задача 1. На плоскости перегородками (единичными отрезками) выложили клетчатый квадрат 5 5 (рис.1). Какое мини-

Рис. 3

две соседние карточки (рис.3). За какое наименьшее число ходов можно всегда получить ряд из карточек, идущих слева направо в порядке возрастания? Условия задач совсем разные, но имеют единую структуру: определяется некоторая операция и ставится вопрос о наименьшем числе таких операций, которое требуется произвести, чтобы из одного положения попасть в другое. Чтобы найти подходы к решению задач, вначале обсудим более простую задачу с похожей логической структурой. Простая задача. Фишка стоит в точке 7, 7 координатной плоскости (рис.4). За

Рис. 1

мальное число перегородок нужно удалить, чтобы из каждого квадратика можно было выйти наружу (не пересекая перегородку)? Задача 2. Дана полоска 1 20, в которой каждая клетка либо белая, либо черная. За одну операцию можно перекрасить клетки в любом прямоугольнике (рис.2). За какое

Рис. 2

наименьшее число операций можно наверняка сделать всю полоску белой? Задача 3. Десять карточек с числами от 1 до 10 положили в ряд в некотором порядке. За один ход можно поменять местами

Рис. 4

один ход ее можно передвинуть на 1 вправо, влево, вверх или вниз. За какое наименьшее число ходов фишка может попасть в начало координат? Конечно, за 14: начальная клетка отстоит на 7 горизонталей и на 7 вертикалей от цели, поэтому придется сделать не менее 7 горизонтальных ходов и не менее 7 вертикальных (и конечно, есть много способов дойти до цели ровно за 14 ходов). Можно рассуждать и иначе. В каждый узел первого квадранта целочисленой ре-

39

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

шетки запишем сумму координат, тогда записанные числа представляют собой своеобразный счетчик: когда фишка находится в клетке с числом k, ей остается k ходов до цели. Счетчик можно было бы установить и без привлечения координат, просто двигаясь от цели «с конца»: ставим число 1 в узлы, из которых можно дойти до цели за один ход (I «этаж»), число 2 – в узлы, из которых можно дойти до некоторого узла с I этажа за один ход (II «этаж»), и т.д.

Упражнение 1. Девять фишек изначально заполняют правый верхний угол 3 3 шахматной доски. За один ход можно передвинуть одну из фишек на соседнюю свободную клетку. За какое наименьшее число ходов фишки может перевести в левый нижний угол 3 3?

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

Рис. 5

КРУЖОК

операцию количество водоемов уменьшается не более чем на 1. Вначале у нас 26 водоемов (включая внешний «океан»), в конце должен остаться один, поэтому количество операций не менее 26 – 1 = 25. Предлагаем читателю привести пример удаления ровно 25 перегородок (как мы теперь понимаем, в оптимальном примере достаточно только избегать удаления перегородок между двумя клетками одного и того же водоема). Таким образом, подходящий счетчик (минимальное количество ходов до цели) в задаче 1 это n – 1, где n – количество водоемов. Отметим, что переформулировка этой задачи обсуждалась в «Кванте» и раньше – например, в статье «Свяжитесь с графом» («Квант» № 4 за 2014 г.). По сути во многих задачах упомянутой статьи появляются счетчики «количество областей (или кусков, или компонент связности в графе)». Обсуждение и решение задачи 2. В конечном итоге все клетки полоски должны стать белыми, поэтому вначале может показаться, что искомый счетчик должен быть связан с количеством черных клеток. Но даже если черных клеток много, иногда можно обойтись всего одной операцией перекраски (например, для полностью черной полоски). Дело в том, что с блоком последовательных черных клеток «бороться» столь же легко, как и с одной черной клеткой. А вот устранить большое число переходов между черными и белыми блоками не так просто. Ключ к решению надо искать, рассматривая эти блоки или переходы между черными и белыми блоками. Возьмем счетчик «количество черных блоков». Рассмотрев всевозможные случаи выполнения операции перекрашивания (когда границы перекрашиваемого прямоугольника находятся внутри черного или белого блока или же попадают между блоков; некоторые случаи показаны на рисунке 6), убеждаемся, что количество черных блоков либо не изменяется, либо изменяется на 1. Конечное количество черных блоков должно равняться 0, изначальное количество черных блоков может равняться 10 – как в случае «зебры» на рисунке 7. Значит, если начальная раскраска – «зебра», то нам потребуется выполнить не менее 10 операций.

40

КВАНТ 2017/№6

Рис. 6

Рис. 7

С другой стороны, ясно, что в любой ситуации начальное количество черных блоков не более 10. И мы можем просто каждой очередной операцией брать черный блок и превращать его в белый. Не более чем за 10 операций мы получим белую полоску.

Упражнение 2. Придумайте другое рассуждение, решающее задачу, используя «перегородки» между черными и белыми блоками.

Обсуждение и решение задачи 3. Интуитивно ясно, что самая «неудобная» ситуация – когда карточки изначально лежат в порядке убывания: 10, 9, 8, …, 1. Можно вначале проследить за перемещением каждой карточки. Для того чтобы прийти к порядку возрастания 1, 2, …, 10, карточке 1 (так же, как и карточке 10) надо переместиться на 9 позиций влево (соответственно, вправо), карточкам 2 и 9 – на 7 позиций, карточкам 3 и 8 – на 5, карточкам 4 и 7 – на 3, карточкам 5 и 6 – на 1 позицию. Итого суммарное перемещение должно равняться 2(9 + 7 + 5 + + 3 + 1) = 50. За один ход две карточки перемещаются на 1, поэтому необходимо сделать хотя бы 50/2 = 25 ходов. Однако, чтобы каждая карточка переместилась именно на указанное число единиц, не допускаются перемещения «в неправильную» сторону. Например, чтобы добраться до самой левой позиции за 9 ходов, карточка 1 должна двигаться только влево. То же должно быть верно и для карточки 2: чтобы добраться до второго слева места за 7 ходов, карточка 2 должна двигаться только влево. Но одновре-

менно эти два условия для карточек 1 и 2 невыполнимы. Действительно, в начальной ситуации карточка 1 правее карточки 2, а в конечной ситуации – левее. Значит, на каком-то ходе нам нужно будет поменять местами карточки 1 и 2, при этом карточка 2 переместится на 1 вправо, т.е. сделает перемещение в «неправильную» сторону. Получается, что попытка ввести счетчик «суммарное количество перемещений» приводит к некоторой оценке на число ходов, но эта оценка неточна. Но, разбираясь в ситуации, мы поняли, что обязательно сделаем ход, состоящий в обмене конкретной пары карточек 1 и 2. Аналогично, для любой пары карточек m < n, для которой в начальной ситуации карточка n левее карточки m (такие изначально «неправильные» пары карточек называют еще «беспорядками»), когда-то должен был произойти ход, состоящий в обмене карточек m и n. Значит, чтобы из позиции 10, 9, 8, …, 1 прийти к позиции 1, 2, …, 10, должен произойти обмен каждой конкретной пары карточек. Таким образом, необходимое количество ходов не меньше количе- ства пар, т.е. не меньше чем

10 9 2

С другой стороны, при любой начальной ситуации 45 ходов хватит. Например, сначала карточку 1 обменяем со всеми карточками, которые левее нее, в результате чего она окажется на самом левом месте. Затем «двигаем» карточку 2 влево и переведем на второе место слева и т.д. Каждый раз мы уменьшаем число беспорядков на 1, значит, сделаем не более 45 ходов до конечной позиции 1, 2, …, 10. (Конечно, здесь можно оценить число ходов и без всяких беспорядков: карточка 1 сделала не более 9 ходов, после этого карточка 2 – еще не более 8 ходов и т.д., наконец, карточка 9 сделала не более одного хода, итого не более 9 + 8 + … + 1 = = 45 ходов.) Задача 3 решена. Здесь помог счетчик «количество беспорядков». Этот счетчик уже «точный»: за один ход он изменяется (увеличивается или уменьшается) ровно на 1.

Упражнение 3. Изначально 10 карточек с числами от 1 до 10 положили в ряд в порядке 2, 4, 6, 8, 10, 1, 3, 5, 7, 9. За один ход можно поменять местами две соседние карточки (как в задаче 3).

46

КВАНТ 2017/№6

11 класс 1. См. задачу 1 для 10 класса. 2. Найдите количество трехзначных номеров, записываемых цифрами от 0 до 9 включительно, у которых ровно две цифры совпадают. 3. В четырехугольник ABCD с неравными сторонами AB и CD вписана окружность, которая касается сторон AB, BC, CD и AD в точках K, L, M и N соответственно. Докажите, что прямые AC, KL и MN имеют общую точку. 4. Найдите, на какую наибольшую степень числа 3 делится произведение всех натуральных чисел от 1 до 2017 включительно. 5. Решите систему из двух уравнений $x y^{2} 2$ и $x^{2} y 2. 6.$ Для каждого значения a находят наибольшее значение функции f x a

1 sin 2 x a

3 cos 2 x, равное M a. Найдите, чему равно наименьшее значение M a.

ФИЗИЧЕСКОЕ ОТДЕЛЕНИЕ

ФИЗИКА

7 класс

1. Измерьте линейкой длину, ширину и высоту твердой коробки, например из-под обуви. Определите площадь каждой поверхности и объем коробки. Оцените ошибку каждого из проведенных измерений. 2. Измерьте длину своего шага. Пользуясь этой «мерой», определите длину пути, который вы проходите до школы или автобусной остановки. Оцените погрешность определения пути. 3. Автомобиль проходит первую половину пути со скоростью $v_{1} = 70$ км/ч, а вторую – со скоростью $v_{2} = 30$ км/ч. Определите среднюю скорость на всем пути. 4. Оперу слушают: зритель, сидящий в зале театра, и радиослушатель, находящийся возле приемника. Микрофон установлен в оркестре. Скорость звука v = 340 м/с. Скорость распространения радиоволн $c 3 10^{8}$ м/с. На каком расстоянии $s_{1}$ от оркестра должен сидеть зритель, чтобы слышать одновременно с радиослушателем, если последний находится на расстоянии $s_{2} = = 7500$ км от театра?

5. Кабина лифта опустилась с одиннадцатого этажа здания на пятый, а затем поднялась на восьмой этаж. Считая, что расстояния между этажами равны L = 4 м, определите путь и перемещение кабины.

8 класс

1. См. задачу 1 для 7 класса. 2. Катер, двигаясь по течению между двумя пунктами, затратил время $t_{1}$, а возвращаясь обратно, он затратил время $t_{2}$. Скорость катера относительно воды v. Найдите скорость течения. 3. Два поезда длиной $L_{1} = 600$ м и $L_{2} = = 800$ м идут по параллельным путям в одном направлении со скоростями $v_{1} = = 54$ км/ч и $v_{2} = 72$ м/ч соответственно. Сколько времени они проходят друг мимо друга? 4. Определите силу натяжения нити, связывающей два шарика объемом $10 см^{3}$ каждый, если верхний шарик плавает, наполовину погрузившись в воду (рис.3). Нижний шарик в 3 раза тяжелее верх- Рис. 3 него. 5. Тело массой m, упавшее с высоты H, вновь поднялось на высоту h. Какое количество теплоты Q выделилось при ударе тела о поверхность?

9 класс

1. Когда в кастрюлю с кипящей водой бросили порцию замороженных пельменей, уровень воды в ней поднялся на высоту $h_{1}$. Через некоторое время пельмени сварились и всплыли – после этого уровень воды поднялся еще на $h_{2}$. Во сколько раз плотность замороженных пельменей больше плотности кипящей воды? Пельмени не впитывают воду. 2. Имеются две одинаковые линейки размером a b c 30 2,5 0,4 см и грузик известной массы. Необходимо определить массу линейки. Для этого одна линейка устанавливается вертикально, а вторая выкладывается на первую так, чтобы линейки образовывали букву T и горизонтальная линейка не падала (рис.4). Затем берут грузик известной массы m и находят минимальные расстояния $x_{1}$ и $x_{2}$ до краев линей-

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

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

ЗАДАЧИ

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

1. 7 сольдо. Сдача тремя разными монетами составляет не меньше чем 1 + 2 + 3 = 6 сольдо. Так как этих денег не хватило на мороженое, то оно стоит не меньше чем 7 сольдо. Больше чем 7 сольдо мороженое стоить не может, иначе на два мороженых Буратино потратил бы не меньше чем 8 + 8 = 16 сольдо, но у него была всего одна монета, т.е. не больше чем 20 сольдо, и тогда он не смог бы получить 6 сольдо сдачи. Значит, мороженое может стоить только 7 сольдо. Действительно, тогда процесс платы за мороженое выглядел так: 20 – 7 = 13; 13 – 7 = 6 = 1 + + 2 + 3. 2. Синего. На первом цветном фото – 8 красных граней, на втором – 8 синих, на третьем – 8 желтых. Так как у четырех кубиков в совокупности 6 ¥ 4 = 24 грани и 8 ¥ 3 = 24, то на первом фото есть все красные грани, на втором – все синие, на третьем – все желтые. На фотографии параллелепипеда видны все четыре кубика, причем только у одного их них одна грань – видимая, а у каждого из трех остальных видны хотя бы две. На первом цветном фото есть два кубика, у которых только по одной красной грани, значит, искомый цвет не может быть красным. На третьем цветном фото есть кубик, в котором нет желтых граней, следовательно, искомый цвет не желтый. Таким образом, все видимые грани кубиков могут быть только синими. Это возможно, так как на втором цветном фото: 1) есть кубик с тремя синими гранями, имеющими общую вершину; 2) есть два кубика, у каждого из которых есть две соседние синие грани; 3) есть еще один кубик с синей гранью. Отметим, что условие задачи позволяет определить, как раскрашены все кубики. Есть кубик с тремя смежными красными и тремя смежными синими гранями, кубик с тремя смежными красными, двумя желтыми и одной синей гранью и два одинаковых кубика с тремя смежными желтыми, двумя синими и одной красной гранью. 3. Из возможных примеров приведем два:

7 6 5 3 5 6 9 2 + + + = 9, + + + = 7. 4 8 1 2 4 8 3 1

4. Да, может. Примеры – на рисунке 1.

Рис. 1

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

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

24. 182. Если какое-то качество у феи увеличивалось каждый день, то стать прежней она не могла. Значит, для того чтобы фея не изменилась, необходимо, чтобы каждое ее качество хотя бы один раз ухудшилось или все время оставалось прежним. Если фей хотя бы 183, то суммарно у них качеств 183 ◊ 2 = 366 – это больше, чем число дней в году. Но каждый день ухудшается или остается прежним только одно качество у одной феи. Значит, такого быть не могло. Покажем, что фей могло быть 182. Тогда у них 364 качества. Пусть каждый день происходит уменьшение одного из качеств, всего уменьшений 365. У 363 качеств будет по одному уменьшению за год и ровно настолько, насколько оно увеличилось за все остальные дни. А у оставшегося качества будет два уменьшения, опять же ровно настолько, насколько оно увеличилось за остальные 363 дня. Тогда феи к концу года станут такими же, какими были в его начале. 25. а) Да; б) да; в) нет. а) Обозначим вершины четырехугольника A, B, C, D. Так как AC – хорда окружности, то серединный перпендикуляр к AC делит круг пополам. Построим точку E, симметричную точке D относительно серединного перпендикуляра. В силу симметрии точка E тоже будет лежать на границе круга, а также AD = CE и AE = BD. Тогда четырехугольник ABCE – искомый: он лежит внутри круга и длины его сторон такие же, как и у исходного четырехугольника, однако их порядок изменился. (Фактически мы разрезали четырехугольник по диагонали AC, перевернули треугольник ADC и снова соединили в четырехугольник.) Обратите внимание, что мы пользовались только тем, что AC – хорда окруж-