Регион 9 класс

Первое решение. Между двумя моментами встречи каждый мальчик проехал половину асфальтового и половину песчаного участков, и они затратили на это поровну времени. Значит, на всю дорожку каждый из них затратил вдвое больше времени, то есть тоже поровну.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Нарисуем графики движения мальчиков по дорожке: на горизонтальной оси отмечаем время на вертикальной — положение мальчика, считая от начала дорожки.

Пусть — точки, соответствующие старту Пети, моменту, когда он перешёл с асфальтового участка на песчаный, и его финишу; пусть — аналогичные точки для Васи. Тогда графики движения мальчиков — это ломанные и при этом отрезки и горизонтальны (см. рисунок). По условию, середины отрезков и совпадают, откуда — параллелограмм. Аналогично, — параллелограмм. Значит, отрезки и параллельны и равны. Поэтому между моментами финиша Пети и Васи прошло столько же времени, сколько и между моментами их старта; отсюда и следует ответ.

Многоугольник, у которого площадь (измеренная в ) численно равна периметру (измеренному в см), назовём хорошим.

Заметим, что исходный треугольник — хороший: он прямоугольный с катетами см и см, поэтому его площадь равна и численно совпадает с его периметром, равным

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

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

Заметим, что в каждой вертикали и каждой горизонтали стоит ровно по одной ладье.

Покажем сначала, что все ладей не могли попасть в одну часть. Пусть — угловые клетки доски в порядке обхода против часовой стрелки. Из симметрии, и должны принадлежать разным частям, как и и Это значит, что либо и либо и лежат в одной части, а остальные две клетки — в другой.

Пусть для определённости и лежат в части I. Тогда все граничные клетки между ними также должны лежать в части I; действительно, если какая-то такая клетка лежит в части II, то в ней же лежит какой-то путь из в а в части I лежит какой-то путь из в но эти пути должны иметь общую клетку, что невозможно.

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

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

Первое решение. Предположим противное: пусть Из делимости на следует, что число

кратно Поскольку числа и

взаимно просты, получаем, что делится на Ясно, что поэтому либо

либо

В первом случае получаем

и, значит, делится на что невозможно по условию. Во втором случае имеем

то есть

Это значит, что то есть но это также невозможно по условию, ибо тогда снова делится на

______________________________________________________________________________________________________________________________________________________

Второе решение. Опять же предположим противное. Поскольку делится на то и

тоже кратно то есть

при некотором натуральном Иначе говоря,

Значит, делится на

По нашему предположению, С другой стороны, поскольку имеем

откуда Значит,

и потому

Теперь переписывается в виде

то есть

Но тогда

то есть делится на Это невозможно.

Обозначим окружности с диаметрами и через и соответственно. Заметим, что точка лежит на отрезке

Пусть прямые и пересекают в точках и соответственно. Поскольку — диаметр имеем В прямоугольном треугольнике отрезок — высота, поэтому

С другой стороны, поскольку имеем

Итак,

то есть точки и лежат на одной окружности

Пусть теперь прямая пересекает окружности и в точках и соответственно (точка лежит на отрезках и ). Тогда

поскольку — центр окружности С другой стороны,

что следует из того, что — высота в прямоугольном треугольнике Значит,

то есть Но точка отлична от и так как не лежит на значит, окружности и имеют три общих точки то есть они совпадают. Поэтому лежит на что и требовалось доказать.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание 1. Решение можно было бы завершить многими разными способами. Например, равенства

означают, что точки и лежат на одной окружности Тогда либо окружности и совпадают, либо это три разных окружности. Во втором случае радикальные оси пар этих трёх окружностей должны пересекаться в одной точке или быть параллельными; но эти радикальные оси — это прямые и и для них эти утверждения неверны.

Рассуждение выше имеет недостаток: оно не проходит, когда точки и лежат на одной прямой. Этот случай легко разобрать отдельно (тогда проходит через центр окружности

______________________________________________________________________________________________________________________________________________________

Замечание 2. Существуют и другие решения, идейно схожие с приведённым выше. Например, можно рассуждать так.

Пусть лучи и пересекают повторно в точках и Пусть Тогда

откуда Тогда — высота в прямоугольном треугольнике, и

С другой стороны, если прямая пересекает в точках и то

Однако, как нетрудно проверить, на отрезке есть только две точки такие, что и это точки и Значит, что и требовалось доказать.

Докажем, что Все числа с доски разбиваются на цепочки чисел вида

так, что числа из разных цепочек не отличаются ровно на 1. Такое разбиение нетрудно построить, соединив любые два числа, отличающиеся на 1, отрезком и рассмотрев полученные ломаные.

Пусть получилось цепочек, в которых …, чисел соответственно (некоторые цепочки могут состоять из одного числа). В цепочке из чисел есть ровно пара чисел, отличающихся на 1. Поэтому общее количество единиц в тетрадке равно

откуда Значит, в одной из цепочек не меньше, чем чисел, то есть не меньше 8 чисел. Разность наибольшего и наименьшего чисел в такой цепочке не меньше

Осталось привести пример, в котором Такой пример дают, например, числа

Действительно, в этом примере и ровно для первых 85 из этих чисел в наборе есть число, на единицу большее.

Первое решение. Совершим гомотетию с центром и коэффициентом При этой гомотетии точки и переходят в и соответственно; пусть точки и переходят соответственно в и Тогда достаточно доказать, что четырёхугольник описан. Мы докажем, что он описан около вписанной окружности треугольника Три стороны четырёхугольника уже касаются поэтому достаточно доказать, что её касается

Пусть — центр Тогда поэтому и симметричны относительно Далее заметим, что

Но — медиана в прямоугольном треугольнике поэтому Значит, Значит, и прямые и также симметричны относительно поскольку одна из них касается то и другая тоже. Это и требовалось доказать.

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Пусть прямая пересекает прямую в точке Как и в решении выше, получаем, что

откуда

Мы докажем, что окружности, вписанные в треугольники и совпадают (тогда это и будет вписанная окружность четырёхугольника ). Поскольку обе окружности вписаны в угол для этого достаточно показать, что они касаются прямой в одной и той же точке. Как известно, расстояния от до точек касания этих окружностей с равны соответственно

Значит, нам надо доказать, что

или что

Обозначим полупериметр треугольника через и пусть Имеем

С другой стороны,

откуда и следует искомое равенство.

_________________________________________________________________________________________________________________________________________________________________________________

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

Первое решение. Докажем сначала, что удовлетворяет требованиям задачи. Заметим, что Следовательно,

Значит, осталось доказать неравенство

Возведем это неравенство в квадрат; оно примет вид

После сокращения слева останется сумма корней, а справа — Но любой из корней не меньше, чем действительно, например,

Отсюда и следует требуемое.

Осталось доказать, что при любом неравенство выполнено не всегда; достаточно это сделать при Пусть при Положим и Тогда однако

______________________________________________________________________________________________________________________________________________________

Второе решение. Приведём другое доказательство того, что подходит. Для этого докажем, что если — наибольшее из чисел то верно даже неравенство

Обозначим заметим, что поэтому Левая часть неравенства выше переписывается как

Значит, нам достаточно доказать, что

Возводя это неравенство в квадрат, получаем

после сокращения подобных слагаемых получаем, что нам достаточно доказать неравенство

Наконец, это неравенство вытекает из неравенства (поскольку ) и

где мы применили неравенство о средних.

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

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

После действий Пети найдётся слой, в котором включено лампочек — назовём один такой слой главным. Пусть — набор из переключателей на красной грани, связанных со включёнными лампочками в главном слое. Мы докажем, что Вася сможет погасить все лампочки, использовав с красной грани ровно эти переключатели.

Запустим несколько другой процесс, начиная с того же исходного положения. Пусть — набор переключателей с красной грани, использованных Петей, а — набор использованных им переключателей с некрасных граней, связанных с главным слоем. Пусть Петя применит и , а затем Вася применит . После действий Пети в главном слое будут гореть те же лампочек, что и раньше, а значит, после действий Васи все лампочки в главном слое будут погашены. Если теперь Вася применит в каждом из остальных слоёв наборы переключателей с некрасных граней, аналогичные , то все лампочки будут погашены.

Пусть теперь Петя применит все остальные переключатели (с некрасных граней!), которые он применял исходно, а Вася применит их ещё по разу. Все лампочки по-прежнему будут погашены. При этом в новом процессе Петя применил ровно те же переключатели, что и в исходном, а Вася использовал лишь переключатели набора с красной грани (и какие-то — с остальных граней). Значит, если в исходном процессе Вася совершит те же действия, которые он сделал в новом, он добьётся требуемого.

Пусть По условию, где Запишем разность:

Рассмотрим пары такие, что и

Тогда:

Подставим и в

Это выражение является квадратом натурального числа

Для целочисленности и требуется, чтобы числители в выражениях для и делились на 2. Поскольку имеет ту же чётность, что и а фиксировано, условие выполняется для всех целых

Пример: В этом наборе три числа делятся на 5, четыре числа делятся на 4, а общая сумма равна

Пусть — сумма цифр числа Тогда суммы цифр полученных чисел будут равны …, Три из этих сумм будут делиться на По признаку делимости на соответствующие три числа на доске также будут делиться на При этом они будут больше а значит, будут составными. Поэтому больше 6 простых чисел на доске оказаться не может.

Шесть простых чисел может оказаться даже при — например, если Петя получит, среди прочих, числа и

Во всех решениях ниже мы рассматриваем граф дружб, в котором вершины — это люди в компании, а два человека соединены рёбром, если они дружат.

Если граф — это цикл, содержащий 101 вершину, то на любых 100 вершинах ровно 99 рёбер, так что такая компания удовлетворяет условиям задачи. Осталось показать, что не существует такой компании из 102 человек (тогда и компании из более чем 102 человек тоже быть не может). Ниже мы приведём несколько различных способов сделать это; в каждом способе мы предполагаем, от противного, что такая компания нашлась.

_________________________________________________________________________________________________________________________________________________________________________________

Первое решение. Рассмотрим произвольное множество из 101 вершины и индуцированный подграф на этих вершинах, пусть в нём рёбер. Выбрасывая из этого подграфа произвольную вершину (скажем, степени ), получаем 100 вершин с нечётным количеством рёбер Значит, степень любой вершины в нашем подграфе имеет чётность, отличную от чётности то есть степени всех вершин подграфа имеют одну и ту же чётность. Но, как хорошо известно, в графе из нечётного числа вершин все вершины не могут иметь нечётную степень. Поэтому все эти степени чётны, а число рёбер нечётно.

Пусть теперь во всём графе на 102 вершинах рёбер. При выкидывании любой вершины (скажем, степени ) получается подграф с нечётным числом рёбер аналогично рассуждению выше получаем, что и во всём графе степени всех вершин имеют одинаковую чётность. Заметим, что наш граф не может быть пустым (т.е. не иметь рёбер) или полным (т.е. иметь все рёбер), иначе на любых 100 вершинах будет либо либо рёбер, то есть чётное количество. Тогда найдётся вершина, соединённая хоть с какой-то другой вершиной, но не со всеми. Иначе говоря, есть вершины и такие, что соединена с но не с Степени вершин и в исходном графе одной чётности, поэтому после удаления они будут иметь разную чётность. Это невозможно по доказанному выше.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Существует всего способов выбросить две вершины из 102, оставив 100. Пронумеруем эти способы числами от 1 до Пусть — количество рёбер на оставшихся 100 вершинах в -м способе; по предположению, все числа нечётны, а значит, нечётна и их сумма (поскольку число нечётно).

С другой стороны, рассмотрим любое ребро Это ребро учтено в числе ровно тогда, когда вершины и не выброшены в -м способе, то есть когда выброшена какая-то пара из оставшихся 100 вершин. Это происходит в способах. Итак, каждое ребро учтено в чётное количество раз, поэтому должно быть чётным. Противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

Третье решение. Назовём вершину чётной, если её степень чётна, и нечётной иначе. Рассмотрим два случая.

Случай 1. Пусть общее количество рёбер в графе нечётно. Тогда, выкидывая любую пару вершин, мы должны выкинуть из графа чётное число рёбер (чтобы осталось нечётное число). С другой стороны, если мы выкидываем вершины со степенями и то число выкинутых рёбер равно если эти вершины не соединены рёбром, и если соединены. Отсюда следует, что вершины одинаковой чётности всегда не соединены рёбром, а вершины разной чётности — всегда соединены. Значит, если в графе чётных вершин и нечётных, то чётные вершины имеют (чётную) степень а нечётные — (нечётную) степень Это невозможно, ибо

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

Записывая условие при и при получаем

и

то есть Отсюда и следует ответ.

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

Предположим, что существует Васино разбиение на домино, удовлетворяющее требованиям задачи. Если в васином разбиении какая-то из клеток …, занята вертикальным домино, то это — то же домино, что и в Петином разбиении, и из этих двух клеток нельзя добраться до остальных. Поэтому в Васином разбиении обязательно должны присутствовать домино …, Аналогично, клетки и не могут быть накрыты горизонтальными домино, поэтому они накрыты вертикальными домино и Но тогда из четырёх клеток нельзя попасть в остальные — противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

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

Раскрасим все клетки в шахматном порядке в чёрный и белый цвета, и поставим на каждом синем отрезке стрелку от белой клетки к чёрной, а на красном — от чёрной к белой. Тогда из каждой клетки ведёт ровно одна стрелка, и в неё входит ровно одна. Тогда все клетки разбились на циклы, и, если Васе удалось, то получился один цикл из всех клеток.

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

Поскольку треугольники и подобны, и потому

Достроим треугольник до параллелограмма (см. рисунок). Тогда треугольники и подобны, поэтому Наконец, поскольку и получаем

откуда и следует, что

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

Теперь докажем оценку это можно сделать несколькими способами.

_________________________________________________________________________________________________________________________________________________________________________________

Первый способ. Осталось доказать, что Любые три отмеченных точки образуют треугольник, поэтому не могут лежать на одной прямой. Считая отмеченные точки расположенными на координатной плоскости, обозначим через любую из них с максимальной ординатой. Среди оставшихся выберем точки и такие, что угол максимален.

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

_________________________________________________________________________________________________________________________________________________________________________________

Второй способ. Рассмотрим пару отмеченных точек на наибольшем расстоянии друг от друга. Тогда для любой другой отмеченной точки сторона — наибольшая в треугольнике поэтому, в частности, угол острый.

Проведя из точки лучи во все отмеченные точки, получаем, что все эти лучи различны (ибо три отмеченных точки не могут лежать на одной прямой), и каждый составляет с лучом острый угол, выражаемый целым числом градусов. Такой угол (если луч не совпадает с ) может принимать значения от до поэтому количество таких лучей не превосходит Отсюда

Положим Через обозначим сумму цифр числа Отметим простое свойство которое сразу видно, если числа и сложить в столбик.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Пусть — натуральное число, и пусть натуральное число кратно Тогда

Доказательство. Индукция по База очевидна.

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

также кратно Поэтому по предположению индукции, а тогда

______________________________________________________________________________________________________________________________________________________

Для решения задачи осталось взять такое что и заметить, что если и то делится на и, значит,

Приведём одну из возможных выигрышных стратегий для Пети. Он всё время будет делать ходы, параллельные одной из диагоналей доски (назовём её главной).

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

В результате сдвигов и бывшие вертикали, и бывшие диагонали, параллельные главной, стали наклонными рядами. При этом “вертикали” одной лесенки симметричны “диагоналям” другой. Это значит, что на каждый ход Васи Петя может ответить симметричным ходом в другую лесенку (два таких ответа показаны на рис. ).

Тогда после каждого Петиного хода ситуация на «сдвинутой» картинке будет оставаться симметричной, а значит, Петя всегда сможет сходит согласно описанной стратегии. Так как игра закончится (не более чем за ходов), в некоторый момент Васе будет некуда ходить, и Петя выиграет.

Первое решение. Назовём длиной слова количество букв в нём. Пусть — буквы алфавита. Тогда нетрудно проверить, что хорошим является слово

Осталось показать, что нет хороших слов большей длины.

Предположим, что в -буквенном алфавите существует хорошее слово длины Тогда какая-то буква (скажем, встречается в нём хотя бы три раза. Отметим её второе и предпоследнее вхождение в слово (тогда стоит не правее, чем

Любая другая буква встречается не более одного раза перед а также не более одного раза после иначе вычёркиванием можно получить запрещённую последовательность. Значит, каждая из букв встречается не более двух раз. Более того, если такая буква и встречается дважды, то одно из её вхождений стоит до а другое — после

Пусть встречается раз. Тогда между и стоят хотя бы буквы, отличных от (по одной между соседними вхождениями и все такие буквы встречаются ровно по разу. Выделим таких буквы. Остальные буквы могут встречаться максимум по два раза. Поэтому длина слова не превосходит

что противоречит нашему предположению.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Приведём другое доказательство того, что длина хорошего слова не превосходит Индукция по В базовом случае буквы в слове чередуются, и слово длины хотя бы содержит фрагмент вида из которого вычёркиванием букв можно получить Для перехода предположим, что в -буквенном алфавите есть хорошее слово длины, не меньшей Тогда какая-то буква встречается в этом слове хотя бы три раза. Предположим, что букв, встречающихся хотя бы раза, две — и Пусть, без ограничения общности, второе вхождение стоит раньше второго вхождения тогда вычёркиванием букв можно получить слово что невозможно. Значит, буква встречается в слове раз, а все остальные — максимум по два раза. Тогда длина слова не меньше, чем и не больше, чем откуда Между вторым и третьим вхождением буквы есть какая-то буква Эта буква не может встречаться в других местах: если она встречается после второго вхождения то вычёркиванием букв можно получить а если до него — то (поскольку Пусть соседи буквы различны. Тогда, удалив её из слова, мы получим хорошее слово в -буквенном алфавите (без буквы Длина этого слова будет не меньше что противоречит индукционному предположению. Если же соседи буквы одинаковы, удалим из слова и букву перед ней; тогда на этом «стыке» останутся различные буквы. Поэтому мы опять получим хорошее слово в -буквенном алфавите, длина которого не меньше, чем это опять же невозможно по индукционному предположению.