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

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

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

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

ВЭТОЙ СТАТЬЕ МЫ ОБСУДИМ НЕКОТО- рые подходы к комбинаторным задачам об оценке количества операций. Вначале рассмотрим следующие задачи. Задача 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 – хорда окруж-