Тема Применение классических комбинаторных методов к разным задачам

Индукция в комбинаторике

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела применение классических комбинаторных методов к разным задачам

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#76593

В куче лежат $2024$ камня. Ее делят на две части, затем одну из частей опять делят надвое и так далее, пока не получат $2024$ отдельно лежащих камней. При каждом делении одной из куч на две части на доску записывается произведение количеств камней в этих частях. Какие значения может принимать сумма всех чисел, записанных на доске?

Показать ответ и решение

Пусть $S n$ — сумма чисел, полученная при данном процессе, при условии, что исходная куча содержит $n$ камней. Покажем по индукции, что

(n − 1)n Sn = 1+ 2+ ...+(n− 1)=--2----

При $n =2$ разбиение на две кучи единственно и произведение количеств камней равно $1,$ что доказывает выполнение базы индукции.

Покажем, что верен шаг индукции. Пусть при всех $i∈ {2,3,...,n− 1}$ доказываемое утверждение верно. Пусть кучу, состоящую из $n$ камней разбили на кучи по $k$ и $n− k$ камней. Тогда

Sn = k(n − k)+ Sk+ Sn−k =

(k− 1)k (n − k − 1)k (n− 1)n =k(n− k)+---2-- + ----2----= ---2---

Таким образом, ответом на задачу является число

S2024 = 2023⋅2024-= C22024 2

Ответ:

$2023⋅1012$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#81093

В углу квадрата $n× n,n> 1,$ стоит фишка. Федя и Серёжа делают ходы по очереди, начинает Федя. Ход заключается в том, чтобы выбрать одно из четырёх направлений, после чего несколько раз (хотя бы один) передвинуть фишку на одну клетку в этом направлении. Дважды бывать в одной клетке нельзя. Проигрывает тот, кто не может сделать ход. Кто из игроков может обеспечить себе победу?

Показать ответ и решение

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

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

Индукцией по количеству ходов Федора покажем, что после каждого его хода доска является прямоугольником $x× y$ $(x >y),$ при этом следующих ход будет совершен Сергеем в одну из угловых клеток.

База индукции верна, поскольку после первого хода доска имеет вид прямоугольника $n ×n − 1,$ причем следующих ход будет совершен Сергеем в нижнюю левую клетку.

Докажем переход. Пусть после некоторого хода Федора доска имеет вид $x ×y$ $(x >y),$ причем Сергей совершит ход в одну из угловых клеток и делает несколько ходов по горизонтали, после чего из этой клетки Федор вновь совершает максимальное количество ходов по вертикали. После этого хода Сергей может сделать ход либо вправо, либо влево. Если в каждой из этих случаев доска будет иметь вид $x× 1,$ то Федор сделает последний ход и победит. Иначе одном из случаев доска будет иметь вид прямоугольника $x− 1× z,$ в другом $x× t,$ причем если $z ≤ y− 1$ и $t≤y− 1,$ а значит $x− 1> z$ и $x> t,$ что доказывает переход

Заметим, что каждая пара ходов Федора и Сергея уменьшает сумму количества столбцов и строк доски по крайней мере на 1, а значит, не позже, чем через $2n$ ходов, доска придет к виду $x×1,$ где $x >1.$ Следующим ходом Сергей встанет на самую верхнюю или нижнюю клетку доски, после чего Федор пройдется по всем оставшемся ее клеткам и завершит игру.

Ответ:

Федя

Ошибка.
Попробуйте повторить позже

Задача 3#82934

В некой стране $100$ городов (города считайте точками на плоскости). В справочнике для каждой пары городов имеется запись, каково расстояние между ними (всего $4950$ записей). Пусть стерлись $k$ записей, и известно, что в этой стране никакие три города не лежат на одной прямой. При каком наибольшем $k$ всегда можно однозначно восстановить стершиеся записи?

Показать ответ и решение

Первое решение. Индукцией покажем, что для $n≥ 4$ городов $k= n− 4.$ База очевидна.

Шаг индукции. Пусть для $n$ городов стёрто не более $n − 4$ записей. Выберем город $A,$ для которого стёрто хотя бы одно расстояние до другого города, и рассмотрим остальные $n$ городов. Между ними стёрто не более $n− 5$ расстояний, и по предположению индукции можно восстановить все эти расстояния, а тогда и взаимное расположение этих городов на плоскости. Для города $A$ известны расстояния по крайней мере до трёх городов, и это позволяет однозначно восстановить его расположение. Увеличить $k$ до $n− 3$ нельзя. Пусть неизвестны расстояния от точки $A$ до всех точек, кроме $B$ и $C.$ Тогда положение точки $A$ определено с точностью до симметрии относительно прямой $BC,$ значит, расстояния от неё до остальных точек не восстанавливаются.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Рассмотрим граф со $100$ вершинами и $96$ рёбрами, соответствующими стёртым записям. Этот граф содержит не менее четырёх компонент связности. Зафиксируем по вершине $(A,B,C,D$ ) в каждой из этих четырёх компонент. Все расстояния между этими вершинами известны. Рассмотрим произвольную вершину первой компоненты. Известны её расстояния до точек $B,C,D,$ следовательно, положение соответствующего города на плоскости определено однозначно. Аналогична ситуация с вершинами оставшихся компонент.

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 4#85488

Кощей придумал для Ивана-дурака испытание. Он дал Ивану волшебную дудочку, на которой можно играть только две ноты — до и си. Для прохождения испытания Ивану нужно сыграть какую-нибудь мелодию из 300 нот на свой выбор. Но до того, как он начнёт играть, Кощей выбирает и объявляет запретными одну мелодию из пяти нот, одну — из шести нот, $...$ , одну — из 30 нот. Если в какой-то момент последние сыгранные ноты образуют одну из запретных мелодий, дудочка перестаёт звучать. Сможет ли Иван пройти испытание, какие бы мелодии Кощей ни объявил запретными?

Источники: ММО - 2024, первый день, 11.6 (см. mmo.mccme.ru)

Подсказки к задаче

Подсказка 1

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

Подсказка 2

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

Подсказка 3

А давайте попробуем строить периодические бесконечные мелодии! Но периода какой длины нам хватит?

Подсказка 4

Обратите внимание на то, что при подсчёте количества мелодий, которые запрещает конкретный отрывок длины k, мы будем вычеркивать не более 2^(l-k) мелодий, где l — длина периода.

Показать ответ и решение

Первое решение.

Рассмотрим всевозможные мелодии из нот до и си длины $13$ , коих $13 2$ штук. Каждую такую мелодию периодически продолжим в обе стороны, получив бесконечную в обе сторону мелодию. Назовём две получившиеся бесконечные мелодии эквивалентными, если одна получается из другой сдвигом.

Наименьший период всех бесконечных мелодий, кроме двух, состоящих только из нот до и только из нот си, равен $13.$ Количество не эквивалентных друг другу бесконечных мелодий равно

213− 2 --13--+ 2= 632

(каждой бесконечной мелодии $X$ периода $13$ эквиваленты $13$ мелодий (включая саму $X$ с периодом, который будет циклическим сдвигом $13$ нот, дающих мелодию $X$ )

Из них мелодий, содержащих запрещённые Кощеем мелодии, не больше

(28+ 27 +...+ 21)+18= 528

(в скобках учтены запретные мелодии длины $≤ 12$ , полученные дописыванием $k$ символов к запретной мелодии длины $13− k$ , а за скобками — все остальные).

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

______________________________________________________________________________________________________________________________________________________

Второе решение.

Пусть $Ln$ - число мелодий длины $n$ , не содержащих запретных последовательностей нот. Будем считать, что $L0 = 1.$ По индукции докажем, что $Ln+1 ≥ Ln+ Ln−1$ для всех натуральных $n$ .

База индукции $(n= 1):$ $L2 = 4≥ 2+ 1= L1+ L0.$

Предположим, что неравенство $Lk+1 ≥Lk +Lk−1$ верно для всех $k$ , меньших $n.$ Покажем, что тогда $Ln+1 ≥ Ln+ Ln−1.$ Заметим, что

Ln+1 ≥2Ln − Ln−4− Ln−5− ...− L0

Действительно, мы можем добавить в конец ноту двумя способами к уже имеющейся незапрещенной мелодии из $n$ нот. При добавлении ноты могла возникнуть запретная мелодия длины $5$ в конце последовательности, однако она "испортит"максимум $L n−4$ последовательности нот, так как первые $n− 4$ ноты до "запрещенной"мелодии - незапрещенная мелодия длины $n − 4$ . Аналогично могли получить запретную последовательность из $6$ нот и испортить разрешённую мелодию из $n− 5$ нот и т. д. (Здесь мы можем вычесть лишнее, если $n> 30$ , и часть вычитаемых мелодий могут быть одинаковыми, но поскольку мы пишем оценку снизу, всё правильно.)

Из предположения индукции для $k< n$ $(Lk+1 ≥Lk +Lk−1)$ также следуют неравенства:

Lk+1− Lk ≥Lk−1

Lk+1− Lk−1 ≥Lk

Применим эти следствия, а также неравенство выше, для доказательства перехода индукции и получим:

Ln+1 − Ln − Ln−1 ≥(Ln− Ln−1)− Ln−4 − Ln−5− Ln−6− ...L0 ≥

≥(L − L )− L − L − ...− L ≥ L − L − L − ...L ≥ n−2 n−4 n−5 n−6 0 n−3 n−5 n−6 0

≥ Ln−4− Ln− 6− ...− L0 ≥...≥L1 = 2> 0

Следовательно, $Ln+1 ≥ Ln+ Ln−1$ и переход доказан.

Тогда из-за положительности $L0,L1$ последовательность $Ln$ возрастающая, а значит $L300 > 0$ , откуда следует, что Иван справится с испытанием Кощея.

Ответ: да

Ошибка.
Попробуйте повторить позже

Задача 5#85519

У Вани есть клетчатая бумага двух видов: белая и чёрная. Он вырезает кусок из любой бумаги и наклеивает на серую клетчатую доску $45× 45,$ делая так много раз. Какое минимальное число кусков нужно наклеить, чтобы «раскрасить» клетки доски в шахматном порядке? (Каждый кусок — набор клеток, в котором от любой клетки до любой другой можно пройти, переходя из клетки в соседнюю через их общую сторону. Можно наклеивать куски один поверх другого. Все клетки имеют размер $1× 1.)$

Источники: Турнир городов - 2024, весенний тур, 11.6 (см. turgor.ru)

Подсказки к задаче

Подсказка 1

Когда сложно понять, как устроена наша конструкция, можно попробовать рассмотреть “маленькие” поля, со стороной 1,2 или 3, в них будет легче понять закономерность и прийти к мысли об оценке и примере.

Подсказка 2

Если мы увидели предположительную закономерность на маленьких числах, для оценки можно попытаться применить индукцию. Для того чтобы осуществить шаг индукции, можно воспользоваться тем, что шахматная доска состоит из большого числа отдельных белых и черных “кусочков”. Как это формализовать?

Подсказка 3

Шахматная раскраска означает, что при переходе в соседнюю по стороне клетку мы всегда меняем цвет. И для оценки можно как раз считать количество таких “смен цвета”, в данной задаче эта конструкция очень и очень поможет!

Показать ответ и решение

Оценка.

Можно считать, что первый наклеенный кусок — весь квадрат, от этого ничего не испортится. Считаем его нулевым. Докажем индукцией по $k$ утверждение:

_________________________________________________________________________________________________________________________________________________________________________________

После еще $k$ кусков между любыми двумя клетками есть путь с не более чем $2k$ сменами цвета.

_________________________________________________________________________________________________________________________________________________________________________________

База при $k= 0$ верна.

_________________________________________________________________________________________________________________________________________________________________________________

Рассмотрим наклеивание $k$ -го куска $S$ . Пусть до этого между двумя клетками был путь с не более $2(k− 1)$ сменами цвета. Если он не заходил в $S$ , то он таким и остался. Иначе заменим его кусок от первой его клетки в $S$ до последней такой клетки на путь по $S$ между этими клетками. Тогда количество смен цвета в новом пути увеличилось не более чем на 2 по сравнению со старым. Переход доказан.

_________________________________________________________________________________________________________________________________________________________________________________

В конце между противоположными углами любой путь имеет хотя бы 88 смен цвета. Значит, поверх нулевого куска наклеено еще хотя бы 44.

_________________________________________________________________________________________________________________________________________________________________________________

Пример.

Пусть верхний слой состоит из центральной клетки. Далее пусть каждый нижележащий слой состоит из клеток предыдущего слоя и из клеток, примыкающих к ним по стороне, и имеет противоположный цвет.

Ответ: 45

Ошибка.
Попробуйте повторить позже

Задача 6#90600

Целые точки плоскости раскрашены в $k$ цветов. Докажите, что найдется клетчатый квадратик, вершины которого покрашены в один цвет.

Подсказки к задаче

Подсказка 1

Решать задачу для k цветов тяжело. Попробуйте решить задачу для 2 цветов. Почему он сработал? Потому что удалось создать ситуацию, что в какой цвет не покрась клетку, будет квадрат. Попробуйте сделать больше запретов.

Подсказка 2

Сделайте алгоритм, который дал 2 запрета на 1 раз больше. Что получится?

Показать доказательство

Докажем, сначала, что для раскраски целочисленных точек в $k$ цветов любом квадрате достаточно большого размер, имеющего целые вершины и границы, параллельные линиям сетки, найдется одноцветный равнобедренный треугольник $ABC,$ у которого $AB$ и $BC$ являются катетами, а также вершина $B$ находится ниже вершины $A$ и правее вершины $C.$ Доказывать это утверждение будем индукцией по $k.$ База для $k= 1$ очевидна. Будем обозначать сторону квадрата из утверждения через $lk.$ Тогда берем $l1 = 2.$ Выберем произвольную горизонтальную прямую. Тогда по теореме ван дер Вардена для отрезка длины $W(k+ 1,2lk)$ найдется одноцветная арифметическая прогрессия длины $2lk$ . Обозначим координаты этих $2lk$ точек через $(x,0),(2x,0),...(2lkx,0)$ (не нарушая общности, можно считать координаты такими), и пусть они все покрашены в первый цвет. Рассмотрим решетку со стороной $x,$ содержащую точку $(0,0).$ Тогда заметим, что точки этой решетки, принадлежащие треугольнику с координатами $(2x,x),(2lkx,x),(2lkx,(2lk− 1)x),$ не могут быть покрашены в первый цвет (иначе требуемый прямоугольный треугольник уже был бы найден). С другой стороны внутрь выделенного треугольника помещается квадрат со стороной $lkx.$ Тогда требуемый прямоугольный треугольник найдется по предположению индукции в данном квадрате (с новой решеткой). В качестве $lk+1$ нам подойдет $W (k+1,2lk).$

Перейдем к решению задачи. Разобьем все целые точки на квадраты со стороной $l2.$ Будем каждый квадрат считать точкой. Цвет квадрата определим как набор цветов его целочисленных точек (то есть всего цветов не больше $2 2(l2+1)$ ). Тогда по ранее доказанному найдется равнобедренный прямоугольный треугольник с вершинами — квадратами. Но в каждом таком квадрате есть равнобедренный прямоугольный треугольник. Тогда имеем конструкцию как на рисунке. Будем считать, что три найденных треугольника покрашены в белый цвет. Заметим, что вершины, дополняющие каждый треугольник до квадрата должны быть окрашены в другой цвет, пусть в черный (иначе мы бы уже нашли квадрат). Но тогда посмотрим на обведенную точку. У нее $2$ запрета, проделая операцию, совершенную при поиске уголка на $1$ раз больше, мы бы получили $3$ запрета, проделая еще на $1$ раз больше $4$ запретов. Процесс можно продолжать до $n$ запретов.

$PIC$

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#90602

[Обобщенная теорема ван дер Вардена] Целые точки плоскости раскрашены в $k$ цветов. Назовем фигурой конечное множество точек $M$ с целыми координатами. Докажите, что на плоскости можно выбрать фигуру, гомотетичную $M,$ в которой все точки одноцветны.

Подсказки к задаче

Подсказка 1

Формулировка достаточно тяжелая, что делать непонятно. Понятно, что нужна какая-то сложная техническая работа. В таких случаях часто помогает индукция. Проведите ее по числу вершин в фигуре.

Подсказка 2

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

Подсказка 3

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

Подсказка 4

Почему фигура из n точек не находится? Значит, что все дополняющие фигуру из n-1 точки не подходящего цвета. А что это значит в терминах больших квадратов?

Подсказка 5

Существует фигура из n-1 квадрата со стороной N, на самом деле это N^2 больших фигур, где сторона клетки 1. Это нам дает еще какое-то количество запретов. Ура! Мы научились делать 2 запрета цвета у клетки. Как сделать больше?

Подсказка 6

Рассмотрите квадраты, сделанные из квадратов со стороной N. Аккуратно покажите, как появляется еще один запрет, проделайте это много-много раз.

Показать доказательство

Пусть фигура $M = {M ,M ,...,M }, 1 2 n$ где $M i$ — точка плоскости. Обозначим за $X M,r$ минимальное значение стороны квадрата иp точек, в котором точно найдётся фигура гомотетичная $M$ при раскраске в $r$ цветов.

Введем операцию: сжатием фигуры $Y ={Y1,Y2,...,Yn}$ будем называть следующее. Пусть точки фигуры $Y$ можно покрыть квадратом стороны $k,$ тогда способов раскрасить этот квадрат $k2 r ,$ назовем такой квадрат сжатой точкой, тогда составим квадрат со стороной $XY,rk2$ сжатых точек. В нем точно найдется фигура гомотетичная $Y$ составленная из сжатых точек, ее назовем образом первого ранга. Аналогично определим сжатия больших рангов.

Вернемся к исходной задаче. Ее будем решать индукцией по $n$ — количеству точек фигуры. База $n= 2:$ очевидна на любой прямой проходящей через любые две точки. Среди них будет две одноцветных. Переход: докажем утверждение для каждого фиксированного $r.$ Пусть фигура $M = {M1,M2,...,Mn}.$ По предположению индукции фигуру гомотетичную $′ M ={M1,M2,...,Mn −1}$ мы строить умеем, сделаем это. Посмотрим на точку $V,$ дополняющую фигуру до гомотетичной $M,$ далее она конечная. Если $V$ того же цвета, что и $M′,$ то мы получим требуемое. Теперь $V$ другого цвета.

Точкой $Ai1s,i2s−1,...,is1$ будем обозначать следующее. Пусть мы провели $s+1$ сжатия, тогда $ij$ это индекс сжатой точки после $s+ 2− j$ сжатий такой, что расположение этой сжатой точки относительно остальных сжатых точек соответствует расположению $Aij$ относительно ${A1,A2,...,Ak}∖Aij.$

______________________________________________________________________________________________________________________________________________________

Лемма. Пусть мы провели сжатие фигуры или образа(далее фигуры). Тогда, если до сжатия была фигура $B = {B1,B2,...,Bn},$ то фигура заданная множеством ${Bi2,i1|i=1,2,...,k}$ будет гомотетична $B.$

Доказательство. Рассмотрим пару точек $Bi,Bj,$ тогда после сжатия, сжатые точки $Ui,Uj$ соответствуют $Bi,Bj,$ до сжатия так как образ гомотетичен фигуре, то соответствующие элементы квадратов $Ui$ и $Uj$ отличаются на вектор $z−B−−i→Bj$ для фиксированного $z.$ Точки $B ,B i j$ отличаются на вектор $−−B−B→, i j$ а точки $B ,B i2 j2$ будут отличаться на $z−B−−→B + −−B−→B = (z +1)−−B−B→, i j i j i j$ где $z +1$ — фиксировано для каждой пары точек, лемма доказана.

_________________________________________________________________________________________________________________________________________________________________________________

Построим конструкцию по индукции по числу сжатий. Далее верхний индекс - цвет фигуры. База $t=1 :$ строим фигуру из $n− 1$ точки, $1 V$ — конечная. Переход: пусть проведено $t− 1$ сжатие и точка $t V$ — конечная для фигур

j {{{Ait−2,it−3,...,ij}|i= 1,2,...,n− 1}|j = 1,2,...,n− 1}

Из построения будет видно, что точка $i−$ ого цвета после $i− 1−$ ого сжатия единственная.

Делаем сжатие, получаем фигуру из $n− 1$ образов $t− 1$ ранга. Перед этим переобозначим $j j W i = Ait−2,it−3,...,ij.$ Тогда по доказанной лемме множество $j {W i2,i1|i= 1,2,...,n− 1}$ для всех цветов $j$ будет образовывать фигуры подобные $M ′.$ Так как до сжатия существовала $Vt−1$ дополняющая до $M$ все эти фигуры, значит, после гомотетии существует $V t+1$ с которой фигуры гомотетичны $M.$ Осталось показать, что $Vt+1$ дополняет до $M$ точки $Vt1,Vt2,...,Vnt−1.$ Действительно, посмотрим на квадрат, который дополнял бы $n− 1$ образов $t− 1$ ранга до $n$ сжатых точек, образующих фигуру, гомотетичную $M.$ Возьмем в ней точку соответствующую $V t$ до сжатия, обозначим за $Vt+1,$ тогда очевидно, что соответствующие точки в этих квадратах образуют нужную нам фигуру. С другой стороны по доказанной лемме, если взять точку в квадрате, соответствующему по расположению этой точки относительно других квадратов, то все такие точки являются нужной нам фигурой. Тогда мы получили $n$ фигур различных цветов с общей дополняющей точкой, значит, решили задачу.

Ошибка.
Попробуйте повторить позже

Задача 8#94915

На полке стоит $55$ томов собрания сочинений В.И.Ленина. За раз разрешается взять несколько подряд идущих томов и переставить их в обратном порядке. Докажите, что такими операциями можно расставить тома по порядку.

Показать доказательство

Будем решать задачу для $n$ томов.

База для $n= 1$ и $n= 2.$ Для $n =1$ расстановка верна. Для $n= 2$ либо порядок уже верен, либо его можно изменить за один ход из $2,1$ в $1,2.$

Переход: $n→ n +1$

Найдём, где стоит $(n +1)−$ й том. Возьмём блок, начинающийся с этого тома до последнего, и переставим книги в нём в обратном порядке. Тем самым получаем следующую расстановку: тома с $1−$ го по $n−$ й стоят в произвольном порядке, а $(n+ 1)−$ й том находится на последнем месте. Теперь можно применить индукцию к первым $n$ томам. Получаем верную расстановку $(n+ 1)−$ го тома. Переход доказан.

Значит, и 55 томов можно расставить.

Ошибка.
Попробуйте повторить позже

Задача 9#94936

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

Показать доказательство

База для $n = 1$ очевидна.

Переход: $n→ n +1$

Рассмотрим ситуацию перед последним разрезом. К этому моменту было уже $n$ действий. По предположению индукции, после $n$ разрезов остаётся чистый кусок. После $(n+1)−$ го разреза этот кусок мог остаться нетронутым или мог быть разрезан на две части, но так как нож с одной стороны чистый, то с этой стороны кусок также останется полностью чистым. Значит, после $(n +1)−$ го разреза найдётся чистый кусок. Переход доказан.

Ошибка.
Попробуйте повторить позже

Задача 10#94938

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

Показать доказательство

Будем доказывать это утверждение индукцией по числу ступенек.

База для $n= 1$ очевидна.

Переход: $n→ n +1$ . Будем воспринимать лестницу из $(n+ 1)−$ й ступеньки как лестницу из $n$ ступенек и ещё одной дополнительной ступеньки.

Первое решение. Если человек стоит на $(n +1)−$ й ступеньке и при следующем ходе уходит с лестницы, то переход доказан. Если первым ходом он попадает на лестницу из $n$ ступенек, то будем считать, что он изначально стоял на ней.

(*) Пусть человек стоит на лестнице из $n$ ступенек. По предположению индукции он точно покинет её. Если он сойдёт с её 1-й ступеньки, то переход доказан. Если нет, то он встанет на $(n+ 1)$ -ю ступеньку. Здесь возможны два варианта: если на этой ступеньке стрелка показывает в сторону окончания лестницы, то переход доказан. Если нет, то стрелка развернётся в сторону выхода, и человек снова окажется на лестнице из $n$ ступенек. Рассуждения с места (*) повторятся, но теперь, в случае попадания на $(n +1)−$ ю ступеньку, мы гарантируем, что он выйдет с лестницы. Переход доказан.

Второе решение. Предположим, что человек может бесконечно ходить по лестнице из $(n+ 1)−$ й ступеньки. На $(n+ 1)−$ ю ступеньку он может встать не более одного раза, потому что если он встал на неё и сошёл на $n−$ ю ступеньку, то стрелка развернулась в сторону выхода, и в следующий раз при наступлении на неё человек точно сойдёт с лестницы. Тогда если человек не становится на $(n+ 1)−$ ю ступеньку, то он бесконечно ходит по лестнице из $n$ ступенек, что противоречит предположению индукции. Если он всё-таки встал на $(n+ 1)−$ ю ступеньку, то до этого он сделал конечное число шагов, а продолжить бесконечное число шагов он должен на лестнице из $n$ ступенек, что снова противоречит предположению индукции. Противоречие. Значит, он обязательно сойдёт с лестницы.

Ошибка.
Попробуйте повторить позже

Задача 11#97574

В теннисном турнире участвовало $1000$ человек, каждый с каждым сыграл один раз, ничьих нет. Докажите, что всех игроков можно поставить в ряд так, чтобы каждый из $998$ человек, стоящих не на краю, либо победил обоих своих соседей, либо проиграл обоим соседям.

Подсказки к задаче

Подсказка 1

Конечно, в этой задаче хочется использовать индукцию. К сожалению, при n=3 существует контрпример, поэтому переход стоит делать от n к n+2.

Подсказка 2

Мы хотим "расширить" наш пример. По предположению индукции точно есть цепочка, в которой хотя бы n человек. Нетрудно получить решение, если их n+1, но вот встроить оставшихся двух человек не получается. Что тогда можно сделать?

Подсказка 3

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

Показать доказательство

Докажем утверждение по индукции. База $n =2$ очевидна. Переход будем делать, добавляя по $2$ человека. Пусть для $2k$ человек их можно расставить, как требуется по условию. Покажем, что и $2k +2$ тоже можно. Выделим в этих $2k+ 2$ самую длинную цепочку, подходящую по условию. По предположению индукции там хотя бы $2k$ человек.

1.: Предположим, что там $2k+ 1$ человек. Без ограничения общности, можно считать, что крайние люди $A$ и $B$ проиграли своим соседям (по чётности их результаты будут одинаковы). Будем писать $A >B,$ если $A$ выиграл у $B.$ Без ограничения общности, можно считать, что $A >B.$ Рассмотрим оставшегося человека $X.$ Если он выиграл у $A$ или у $B,$ то можно увеличить цепочку, добавив $X$ на край. Значит, $X < A$ и $X < B.$ Тогда переставим $A$ на другой край, а потом на тот же край поставим $X.$ Получим подходящую цепочку $B < A >X.$ Мы в любом случае сможем добавить человека $X,$ что и хотели.
2.: Предположим, что там $2k$ человек. Тогда уберём одного с краю, останется три человека. Опять можно считать, что крайние люди $A$ и $B$ проигравшие и $A >B$ . Пусть их зовут $X,Y,Z.$ Среди них обязательно есть человек, который одному проиграл, а у другого выиграл. Пусть это $Y$ и $X > Y > Z.$ Посмотрим, как $Y$ сыграл с $A.$ Если $Y > A,$ то добавим на край после $A$ $Y,$ а потом $Z.$ Получим корректную цепочку $Z <Y > A.$ Теперь в ней $2k+ 1$ человек, противоречие. Пусть $Y < A.$ Тогда перекинем $A$ на другой край, допишем за ним $Y,$ а дальше $X.$ Снова получим цепочку, которая теперь кончается на $B < A> Y <X$ и в ней $2k +1$ человек. Так что мы всегда сможем найти увеличить нашу цепочку, пока в ней не станет $2k+ 2$ человек, ЧТД.

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#67957

В каждой клетке таблицы $100× 100$ записано натуральное число. В каждой строке имеется по крайней мере 10 различных чисел, а в каждых четырех последовательных строках не более 15 различных чисел. Какое наибольшее количество различных чисел может быть в таблице?

Источники: СПБГУ-23, 11.1 (см. olympiada.spbu.ru)

Подсказки к задаче

Подсказка 1

У нас в каждой строке не менее 10 различных чисел, в подряд идущих четырех строчках не больше 15 различных...как будто следующие 3 строчки дают не очень много новых различных чисел. Это наблюдение легко сделать строгим, и останется привести пример)

Подсказка 2

Если вышло, что различных чисел не больше 175, это хорошо. Тогда вот идея для примера: в первой строчке давайте сделаем все числа от 1 до 10, а в 2, 3 и 4 поставим числа от 1 до 5 и от 11 до 15. Придумайте, как это обобщить на всю нашу доску)

Показать ответ и решение

В одной строке не менее 10 различных чисел, поэтому в следующих трех строках вместе появляется не более 5 новых чисел. Стало быть, первые четыре строки содержат не более 15 различных чисел, а каждые следующие три строки дают не более 5 новых чисел и всего чисел не больше, чем $15+32⋅5= 175.$

Приведем пример на 175 чисел. Занумеруем строки числами от 1 до 100. В первой строке поставим числа от 1 до 10, а в строке с номерами от $3k− 1$ до $3k+ 1$ поставим числа 1 до 5 и числа от $5k+6$ до $5k+ 10.$ Тогда в каждой строке будет 5 уникальных чисел и еще числа от 1 до 5, т.е. ровно 10 различных чисел, а в каждых четырех строках будет ровно 15 различных чисел. Таким образом, в таблице будут числа от $1$ до $5⋅33 +10= 175.$

Замечание.

Доказать, что количество различных чисел в таблице не превосходит 175, можно по индукции. А именно, доказать, что в любых $3n +1$ подряд идущих строках расположено не более чем $5(n +2)$ различных чисел. База $n =1$ верна по условию. Установим переход от $n$ к $n+ 1.$ Рассмотрим $3n+ 4$ подряд идущие строки. Пусть в четвертой с конца строке имеется $k≥ 10$ различных чисел. Тогда в трех самых нижних строках не более чем $15− k$ различных чисел. А в оставшихся $3n +1$ строке по индукционному предположению не больше $5(n +2)$ чисел. Поэтому всего различных чисел будет более чем $5(n+ 2)+ 15− k= 5(n+ 5)− k≤5(n+ 3).$

Ответ: 175

Ошибка.
Попробуйте повторить позже

Задача 13#74422

Каждая клетка доски $8× 8$ чёрная или белая. За ход можно любой прямоугольник из трёх клеток перекрасить в тот цвет, которого в нём больше. Докажите, что за несколько ходов можно сделать всю доску одноцветной.

Показать доказательство

Индукцией по $n$ докажем, что за несколько таких ходов прямоугольник $n× n$ ( $n ≥3$ ) можно сделать одноцветным.

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

Переход. Рассмотрим квадрат $(n +1)× (n +1).$ Выделим в нижнем левом углу квадрат $n ×n.$ По предположению мы можем сделать его одноцветным, сделаем это. Теперь осталось покрасить все клетки верхней строки и правого столбца в цвет квадрата. Это нетрудно сделать, ведь для любой их клетки кроме той, что находится в правом верхнем углу, можно выбрать прямоугольник, в котором она находится с двумя клетками выделенного квадрата $n× n.$ Далее если клетка в правом верхнем углу не покрашена в нужный цвет, сделаем ход в любом прямоугольнике, в который она входит. Что и требовалось.

Ошибка.
Попробуйте повторить позже

Задача 14#74425

Есть $555$ гирь весами $1,2,3,...,555$ г. Докажите, что их можно разложить на $5$ равных по весу кучек.

Подсказки к задаче

Подсказка 1

Возможно, число 555 не так уж важно, и написано для красоты. Тогда можно попробовать применить индукцию. Какое утверждение мы будем доказывать?

Подсказка 2

Заметим, что 555 = 5 × 111. То есть нечетное число, умноженное на 5. Тогда попробуем доказать нужное утверждение для всех чисел вида 5(2k+1). Как доказать базу индукции при k = 1?

Подсказка 3

Верно! Просто создадим готовые кучки. Например, в первую 9 и 15, во вторую положим 14 и 10, в третью — 11 и 13, в четвертую — 12, 8 и 4 и остальные — в пятую. Теперь мы предполагаем, что умеем разбивать все числа на 5 групп с одинаковой суммой для некоторого k = s. Можно ли для перехода использовать идею симметрии?

Показать доказательство

Докажем индукцией по $k,$ что гири с весами $1,2,...,5(2k +1)$ можно разбить на $5$ равных по весу кучек.

База для $k= 1.$ В первую кучу положим $9$ и $15,$ во вторую $14$ и $10,$ в третью — $13$ и $11,$ в четвёртую — $12,8$ и $4.$ Остальное — в пятую.

Переход. Пусть мы умеем разбивать гири с весами $1,2,...,5(2k +1)$ на $5$ равных по весу кучек. Добавим гири с весами $5(2k +1)+ 1,5(2k+1)+ 2,...,5(2k +1)+ 10.$ Разобьём эти числа на $5$ групп вида $(5(2k +1)+ i,5(2k+ 1)+11− i).$ Нетрудно видеть, что в каждой группе сумма чисел одинаковая. В каждую кучу добавим по одной группе и получим требуемое.

Ошибка.
Попробуйте повторить позже

Задача 15#74659

Даны трое чашечных весов без гирь, из которых ровно одни сломаны: их показания произвольны, и мы не знаем, какие весы неисправны. Докажите, что из $k 3$ монет можно определить одну фальшивую (легче настоящих) не более, чем за $2k+ 1$ взвешивание.

Показать доказательство

Докажем индукцией по $k.$

База для $k= 1.$ Возьмём две монетки и сравним на двух весах. Если показания одинаковые, то мы уже определили фальшивую монету, так как одни из этих весов точно рабочие. Действительно, если на обоих весах монеты равны, то третья — фальшивая. Если, не умаляя общности, на обоих весах первая монета легче, то она фальшивая.

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

Докажем переход. Разделим $k 3$ монет на три кучи по $k−1 3$ монет в каждой. Возьмём две кучи и сравним их массы на двух весах.

Если показания разные, третьи весы точно рабочие. Далее работаем только с ними. Доказывая базу, мы поняли, что одно взвешивание на рабочих весах позволит определить кучу с фальшивой монетой. Поэтому сравним любые две кучи на третьих весах, определим кучу с фальшивой монетой, разделим её на три кучи по $3k−2$ монет и продолжим делать то же самое с полученными кучами. В этом случае мы сделаем $k+2 <2k +1$ взвешиваний.

Предположим, что показания разные. По рассуждениям из базы ясно, что такая ситуация даёт нам понять, какая из кучек содержит фальшивую монету. Заметим, что теперь у нас $3k−1$ монет и $2k− 1= 2(k − 1)+ 1$ взвешивания, то мы можем использовать предположение. Что и требовалось.

Ошибка.
Попробуйте повторить позже

Задача 16#75913

В колонию из $1000$ бактерий попал вирус. Каждую секунду каждый вирус уничтожает одну бактерию, после чего все бактерии и все вирусы делятся пополам. Докажите, что рано или поздно все бактерии будут уничтожены, и выясните, когда это произойдет.

Подсказки к задаче

Подсказка 1

Для начала стоит понять сколько будет вирусов на n-ой секунде.

Подсказка 2

В n-ую секунду будет 2ⁿ вирусов. Теперь попробуйте понять, сколько будет бактерий в эту секунду(какая-то формула от n).

Подсказка 3

На самом деле бактерий в n-ую секунду будет 2ⁿ(1000 - n). Попробуйте доказать это по индукции.

Подсказка 4

Теперь осталось понять, на какой же секунде все бактерии погибнут, то есть найти корень выражения 2ⁿ(1000 - n).

Показать ответ и решение

Очевидно, что количество вирусов в $n$ -ую секунду — $2n.$ Докажем тогда по индукции, что число бактерий в $n$ -ую секунду — $n 2 (1000− n).$

База индукции. $n 0 n= 0,2 (1000− n)= 2 ⋅1000= 1000$ — что верно.

Предположение индукции. Пусть для всех $n< k$ верно, что $n 2 (1000− n)$ — число бактерий в $n$ -ую секунду.

Переход индукции. Докажем, что для $n =k.$ Тогда по предположению в $n − 1$ секунду бактерий имеется $n− 1 2 (1000 − n +1),$ а вирусов $n−1 2 .$ Следовательно в следующую секунду будут уничтожены $n−1 2$ бактерий, а остальные существа делятся пополам. Тогда бактерий стало $n− 1 n−1 n (2 (1000 − n +1)− 2 )⋅2= 2 (1000− n).$ Что доказывает переход индукции.

Итого, утверждение доказано. В $n$ -ую секунду у нас $n 2 (1000− n)$ бактерий. А значит, через ровно через $1000$ секунд все бактерии будут уничтожены.

Ответ:

Все бактерии погибнут через $1000$ секунд

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 17#76058

В каждой клетке доски $8 ×8$ нарисована стрелка (вверх, вниз, вправо или влево). Фишка ставится на произвольную клетку. Каждым ходом фишка сдвигается на соседнюю клетку в направлении стрелки, а сама стрелка поворачивается на $∘ 90$ по часовой стрелке. Докажите, что фишка рано или поздно свалится с доски.

Показать доказательство

Докажем по индукции для досок вида $2n× 2n$ со стрелочками, что фишка упадет за пределы доски за конечное число перемещений. Тогда и для доски $8×8$ фишка упадет за пределы доски за конечное число шагов.

База индукции: Доска $2×2.$ После попадания на каждую клетку - стрелочка поворачивается на $∘ 90$ градусов по часовой стрелке. Тогда за не более, чем $2$ поворота стрелочка повернется в сторону от доски, а тогда при попадании на неё фишка вылетит за пределы. Тогда на каждую из $4$ клеток фишка может попасть лишь конечно число раз, не падая за пределы доски. Тогда всего фишка может сделать не более $8$ ходов до того, как вылетит за пределы.

Переход: рассмотрим внешние клеточки доски $2n× 2n$ (по периметру). Опять-таки на каждую из внешних клеток доски можно попасть не более $3$ раз, после чего стрелка на этой клетке повернется вне доски, а тогда после попадания фишки на нее, фишка выпадет. При этом по предположению индукции, если фишка попадает во внутренний квадрат $(2n− 2)× (2n− 2),$ то за не более чем конечное число шагов $k$ она окажется, вне его пределов. Тогда за не более чем конечное число шагов $k$ — фишка будет поворачивать хотя бы $1$ из стрелок во внешних клетках. Но так как клеток внешних конечное число, а также мы попадаем на краевые клетки за конечное число переходов, то за конечное число шагов все внешние стрелки будут направлены вне доски, тогда при попадании на них фишка вылетает за пределы (фишка снова попадет на внешние клетки, так во внутреннем квадрате она находится лишь конечное число ходов).

Ошибка.
Попробуйте повторить позже

Задача 18#74788

Двое играют в карточную игру. У каждого есть колода из 30 карт. Каждая карта красная, зелёная или синяя. По правилам красная карта сильнее зелёной, зелёная сильнее синей, а синяя сильнее красной. Карты одного цвета равны. Колода каждого игрока перед началом партии перемешивается и кладётся перед ним рубашкой вверх. После этого оба открывают по верхней карте своей колоды. Если карты разного цвета, то выигрывает тот, чья карта сильнее. Если карты одинаковые, то они уходят в сброс, а игроки открывают ещё по одной карте - и так до тех пор, пока карты не окажутся различными. Если же обе колоды кончились, а победитель не выявлен, объявляется ничья.

Известно, что у первого игрока в колоде по 10 карт каждого цвета. Второй игрок имеет право взять любую колоду из 30 карт. Может ли он подобрать колоду так, чтобы вероятность его выигрыша была больше 1/2?

Источники: ФЕ-2022, 11.5 (см. www.formulo.org)

Подсказки к задаче

Подсказка 1

Разберемся с ответом. Если мы хотим доказывать, что нет, то нам надо доказывать, что для всевозможных колод у второго вероятность будет меньше 1/2. Это вообще непонятно как делать. А вот если же мы хотим доказывать, что ответ - да, то нам надо привести всего одну «хорошую» колоду. Давайте подумаем, если у нас дано количество синих, красных и зеленых карт каждого человека, то как бы для нас удобно было бы выражать вероятность, ведь наши переменные никак друг от друга не зависят(мы хотим выразить в общем случае вероятность и подставить одну и ту же переменную вместо всех для первого игрока в конце).

Подсказка 2

Наверное было бы удобно делать это рекуррентой, поскольку игра идет по шагам. Мы хотим как-то зафиксировать нашу конструкцию. Давайте подумаем как это можно было бы сделать не вводя кучи переменных. Пусть у нас r, g, b — количество соответственно красных, зеленых и синих карт у первого. Тогда, если мы хотим доказать, что при какой-то колоде все хорошо, то либо нам опять рассматривать все колоды и как-то усреднять (что то же самое, что и доказывать, что ответ «нет», в смысле рассмотрения всевозможных колод), либо брать какую-то конкретную колоду, методом крайнего. Какие колоды при этом кажутся интуитивными в таком случае?

Подсказка 3

Во-первых, интуитивной кажется колода копирующая первого игрока, но чисто навскидку, ситуации симметричны и вряд ли там будет строго больше 1/2 вероятность. Давайте также поймем, что скорее всего число 30 здесь просто так, кроме разве что того, что оно кратно 3. А это значит, что по нашему предположению, мы можем масштабировать колоду, при этом не меняя кардинально конструкцию взятия колоды второму, чтобы было выполнено условие. Но тогда это значит, что мы либо берём какую-то фиксированную долю от колоды для каждого цвета, а если так, то нужны еще согласованности с делимостью на эту долю и это как-то все очень шатко, если мы предполагаем, что можно масштабировать. Это наталкивает нас на мысль, что по хорошему бы брать какое то маленькое (чтобы и для маленьких размеров колод, скажем, меньших 30 условие было выполнено) фиксированное число карт одного цвета, тоже самое с другим, и все остальное - третьего цвета.

Подсказка 4

Чтобы можно было брать маленькое число карт в колоде и все работало, хотелось бы брать по 0 или 1 карте каких-то двух цветов, а все остальное отдавать другому. Ну и при этом понятно, что если мы будем выражать реккурентой нашу вероятность, то если мы, скажем, возьмем 1 зеленый, 1 синий и остальное - красным, то нам надо будет еще выражать как-то реккуренту для подсчета, когда у нас 0 зеленых, 1 синий и остальные - красные, 1 зеленых, 0 синих, остальные - красные, а также 0 зеленых, 0 синих, остальные -красные. Что как бы муторно. Тогда давайте возьмем остальные красными, а одну либо синей, либо зеленой.

Подсказка 5

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

Подсказка 6

Если вероятность победы второго, когда только красные это v(r, g, b), где r, g, b - кол-во красных, зеленых и синих у первого соответственно, то v(r, g, b) = (g * 1 + r * v(r - 1, g, b)) / (r + g + b) - просто перебираем исходы и варианты, когда победим.

Подсказка 7

Напишите такую же рекурренту для u(r, g, b), где это вероятность когда одна синяя и остальные красные(очевидно, она будет выражаться через себя и v(r, g, b)), после чего попробуйте и для v, и для u найти общий вид реккуренты (очевидно, сначала для v, так как она проще и в итоге, искать надо u), перебирая маленькие значения, после чего задача будет решена.

Подсказка 8

Не забудьте доказать эти формулы по индукции, найдя базу и сделав переход (быть может сам переход натолкнет вас на вид, как должны выглядеть v и u).

Показать ответ и решение

Рассмотрим колоду, в которой одна синяя карта, а все остальные красного цвета. Найдём в этом случае вероятность выигрыша второго игрока. Пусть $u(r,g,b)−$ вероятность выигрыша, когда у первого игрока $r$ красных карт, $g$ зелёных, $b$ синих, а у второго одна синяя и все остальные красные (при условии $r+ g+ b>0$ ). Также пусть $v(r,g,b)$ - вероятность выигрыша, когда у второго игрока все карты красные.

Легко видеть, что

g⋅1+ r⋅v(r− 1,g,b) v(r,g,b)= ----r+-g+-b-----

при $r+ g+b> 0$ (если у первого выпала зелёная, то второй выиграл, если синяя, то проиграл, если красная, то игроки потратили по одной красной карте и продолжили игру). Ясно также, что $v(0,0,0)= 0$ (в этом случае будет ничья). Отсюда по индукции получаем, что $v(r,g,b)= gg+b$ при $g+ b> 0$ и $v(r,0,0)= 0$ .

Аналогично

u(r,g,b)= g(r+g+-b−-1)+r(1+(r+-g+-b− 1)u(r−-1,g,b))+-bv(r,g,b−-1)) (r+ g+ b)2

(Здесь мы рассматриваем всевозможные пары ходов: одна из $r+ g+b$ карт первого и одна из такого же количества карт второго. Если у первого выпала зелёная, то второй выиграет во всех случаях, кроме одного; если красная, то второй либо выкладывает синюю и побеждает, либо выкладывает красную и попадает в аналогичную игру с меньшим числом карт; если у первого синяя, то второй имеет шанс на выигрыш, только если выложит синюю и попадёт в новую игру со всеми красными). Кроме этого, $u(1,0,0)=1,$ $u(0,1,0)= u(0,0,1)= 0$ .

Легко проверить (догадаться сложнее... можно, например, угадать формулу, вручную посчитав вероятности для малых $r,g,b$ ), что эти равенства задают формулу

(r⋅(g+1) g⋅b g⋅(g− 1)) 1 u(r,g,b)= g-+b+-1 +g-+b−-1 +--g+-b- ⋅r+-g+b-

при $g+ b>1$ . Тогда

u(n,n,n)= 1 +----12--- > 1 2 6n(4n − 1) 2

при всех $n > 0$ , в том числе и при $n = 10$ .

Ответ: да

Ошибка.
Попробуйте повторить позже

Задача 19#76745

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

Подсказки к задаче

Подсказка 1

Попробуем воспроизвести процесс и начать красить. Провели прямую - покрасили 2 зоны. Теперь проведем вторую прямую - что нужно сделать, чтобы условие снова выполнялось?

Показать доказательство

Докажем индукцией по $n$ . База очевидна. Рассмотрим $n+ 1$ прямую и выкинем одну из них. Теперь по предположению все области можно раскрасить в два цвета так, как нам нужно. Вернём выкинутую прямую. Некоторые области она поделила на две. Раскрасим все области по одну сторону от неё в противоположный цвет. Заметим, что по-прежнему условие выполняется, а значит утверждение доказано.

Ошибка.
Попробуйте повторить позже

Задача 20#76750

$2n$ конфет как-то разложены по $n$ коробкам. Девочка и мальчик по очереди берут по конфете: первой выбирает девочка. Докажите индукцией по $n$ , что мальчик может выбирать конфеты так, чтобы две последние конфеты были из одной коробки, как бы ни действовала девочка.

Подсказки к задаче

Подсказка 1

Попробуем оценить количество конфет в каждой из коробок. В каких случаях можно сразу обратить к предположению индукции? Когда нужно подождать пару ходов?

Показать доказательство

База при $n= 1$ очевидна. Переход: понятно, что есть коробка, в которой не более двух конфет.

Если есть коробка без конфет, забудем про неё и после двух первых произвольных ходов применим предположение.

Если её нет, но есть коробка с одной конфетой, то поступим так: если девочка возьмёт конфету из этой коробки, то мальчик сделает произвольный ход и далее можно применить предположение. Если же девочка не возьмёт оттуда конфету, то это сделает вторым ходом мальчик, и тогда снова можно применить предположение.

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

Предыдущий раздел

Следующий раздел