Конспект лекции А.В. Шаповалова, прочитанной школьникам 9-10 классов на московских сборах 17 ноября 2013 г.
www.ashap.info
Стартовая задача. Мозаика состоит из набора плоских прямоугольников. Все их можно уложить в один слой в одну прямоугольную коробку (так, что их стороны параллельны сторонам коробки). В бракованном наборе у каждого прямоугольника одна из сторон оказалось меньше стандартной. Можно ли утверждать, что у коробки, в которую складывается набор, тоже можно уменьшить одну из сторон? (С. Волченков)
Ответ. Можно.
Краткое решение. Расположим коробку вертикально, вложим в нее исходные прямоугольники и после этого уменьшим их до «бракованных» размеров. Часть прямоугольников «сползет» вниз. Если же верхняя сторона не сползёт, то не сползла упирающаяся друг в друга цепочка прямоугольников. В ней каждый прямоугольник не уменьшился по высоте. Аналогично, если нельзя уменьшить ширину коробки, есть цепочка прямоугольников, соединяющая левую и правую сторону коробки, каждый из которых не уменьшился по ширине. В цепочках можно провести ломаные, они пересекутся, и их общий прямоугольник не уменьшился. Противоречие.
А как доказать, что ломаные пересекутся, не используя теорему Жордана (о том, что замкнутая ломаная отделяет от плоскости конечную фигуру)?
Теорема (о пересечении ломаных и путей ладьи). 1) Если в квадрате проведены две ломаные, одна из которых соединяет верхнюю сторону с нижней, а вторая – левую сторону с правой, то эти ломаные имеют общую точку.
2) Если на клетчатой доске одна (хромая!) ладья прошла от верхней стороны к нижней, а другая – от левой стороны к правой, то есть клетка, через которую прошли обе ладьи.
Заметим, что утверждения равносильны. Ясно, что из 1) следует 2). Обратное верно, поскольку по контрпримеру к 1) строится контрпример к 2). Действительно, если ломаные не пересекаются, то расстояния между любыми их точками не меньше некоторого d (это верно для отрезков, а пар отрезков конечное число). Разобьем квадрат на клетки с диагональю меньше d, тогда в одну клетку не могут попасть точки разных ломаных. Ясно, что ладья может пройти от края до противоположного края по клеткам, где внутри или на границе есть хотя бы одна точка соответствующей ломаной.
Идея доказательства (2). Пусть контрпример существует. Их (для данного размера доски) – конечное число. В каждом контрпримере раскрасим клетки на пути первой ладьи в красный, на пути второй – в синий, остальные клетки – в белый цвета.
Не
белые клетки будем называть цветными.
Ситуацию, когда в квадратике 2x2
ровно три клетки – цветные одного цвета, назовем уголком.
Среди контрпримеров оставим только минимальные по общему числу цветных клеток. Теперь никакой квадратик 2×2 не может быть целиком синим или красным (иначе путь можно сократить). У каждой некрайней клетки пути есть, как минимум, два соседа ее цвета (иначе ладья поворачивает назад, и клетку можно выкинуть. Кроме того, на обоих путях ходы из крайних клеток перпендикулярны соответствующим краям (иначе крайнюю клетку можно отбросить).
Хотя бы один уголок найдется: красный путь не может быть строго вертикален (иначе он перегородит синий путь), а на первом его повороте (при старте снизу) возникает красный уголок.
Усилим требования минимальности: среди оставшихся контрпримеров выберем один с минимальной суммой высот (расстояний до нижнего края) цветных клеток.
Рассмотрим в нем уголок с минимальной высотой, и докажем, что его можно перекрасить так, чтобы сумма высот цветных клеток уменьшилась. Противоречие. Значит, минимального контрпримера нет, поэтому нет и контрпримера вообще.
Задача о короле и ладье. Клетки шахматной доски nn раскрашены в синий и красный цвета. Докажите, что либо хромая ладья может пройти по синим клеткам с нижнего края на верхний, либо король может пройти с левого края на правый по красным клеткам (причем из двух возможностей всегда есть ровно одна!) (Хромая ладья каждым ходом сдвигается на одну клетку по вертикали или горизонтали)
Доказательство. Невозможность существования обоих путей одновременно легко следует из теоремы о пересечении ломаных.
Теперь, если ладья может пройти, все хорошо.
Вот идея доказательства того, что если ладья не может пройти снизу доверху, то король пройдёт справа налево. Отметим все поля, до которых ладья может дойти от нижнего края, добавив нижнюю горизонталь из отмеченных клеток. Закрасим все отрезки, отделяющие отмеченные поля от красных. Легко проверить, что из любого узла в середине доски выходит четное число закрашенных отрезков. Нечетный узел может быть только на краю. На нижней стороне их нет по построению, на верхней – поскольку ладья до верха не доходит. Остаются только левый и правый края, и на обоих нечетные узлы есть. Можно показать, что в графе из закрашенных отрезков есть путь от левого края до правого. Заметим теперь, что к каждому отрезку примыкает по красной клетке, и клетки для двух соседних отрезков имеют общую вершину (в частности, могут совпасть), поэтому король по ним доберется от левого края до правого.
Задача об электрической схеме.
а) Электрическая схема имеет вид решетки 3x3: всего в схеме 16 узлов (вершины квадратиков решетки), которые соединены проводами (стороны квадратиков решетки). Возможно часть проводов перегорела. За одно измерение можно выбрать любую пару узлов схемы и проверить, проходит ли между ними ток (то есть проверить, существует ли цепочка неперегоревших проводов, соединяющих эти узлы). В действительности схема такова, что ток проходит от любого узла к любому. За какое наименьшее число измерений всегда можно в этом удостовериться?
б) Тот же вопрос для схемы, которая имеет вид решетки 5x5 (всего 36 узлов).
в) Тот же вопрос для схемы, которая имеет вид решетки 7x7 (всего 64 узла). (А.В.Шаповалов)
Ответ а) За 8 измерений. б) За 18 измерений. в) За 32 измерения.
Идея решения. Нетрудно убедиться в том, что если перегорели только провода, выходящие из фиксированного узла, то между любыми двумя другими узлами ток проходит. Поэтому каждый узел должен быть задействован в процессе измерений, то есть число измерений не может быть меньше половины числа узлов (8 в случае а) и 18 в случае б)).
Примеры из нужного числа измерений придумайте самостоятельно. Доказательство работоспособности того или иного способа измерений обычно опирается на теорему о пересечении ломаных.
Подробные доказательства теорем и полные решения задач есть в книге Л.Медников, А.Шаповалов «Турнир городов: мир математики в задачах»
Стартовая задача: Д26.7.5. а
Пересечение ломаных или пересечение путей ладьи: Словарик.
Задача о короле и ладье Д24.3.7.
Задача об электрической схеме: 24.3.7, 24.4.7.