Всего: 96 1–20 | 21–40 | 41–60 | 61–80 …
Добавить в вариант
Пусть все фирмы страны имеют определенный ранг, который является натуральным числом. При слиянии двух фирм рангов m и n получается новая фирма ранга (m + n). Прибыль полученной фирмы будет на m · n больше суммы прибылей фирм ее образующих. Прибыль фирмы первого ранга равна 1 д. е. Существует ли ранг, при котором прибыль фирмы будет равна 2016 д. е.?
Пусть pn — прибыль фирмы ранга n. Тогда по условию задачи
Заметим, что для любого n
Докажем, что 
Используем метод математической индукции.
1) База индукции: 
2) Индукционный переход: пусть 
Докажем, что 
Действительно, 
Следовательно, 
Для того, чтобы фирма имела прибыль равную 2016 д. е., её ранг должен удовлетворять равенству 
Последнее уравнение имеет натуральное решение n = 63.
Ответ: да, это ранг равный 63.
Алфавит состоит из n букв. Слово, составленное из этих букв, называется разрешённым, если все стоящие в нём рядом буквы различны и из него нельзя вычёркиванием букв получить слово вида abab, где буквы a и b различны. Какую максимальную длину может иметь разрешённое слово?
Докажем методом математической индукции. При 
— очевидно. В произвольном слове w от n + 1 буквы рассмотрим первую слева букву, назовём её a, если она больше не встречается в w, оставшаяся часть w является словом от n букв и по предположению индукции имеет длину не больше 
Общая длина w при этом не превосходит 
Если a встречается в w ещё хотя бы раз, то подслова, на которые a разбивает w, не имеют общих букв. Иначе, убрав всё, кроме первой a, буквы b, встречающейся в разных подсловах и второй буквы a, стоящей между этими b, получим слово abab, запрещённое условием. Пусть всего w содержит k вхождений a, оно разбивает w на k (если последняя буква w не a) или k − 1 (если последняя буква w равна a) подслов, каждое из которых использует непересекающееся с другими множество букв. Длина каждого подслова оценивается по индукции как удвоенное число использованных в нём различных букв, уменьшенное на 1. Всего в этих словах задействованно n букв, поэтому общая суммарная длина всех подслов не превосходит 
Добавляем сюда k вхождений a, получим, что длина w не превосходит 
— шаг индукции доказан.
Ответ:
| Критерии оценивания выполнения задания | Баллы |
|---|---|
| Верное решение. | 7 |
| Любой неверный ответ и попытка его доказательства. | 0 |
Попытка доказательства, опирающаяся на то, что самое длинное слово обязательно имеет вид  | 0 |
| Решение не соответствует ни одному из перечисленных выше критериев. | 0 |
| Максимальный балл | 7 |
На конференцию приехали несколько человек. Докажите, что их можно разместить в двух конференц-залах так, чтобы у каждого из них в своем зале имелось четное число знакомых (один из залов можно оставить пустым).
Проведем решение индукцией по количеству участников конференции. База индукции проверяется непосредственно.
Предположим, что для n участников утверждение задачи верно.
Пусть на конференцию приехали n + 1 участников. Если каждый из них имеет четное число знакомых, что можно оставить одну из комнат пустой и требование задачи будет выполнено. Поэтому будем считать, что некоторый участник А имеет нечётное количество знакомых B1, B2, …, B2k + 1. Попросим участника A на время удалиться с конференции. Кроме того, заставим любых двух его знакомых познакомиться между собой, если они прежде не были знакомы, и, напротив, временно прервать знакомство, если они знали друг друга. Полученную компанию из n человек можно, по предположению индукции, разместить в двух комнатах так, чтобы у каждого было четное число знакомых в своей комнате. Не умаляя общности, можно считать, что участники B1, B2, …, B2s попали в первую комнату, а B2s + 1, B2s + 2, …, B2k + 1 — во вторую (
). Теперь позовем обратно изгнанного A и подселим его в первую комнату — он будет знать
там четное число людей. При этом количество знакомых у участников B1, B2, …, B2s станет нечетным. Наконец, вернем все знакомства между Bi (
) в первоначальное состояние. Каждое приобретенное или потерянное знакомство меняет количество знакомых на единицу. Поэтому у каждого из B1, B2, …, B2s количество знакомых среди людей этого набора поменяет четность (и станет четным), а у каждого из B2s + 1, B2s + 2, …, B2k + 1 по-прежнему останется четным. У других участников, кроме A и Bi, наборы знакомых всё это время вообще не менялись. Поэтому полученное размещение всех участников по двум комнатам удовлетворяет условию задачи.
Числовая последовательность такова, что 
для всех 
Найдите x2017, если x1 = 6.
Найдём следующие члены последовательности:
Методом математической индукции докажем, что 
при всех натуральных n:
1) n = 1: 
— верно.
2) Пусть утверждение верно при 
3) 
Так как 
то 
Ответ: 
| Критерии оценивания выполнения задания | Оценка | Баллы |
|---|---|---|
| Полное решение. | + | 12 |
| Выписаны несколько первых членов последовательности. Дополнительных обоснований не приведено или приведенные обоснования неверные. Ответ верный. | +/2 | 6 |
| Выписаны несколько первых членов последовательности в виде суммы 5 и дроби. Ответ отсутствует или неверный. | ∓ | 2 |
| Решение не соответствует ни одному критерию, описанному выше. | −/0 | 0 |
| Максимальный балл | 12 | |
Для каких положительных целых n > 2 существует многоугольник с n вершинами (не обязательно выпуклый) такой, что каждая его сторона параллельна какой-либо другой его стороне?
1. Если n — чётное, то такой многоугольник существует. Достаточно взять правильный n-угольник.
2. Для n = 3 или 5 такого быть не может. Действительно, никакие две стороны в треугольнике не параллельны. Если каждая из сторон пятиугольника была бы параллельна другой стороне, мы бы нашли три параллельные стороны, при этом две из них должны были бы пересекаться. Это невозможно.
3. Для n = 7 такой многоугольник существует. Пример приведён на рисунке 1.
Докажем методом математической индукции, что для нечётного положительного числа n > 5 искомый многоугольник существует. Пусть для некоторого целого k существует k-угольник, удовлетворяющий условию задачи. Выберем вершину, в которой внутренний угол многоугольника меньше 180°. Теперь отрежем маленький параллелограмм как показано на рисунке 2. Мы получим (k + 2)-угольник, удовлетворяющий условию задачи.
Ответ: при 
и 
| Критерии оценивания выполнения задания | Оценка | Баллы |
|---|---|---|
| Полное решение. | + | 12 |
| Доказано, что при четном n такой многоугольник существует. Доказано, что и Приведен пример семиугольника, который удовлетворяет условию задачи. Доказательство, что подобный многоугольник существует при нечетных n больше 7 неполное. | +. | 10 |
| Доказано, что при четном n такой многоугольник существует. Доказано, что и Приведен пример многоугольника с нечетным числом сторон, который удовлетворяет условию задачи. | ± | 9 |
| Доказано, что при четном n такой многоугольник существует. | +/2 | 6 |
| Верно рассмотрены случаи при некоторых n. | ∓ | 2 |
| Решение не соответствует ни одному критерию, описанному выше. | −/0 | 0 |
| Максимальный балл | 12 | |
и Назовём змейкой в выпуклом n-угольнике незамкнутую, не самопересекающуюся ломаную из n − 1 звеньев, множество вершин которой совпадает с множеством всех вершин n-угольнике. Найти число различных змеек в n-угольнике. (Змейки равны, если совпадают, как геометрические места точек n-угольника. Например, число змеек в треугольнике равно 3).
1) Докажем по индукции, что число змеек, одним из концов которых является фиксированная вершина А, равно 
База при 
очевидна. Для произвольного n, имеем две возможности для звена с концом А — это стороны АВ и АС n-угольника, где В и С — соседние с А вершины. Если первое звено АХ отлично от АВ и АС, то диагональ АХ делит n-угольник на два невырожденных многоугольника с более, чем тремя вершинами в каждом, считая А и Х. Тогда второе звено змейки и все следующие, ввиду её несамопересекаемости, будут лежать в одном из них и не смогут содержать вершину другого, отличную от А и Х, что противоречит условию. Пусть первым звеном является АВ, тогда оставшиеся 
звена змейки являются змейкой с началом В в 
-угольнике, получающемся из исходного удалением треугольника АВС. По индукционному предположению, таких змеек будет 
— это в точности все змейки с крайним звеном АВ. Аналогично, змеек с крайним звеном АС тоже будет 
поэтому общее число змеек, одним из концов которых является А, будет
2) Теперь умножим 
на число вершин n и поделим пополам, так как каждую змейку мы подсчитали дважды — с каждого из её концов — всего 
Ответ:
| Критерии оценивания выполнения задания | Баллы |
|---|---|
| Верное решение. | 7 |
| Отсутствие деления пополам. | 5 |
| Отсутствие обоснования того, что при выборе следующего звена змейки есть только две возможности из «соседних» вершин. | 5 |
| Решение не соответствует ни одному из перечисленных выше критериев. | 0 |
| Максимальный балл | 7 |
Функция 
такова, что 
и 
для любого x. Найдите 
если 
Из равенства 
мы получаем формулу 
Кроме того, 
По принципу математической индукции докажем, что f(x)=1-x для любого целого x.
Докажем, что указанное равенство верно при четных x: 
1) 
— верно.
2) Пусть 
3) Докажем, что 
Действительно,
Теперь докажем, что указанное равенство верно при нечетных x:
1) 
— верно.
2) Пусть 
при некотором n.
3) Докажем, что 
:
Действительно,
Следовательно, 
Ответ: −2016.
Примечание: заметим, что в случае достаточно доказать, что 
верно для любого нечётного x.
| Критерии оценивания выполнения задания | Оценка | Баллы |
|---|---|---|
| Полное решение. | + | 14 |
| Представлены все основные логические шаги решения. Доказано, что В решении отсутствуют некоторые обоснования. Ответ верный. | ± | 11 |
Выписаны несколько первых значений последовательности  Делается предположение, что  но доказательство данного факта не приводится. Ответ верный. | +/2 | 7 |
Отмечено, что  Обоснования, а также частные подтверждения данного факта не приводятся. Ответ верный. | ∓ | 3 |
| Решение не соответствует ни одному критерию, описанному выше. | −/0 | 0 |
| Максимальный балл | 14 | |
Существует ли многочлен третьей степени такой, что все его корни положительны, а все корни его производной отрицательны, при условии, что и у многочлена, и у производной есть хотя бы один корень?
Подходит, например, многочлен 
его единственный корень — это 1, т. к. 
а единственный корень производной это −1.
Ответ: да.
Только ответ «Да» — 0 баллов.
Пример участника не обязан совпадать с примером из авторского решения. Пример без пояснений (например, без указания, какие именно корни у многочлена и производной или почему они положительны/отрицательны) — не более 1 балла.
Решения с верным примером и недостаточно подробными пояснениями могут быть оценены в 1 или 1,5 балла, однако не стоит слишком придираться: если участник утверждает, что, многочлен имеет такой-то корень и это действительно очевидно, снимать за это не надо.
Существует ли многочлен пятой степени такой, что все его корни отрицательны, а все корни его производной отрицательны, при условии, что и у многочлена, и у производной есть хотя бы один корень?
Подходит, например, многочлен 
его единственный корень — это −1, т. к. 
а единственный корень производной — это 1.
Ответ: да, существует.
Только ответ «Да» — 0 баллов.
Пример участника не обязан совпадать с примером из авторского решения.
Пример без пояснений (например, без указания, какие именно корни у многочлена и производной или почему они положительны/отрицательны) — не более 1 балла.
Решения с верным примером и недостаточно подробными пояснениями могут быть оценены в 1 или 1,5 балла, однако не стоит слишком придираться: если участник утверждает, что, многочлен имеет такой-то корень и это действительно очевидно, снимать за это не надо.
Решите уравнение:
Докажем сначала следующие формулы по индукции в случае, если 
Первая формула. База 
—
Получаем:
Вторая формула. База 
верное утверждение. Переход: предположим, что утверждение верно для некоторого n, докажем, что оно верно и для Получаем:
Разберём сначала случай 
В этом случае левая часть уравнения превращается в 0, а правая это 1009 или −1009, то есть числа 
при целых k не является решениями задачи. Воспользовавшись доказанными выше формулами, превратим исходное уравнение в
откуда 
или 
В первом случае получаем 
где 
откуда 
где 
При этом, так как 
число k не делится на 1009.
Во втором случае получаем 
где 
откуда 
где Для таких чисел поэтому из этого множеств а решений никакие числа исключать не приходится.
Ответ:
1) 
k не делится на 1009.
2) 
1) k не делится на 1009.
2)
Решите уравнение:
Докажем сначала следующие формулы по индукции в случае, если
Первая формула. База 
— Получаем:
Вторая формула. База 
—
Разберём сначала случай 
В этом случае левая часть уравнения превращается в 0, а правая это 1007 или −1007, то есть числа при целых k не являются решениями за дачи. Воспользовавшись доказанными выше формулами, превратим исходное уравнение в
откуда 
или 
В первом случае получаем 
откуда 
где 
При этом, так как число k не делится на 1007.
Во втором случае получаем 
откуда 
Для таких чисел поэтому из этого множества решений никакие числа исключать не приходится.
Ответ:
1) 
k не делится на 1007;
2) 
1) k не делится на 1007;
2)
Последовaтельность зaдaнa следующими соотношениями:
Докaжите, что 
Докажем по индукции неравенство 
База 
Переход от n к Пусть 
тогда 
и, следовательно, 
С другой стороны,
так как для положительных углов выполняется неравенство 
Значит,
что и требовалось доказать.
Замечание. На самом деле можно также доказать, что число π является пределом последовательности 
Последовaтельность зaдaнa следующими соотношениями:
Докaжите, что 
Докажем по индукции неравенство 
База 
Переход от n к 
Пусть 
тогда 
и, следовательно, 
С другой стороны,
так как для положительных углов выполняется неравенство Значит,
что и требовалось доказать.
Замечание. На самом деле можно также доказать, что число 
является пределом последовательности 
Многочлены Чебышева первого рода определены формулой
а) Докажите, что 
б) Докажите, что 
— многочлен степени n с коэффициентом 1 при x^n.
в) Найдите 
и докажите, что для любого квадратного трехчлена 
выполняется неравенство
а) Положим для краткости
б) Доказательство проводится методом математической индукции с использованием рекуррентного соотношения, выведенного в предыдущем пункте. — многочлен степени n с коэффициентом 1 при x^n.
Докажем утверждение по индукции. База. 
Переход. Пусть утверждение верно при 
Докажем его при 
тогда
Итак,
Поэтому степень 
получается увеличением на 1 степени 
а старший коэффициент многочлена 
получается умножением на 2 старшего коэффициента многочлена 
Поскольку
не изменится при переходе к 
в) Имеем: 
и
тогда 
следовательно, надо доказать, что при любых a, b верно неравенство
Далее, имеем:
Поскольку при всех a справедливо неравенство 
то хотя бы одно из этих чисел не меньше единицы. Если 
то хотя бы одно из чисел 
не меньше 
| За каждый из четырех пунктов сюжета выставляется одна из следующих оценок: + (3 балла), ± (2 балла), ∓ (1 балл), − (0 баллов) Максимум за сюжет 12 баллов. При этом необходимо руководствоваться следующим. | |
| Критерии оценивания выполнения заданий | Баллы |
|---|---|
| Верное и полное выполнение задания | 3 |
| Ход решения верный, решение доведено до ответа, но допущен один недочет | 2 |
| Ход решения верный, решение доведено до ответа, но допущено два недочета или одна грубая ошибка | 1 |
| Остальные случаи | 0 |
| К недочетам относятся, например: описки, неточности в использовании математической символики; погрешности на рисунках, недостаточно полные обоснования; неточности в логике рассуждений при сравнении чисел, доказательстве тождеств или неравенств; вычислительные ошибки, не повлиявшие принципиально на ход решения и не упростившие задачу, если задача не являлась вычислительной; замена строго знака неравенства нестрогим или наоборот; неверное присоединение либо исключение граничной точки из промежутка монотонности и аналогичные. Грубыми ошибками являются, например: потеря или приобретение постороннего корня; неверный отбор решения на промежутке при правильном решении в общем виде; вычислительная ошибка в задаче на вычисление; неверное изменение знака неравенства при умножении на отрицательное число, логарифмировании или потенцировании и т. п. | |
а) Докажите, что число различных способов замощения полоски размером 
«доминошками» равно n-му числу Фибоначчи.
б) Найдите формулу для суммы квадратов коэффициентов в разложении бинома 
в) Шестеро учеников готовятся к ответу, сидя в один ряд на скамье за общим столом. Учитель может вызвать их в любом порядке. Какова вероятность того, что, выходя к доске, хотя бы один из них потревожит другого?
а) Пусть xn — число способов замощения полоски «доминошками». Крайняя левая доминошка может лежать так, как показано на рисунке, а или б, в первом случае имеются 
способов замощения оставшейся полоски, во втором их 
Значит, 
а так как 
и 
то, рассуждая по индукции, получаем, что xn — это n-е число Фибоначчи.
б) До этой формулы можно догадаться, рассмотрев несколько значений n, и затем доказать ее по индукции. Приведем, однако, другое рассуждение.
Имеем: 
коэффициент при 
в левой части равен сумме 
откуда и следует указанное тождество.
Ответ: 
в) Найдем вероятность того, что каждый раз ученик выходит к доске, не попросив подняться никого из своих одноклассников. В первый раз учитель должен вызвать Алешу или Евгения (см. рис.), вероятность этого события равна
во второй — опять-таки двух крайних (вероятность — 
и так далее, таким образом с вероятностью 
никто никому не помешает. Искомая вероятность равна 
Ответ: 
| За каждый из четырех пунктов сюжета выставляется одна из следующих оценок: + (3 балла), ± (2 балла), ∓ (1 балл), − (0 баллов) Максимум за сюжет 12 баллов. При этом необходимо руководствоваться следующим. | |
| Критерии оценивания выполнения заданий | Баллы |
|---|---|
| Верное и полное выполнение задания | 3 |
| Ход решения верный, решение доведено до ответа, но допущен один недочет | 2 |
| Ход решения верный, решение доведено до ответа, но допущено два недочета или одна грубая ошибка | 1 |
| Остальные случаи | 0 |
| К недочетам относятся, например: описки, неточности в использовании математической символики; погрешности на рисунках, недостаточно полные обоснования; неточности в логике рассуждений при сравнении чисел, доказательстве тождеств или неравенств; вычислительные ошибки, не повлиявшие принципиально на ход решения и не упростившие задачу, если задача не являлась вычислительной; замена строго знака неравенства нестрогим или наоборот; неверное присоединение либо исключение граничной точки из промежутка монотонности и аналогичные. Грубыми ошибками являются, например: потеря или приобретение постороннего корня; неверный отбор решения на промежутке при правильном решении в общем виде; вычислительная ошибка в задаче на вычисление; неверное изменение знака неравенства при умножении на отрицательное число, логарифмировании или потенцировании и т. п. | |
Пусть 
а) Докажите, что если 
при всех 
то 
при всех 
б) Докажите, что из того, что 
при всех не следует, что 
при всех
в) Пусть 
Докажите, что если при всех то 
где 
при всех
а) В этой задаче, абсолютно очевидной с точки зрения «высшей» математики (рассмотрите интерполяционный многочлен Лагранжа), потребовались некоторые ухищрения для поиска ее решения, не требующего введения новых понятий. Запишем многочлен 
в виде
Очевидно, что достаточно доказать рациональность всех коэффициентов ci, 
Подставляя в выписанное разложение последовательно числа 
получим систему равенств
рациональны. Поскольку 
то из условия рациональности значений 
для 
следует рациональность коэффициентов ck (ср. далее с решением пункта в)).
б) Пример: 
в) Заметим прежде всего, что многочлены 
обладают следующими свойствами:
Последнее свойство достаточно проверить для 
Оно очевидно, поскольку 
Далее, для того, чтобы доказать совпадение многочленов степени n, достаточно показать, что совпадают их значения в 
точке. Поэтому достаточно доказать, что существуют такие 
что 
при 
Рассуждение поведем по индукции. База очевидна, поскольку 
Предположим, что числа 
являются целыми. Подставив 
в равенство 
и воспользовавшись отмеченными свойствами многочленов 
получим, что
откуда и следует целочисленность коэффициента bk.
| За каждый из четырех пунктов сюжета выставляется одна из следующих оценок: + (3 балла), ± (2 балла), ∓ (1 балл), − (0 баллов) Максимум за сюжет 12 баллов. При этом необходимо руководствоваться следующим. | |
| Критерии оценивания выполнения заданий | Баллы |
|---|---|
| Верное и полное выполнение задания | 3 |
| Ход решения верный, решение доведено до ответа, но допущен один недочет | 2 |
| Ход решения верный, решение доведено до ответа, но допущено два недочета или одна грубая ошибка | 1 |
| Остальные случаи | 0 |
| К недочетам относятся, например: описки, неточности в использовании математической символики; погрешности на рисунках, недостаточно полные обоснования; неточности в логике рассуждений при сравнении чисел, доказательстве тождеств или неравенств; вычислительные ошибки, не повлиявшие принципиально на ход решения и не упростившие задачу, если задача не являлась вычислительной; замена строго знака неравенства нестрогим или наоборот; неверное присоединение либо исключение граничной точки из промежутка монотонности и аналогичные. Грубыми ошибками являются, например: потеря или приобретение постороннего корня; неверный отбор решения на промежутке при правильном решении в общем виде; вычислительная ошибка в задаче на вычисление; неверное изменение знака неравенства при умножении на отрицательное число, логарифмировании или потенцировании и т. п. | |
Для числовой последовательности 
..., 
при всех 
Найдите каждый член xn такой последовательности и значения сумм 
Имеем
Тогда 
— любое, и по индукции 
при 
и 
Ответ: при 
x0 — любое.
| Каждая задача оценивается по в соответствии с критериями. | ||
| Вид погрешности или ошибки | Отметка в работе | Баллы |
|---|---|---|
| Решение задачи верное, выбран рациональный путь решения | + | 10 |
| Решение верное, но путь не рационален или имеются один — три недочета или негрубая ошибка | + | 9 |
| Решение верное, но путь не рационален и имеются один — три недочета или негрубая ошибка | ± | 7−8 |
| Ход решения верный, но есть несколько негрубых ошибок или решение не завершено | ∓ | 5−6 |
| Допущены грубые ошибки, но ответ получен (неверный) | ∓ | 3−4 |
| Допущены грубые ошибки и ответ не получен либо решение лишь начато, то что начато — без ошибок | − | 2 |
| Решение начато, но продвижение ничего не дает для результата | − | 1 |
| Задача не решилась | 0 | 0 |
| Недочеты: незначительные (непринципиальные) арифметические ошибки. Негрубые ошибки: технические ошибки в применении формул и теорем, не влияющие на смысл решения; необоснованность логических (верных) выводов. Грубые ошибки: I. Логические, приводящие к неверному заключению. II. Арифметические ошибки, искажающие смысл ответа. III. Неверный чертеж в геометрических задачах. IV. Принципиальные ошибки в применении элементарных формул и теорем. | ||
при x0 — любое.Пусть для каждого натурального n 
Найдите
если a0 = 1, a1 = 2. Докажите по индукции, что 
Знаем, что 
тогда 
и
Следовательно,
Ответ: 148 725.
По окружности движутся n > 4 точек, каждая — с постоянной скоростью. Для любых четырех из них есть момент времени, когда они все встречаются. Докажите, что есть момент, когда все точки встречаются.
(С. Иванов)
Лемма. Пусть 
— арифметические прогрессии с натурального разностями 
причем любые две из них пересекаются. Тогда найдется число, принадлежащее множеству значений всех этих прогрессий.
Доказательство. Индукция по числу прогрессий. База для 
прогрессий очевидна. Докажем переход от n к Не умаляя общности (и по индукционному предположению) можно считать, что прогрессии 
начинаются с нуля. Пусть 
Поскольку прогрессии
имеют общую точку, мы можем считать, что первый член прогрессии 
равен 
(где a — некоторое натуральное число). А поскольку прогрессии и тоже пресекаются, прогрессия должна содержать число вида 
Если 
то мы нашли общую точку всех прогрессий. В противном случае прогрессия содержит все числа вида
По китайской теореме об остатках существует число k, которое делится на 
и имеет остаток 1 при делении 
делится и на d, и на 
т. е. принадлежит множеству значений всех прогрессий.
Покажем, как из леммы следует утверждение задачи. Заметим, что если какие-то три точки встретились вместе только один раз, то и все остальные точки также должны были в этот момент времени с ними встретиться. Если же одни и те же три точки встретились хотя бы два раза, то они будут встречаться бесконечно много раз, причем времена их встреч образуют арифметическую прогрессию. Зафиксируем пару точек A и B и запустим отсчет времени с момента какой-нибудь их встречи.
Пусть в следующий раз они встретились через t секунд, тогда далее все их встречи будут происходить в моменты времени kt, где 
Для каждой точки C моменты ее встреч с парой A, B образуют арифметическую прогрессию 
(здесь 
—
—
По условию точки A, B, C и D встретятся вместе, поэтому прогрессии 
и 
пересекаются для любой пары точек C и D. Тогда, согласно лемме, у всех таких прогрессий есть общая точка P. Значит, в момент времени tP все точки встретятся вместе.
Назовем клетчатым квадрантом четверть плоскости, расположенную выше оси X и правее оси Y, разбитую на клеточки со стороной 1. В клетчатом квадранте закрашены n2 клеток. Докажите, что в этом квадранте найдется не менее n2 + n клеток (в том числе, закрашенных), соседних по стороне с хотя бы одной закрашенной.
(С. Берлов, Д. Ширяев)
Будем доказывать чуть более общее утверждение. Пусть в бесконечном клетчатом квадранте закрашено 
клеток. Тогда у закрашенньх клеток будет как минимум 
соседей. Используем индукцию по n. Базу удобнее всего проверить при 
соседей всегда не меньше, чем самих закрашенных клеток (поскольку у каждой закраненной клетки есть сосед справа и все эти соседи различны).
Для перехода используем для идеи. Они обе просты и незатейливы, но мало связаны друг с другом.
Идея 1. Разобьем весь квадрант на вертикальные полосы ширины 2. Заметим, что в каждой такой полосе, в которой есть хотя бы одна закрашенная клетка (будем называть такие полосы непустыми), соседей хотя бы на одного больше, чем закрашенных клеток. В самом деле, в каждой горизонтальной доминошке (из которых сложена эта полоса) соседей всегда ровно столько жсе, сколько закрашенных клеток — проверьте это! Кроме того, самая верхняя закрашенная клетка в полосе даёт еще одного «лишнего» соседа — сверху от себя.
Таким образом, если среди полос ширины 2 есть хотя бы n непустых, то соседей окажется хотя бы на n больше, чем закрашенных клеток, что и требовалось (и без всякой индукции).
Идея 2. Все клетки квадранта разбиваются на диагональные ряды (в самом первом ряду всего одна клетка, в следующем — две, и т. д.). Рассмотрим самую верхнюю диагональ, в которой еть хотя бы одна закрашенная клетка. Все закрашенные клетки в этой диагонали разбиваются на блоки подряд идущих. Рассмотрим один из таких блоков; пусть в нём k закрашенных клеток.
В следующей (более длинной) диагонали есть 
клеток, соседних с клетками этого блока. Заметим, что других закрашенных соседей у них нет; здесь используется, что соседние в нашей диагонали с рассматриваемым блоком клетки не закрашены (или вообще находятся за границей квадранта). Поэтому, если выкинуть k клеток этого блока (перестать считать их закрашенными), исчезнет соседей. И если окажется, что соседей осталось хотя бы на больше, чем закрашенных клеток, то на исходной картинке их было хотя бы на n больше.
Осталось разобрать два случая. Если 
то клетки нашего диагонального блока затрагивают хотя n полос ширины 2, а значит, работает идея 
Если же 
то после выкидывания этого блока останется
и по индукционному предположению соседей осталось хотя бы на больше, чем закрашенных клеток.
Наверх