РЕШУ ОЛИМП, математика: задания, ответы, решения

Поиск
?

в условии в решении в тексте к заданию в атрибутах
Скопировать ссылку на результаты поиска
Класс: 10 11 6 7 8 9
Атрибут

Всего: 96 1–20 | 21–40 | 41–60 | 61–80 | 81–96

Добавить в вариант

Тип 21 № 1858 Добавить в вариант

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

Развернуть

Решение · Помощь

Тип 21 № 1853 Добавить в вариант

1.1 Докажите, что в любой момент может произойти миграция.

Решение · Помощь

Тип 0 № 1949 Добавить в вариант

Клетки доски 2015 × 2015 раскрашены в шахматном порядке так, что угловые клетки черные. На одну из черных клеток поставлена фишка, а некоторая другая черная клетка отмечена. За ход разрешается переместить фишку на соседнюю клетку. Всегда ли можно обойти фишкой все клетки доски, побывав на каждой из них ровно по одному разу, и закончить обход в отмеченной клетке? (Две клетки являются соседними, если имеют общую сторону.)

Решение.

Индукцией по n докажем, что для любых двух черных клеток A и B доски $левая круглая скобка 2 n плюс 1 правая круглая скобка \times левая круглая скобка 2 n плюс 1 правая круглая скобка$ найдется путь фишки, начинающийся в A, проходящий по всем клеткам доски и заканчивающийся в B.

База $n=1.$ Возможны два размещения черных клеток A и B: в соседних угловых клетках и в противоположных угловых клетках. С точностью до поворота доски они разобраны на верхних двух рисунках.

Переход от n к $n плюс 1.$

Если клетки A и B можно накрыть доской $левая круглая скобка 2 n плюс 1 правая круглая скобка \times левая круглая скобка 2 n плюс 1 правая круглая скобка ,$ ни один из углов которой не совпадает с углом доски $левая круглая скобка 2 n плюс 3 правая круглая скобка \times левая круглая скобка 2 n плюс 3 правая круглая скобка ,$ то подправим путь фишки из A в B, обходящий доску $левая круглая скобка 2 n плюс 1 правая круглая скобка \times левая круглая скобка 2 n плюс 1 правая круглая скобка ,$ следующим образом. В какой-то момент путь попадет в вершину, помеченную на рисунке буквой c (рис. а). Тогда с точностью до симметрии фишка шла по маршруту $d arrow c arrow e.$ Перенаправим ее из d в f, затем по часовой стрелке по каемке доски до g и потом в c.

Если так накрыть клетки A и B нельзя, то хотя бы одна из них находится на границе доски $левая круглая скобка 2 n плюс 3 правая круглая скобка \times левая круглая скобка 2 n плюс 3 правая круглая скобка .$ Пусть для определенности это клетка A (в противном случае A и B можно поменять ролями, рассмотрев обратный путь). Если клетка B расположена не на краю, то сделаем обход таким образом. От клетки A пойдем по каемке против часовой стрелки до клетки c, затем на клетку A′ и после этого по маршруту от A′ до B, который существует по предположению индукции (рис. б).

Рис. а

Рис. б

Рис. в

Если же клетка B также расположена на краю, то сделаем обход иначе. Отметим следующую за B по часовой стрелке клетку c и соседнюю с ней черную клетку в квадрате $левая круглая скобка 2 n плюс 1 правая круглая скобка \times левая круглая скобка 2 n плюс 1 правая круглая скобка$   — клетку A′. Также отметим следующую за A по часовой стрелке клетку d и соседнюю с ней черную клетку в квадрате $левая круглая скобка 2 n плюс 1 правая круглая скобка \times левая круглая скобка 2 n плюс 1 правая круглая скобка$   — клетку B′. Клетки c и d не могут оказаться угловыми, поскольку они белые, а угловые клетки по условию черные. От клетки A пойдем по каемке против часовой стрелки до клетки c, затем на клетку A′ и после этого по маршрут от A′ до B′, потом на d и дальше по каемке до B (рис. в).

Ответ: да.

Решение · Помощь

Тип 21 № 1955 Добавить в вариант

1.3 Докажите, что число колоний на данном острове никогда не превысит количество соседних с ним островов более, чем на 1.

Развернуть

Решение · Помощь

Тип 21 № 1853 Добавить в вариант

1.1 Докажите, что в любой момент может произойти миграция.

Решение · Помощь

Тип 21 № 1993 Добавить в вариант

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

Развернуть

Решение · Помощь

Тип 21 № 1853 Добавить в вариант

1.1 Докажите, что в любой момент может произойти миграция.

Решение · Помощь

Тип 21 № 1995 Добавить в вариант

1.4 Пусть изначально на каждом острове обитает одна колония, и пусть один из островов имеет d соседних. Чему может равняться максимально возможное количество колоний, способных поселиться на этом острове?

Развернуть

Решение.

Пример. Докажем, что в вершине степени d может собраться $d плюс 1$ колония. Подвесим дерево за эту вершину как за корень и будем доказывать, что в каждой вершине, из которой вниз идет e рёбер, можно собрать $e плюс 1$ колонию, проводя только миграции в её поддереве. Докажем это «индукцией от нижних вершин к верхним». Для листьев утверждение очевидно (в них и так есть одна колония), а в для любой другой вершины достаточно собрать нужное количество колоний в её непосредственных потомках, после чего проделать по одной миграции для каждого из них.

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

Доказываем индукцией по числу миграций. База  — ноль миграций, очевидна.

Переход. Пусть вот-вот произойдёт миграция с острова v. По ИП все находящиеся на нем колонии  — с него и соседних островов. Раз можно мигрировать, по ИП на острове есть колонии хотя бы с $\deg v минус 1$ соседних островов; отправим их обратно на свои острова. Если есть колония с оставшегося соседнего острова, тоже отправим её обратно, если есть своя колония, отправим её на любой из соседних островов

Ответ: $d плюс 1.$

Решение · Помощь

Тип 21 № 1853 Добавить в вариант

1.1 Докажите, что в любой момент может произойти миграция.

Решение · Помощь

Тип 0 № 2119 Добавить в вариант

Числа u и v являются корнями квадратного трехчлена $x в квадрате плюс ax плюс b$ с целыми коэффициентами. Для любого натурального n докажите, что если a² делится на b, то $u в степени левая круглая скобка 2n правая круглая скобка плюс v в степени левая круглая скобка 2n правая круглая скобка$ делится на bⁿ.

Решение · Помощь

Тип 0 № 2202 Добавить в вариант

Окружность $S_1,$ которая касается параболы $y=x в квадрате$ в ее вершине, имеет диаметр 1. Каждая из последующих окружностей S₂, S₃, S₄, ... касается внешним образом предыдущей окружности и ветвей параболы. Найдите радиус окружности S₂₀₁₇.

Критерии проверки:

Вид погрешности или ошибки	Отметка в работе	Баллы
Каждая задача оценивается по 10-балльной шкале и снабжается отметкой в работе 0, −, ∓, ±, + в соответствии с критериями.
Решение задачи верное, выбран рациональный путь решения	+	10
Решение верное, но путь не рационален или имеются один  — три недочета или негрубая ошибка	+	9
Решение верное, но путь не рационален и имеются один  — три недочета или негрубая ошибка	±	7−8
Ход решения верный, но есть несколько негрубых ошибок или решение не завершено	∓	5−6
Допущены грубые ошибки, но ответ получен (неверный)	∓	3−4
Допущены грубые ошибки и ответ не получен либо решение лишь начато, то что начато  — без ошибок	−	2
Решение начато, но продвижение ничего не дает для результата	−	1
Задача не решилась	0	0
Недочеты: незначительные (непринципиальные) арифметические ошибки. Негрубые ошибки: технические ошибки в применении формул и теорем, не влияющие на смысл решения; необоснованность логических (верных) выводов. Грубые ошибки:    I.  Логические, приводящие к неверному заключению.   II.  Арифметические ошибки, искажающие смысл ответа. III.  Неверный чертеж в геометрических задачах. IV.  Принципиальные ошибки в применении элементарных формул и теорем.

Решение · Критерии · Помощь

Тип 0 № 2236 Добавить в вариант

Окружность единичного радиуса поделили на $2 в степени левая круглая скобка 2019 правая круглая скобка$ равных частей. Докажите, что расстояние от центра окружности до хорды, стягивающей одну такую часть, составляет ровно половину от величины

$\underbrace корень из: начало аргумента: 2 плюс корень из: начало аргумента: 2 плюс ... плюс корень из: начало аргумента: 2 конец аргумента конец аргумента конец аргумента _2018 двоек.$

Критерии проверки:

Вид погрешности или ошибки	Отметка в работе	Баллы
Каждая задача оценивается по 10-балльной шкале и снабжается отметкой в работе 0, −, ∓, ±, + в соответствии с критериями.
Решение задачи верное, выбран рациональный путь решения	+	10
Решение верное, но путь не рационален или имеются один  — три недочета или негрубая ошибка	+	9
Решение верное, но путь не рационален и имеются один  — три недочета или негрубая ошибка	±	7−8
Ход решения верный, но есть несколько негрубых ошибок или решение не завершено	∓	5−6
Допущены грубые ошибки, но ответ получен (неверный)	∓	3−4
Допущены грубые ошибки и ответ не получен либо решение лишь начато, то что начато  — без ошибок	−	2
Решение начато, но продвижение ничего не дает для результата	−	1
Задача не решилась	0	0
Недочеты: незначительные (непринципиальные) арифметические ошибки. Негрубые ошибки: технические ошибки в применении формул и теорем, не влияющие на смысл решения; необоснованность логических (верных) выводов. Грубые ошибки:    I.  Логические, приводящие к неверному заключению.   II.  Арифметические ошибки, искажающие смысл ответа. III.  Неверный чертеж в геометрических задачах. IV.  Принципиальные ошибки в применении элементарных формул и теорем.

Решение · Критерии · Помощь

Тип 0 № 2289 Добавить в вариант

Решите уравнение с тремя неизвестными $X в степени Y плюс Y в степени Z =XYZ$ в натуральных числах.

Решение · Помощь

Тип 0 № 2456 Добавить в вариант

В одной из клеток таблицы n × n стоит фишка. За один ход можно переместить фишку из произвольной клетки k-го столбца $левая круглая скобка 1 меньше или равно k меньше или равно n правая круглая скобка$ в произвольную клетку k-й строки. При каких n существует такая последовательность из n² ходов, что фишка побывает во всех клетках таблицы и вернется в исходную клетку?

Решение · Помощь

Тип 0 № 2469 Добавить в вариант

Дано натуральное число x, десятичная запись которого n-значная и не содержит нулей. Числа x и x₂ в десятичной системе одинаково читаются слева направо и справа налево. Найдите все n, при которых такое x существует.

Критерии проверки:

Общая схема:

0 баллов  — выставляется, если участник к решению задачи не приступал или начатый ход решения полностью неверен;

1 балл  — выставляется, если участник приступил к решению задачи, указал верное направление решения задачи и получил правильные промежуточные результаты, но при этом не продвинулся настолько, чтобы можно было судить о том, каким образом он собирался получить окончательный ответ (то есть весь ход решения не представлен);

2 балла  — выставляется, если выбранный участником ход решения задачи является в принципе правильным, но при этом участник не смог его реализовать в силу серьёзных ошибок;

3 балла  — выставляется, если решение является в целом правильным, но содержит ошибки, повлиявшие на ответ;

4 балла  — выставляется, если участник решил задачу в целом правильно и получил верный ответ; при этом в решении допускаются незначительные неточности.

Факторы, влияющие на оценку.

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

2.  Правильный ответ к задаче, приведенный без достаточных обоснований, либо при наличии ошибок в решении, либо при отсутствии решения, не ведёт к увеличению оценки, которая выставляется участнику за данную задачу.

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

4.  Если задача решена перебором возможных вариантов, и при этом перебор неполный, то за задачу выставляется до 1 балла. Если участник подобрал частное решение без обоснования и проверил его правильность, то в этом случае за задачу выставляется до 0,5 баллов.

5.  Если задача решена при дополнительном предположении, которое отсутствует в условии, то за задачу выставляется

а)  до 1 балла, если это предположение можно доказать;

б)  до 0,5 баллов, если оно не обязано выполняться, но не противоречит условию задачи;

в)  0 баллов, если оно противоречит условию.

6.  Если в работе приведены два решения или ответа к одной задаче, противоречащие друг другу, то за задачу ставится 0 баллов.

Решение · Критерии · Помощь

Тип 0 № 2487 Добавить в вариант

Натуральное число x в восьмеричной системе 2019-значное, его младшая цифр равна 3, все остальные цифры отличны от 3 и совпадают через одну. Число y получается записью цифр x в обратном порядке. Оказалось, что восьмеричное представление $x умножить на y$   содержит только цифры 1 и 6. Найдите $x умножить на y$   (в восьмеричной системе).

Критерии проверки:

Общая схема:

Факторы, влияющие на оценку.

а)  до 1 балла, если это предположение можно доказать;

б)  до 0,5 баллов, если оно не обязано выполняться, но не противоречит условию задачи;

в)  0 баллов, если оно противоречит условию.

Решение · Критерии · Помощь

Тип 0 № 3179 Добавить в вариант

Доказать тождество

$1 плюс 2 в кубе плюс 3 в кубе плюс ... плюс n в кубе = левая круглая скобка дробь: числитель: n левая круглая скобка n плюс 1 правая круглая скобка , знаменатель: 2 конец дроби правая круглая скобка в квадрате .$

Решение · Помощь

Тип 0 № 3234 Добавить в вариант

Доказать тождество

$1 умножить на 2 плюс 2 умножить на 3 плюс 3 умножить на 4 плюс ... плюс n левая круглая скобка n плюс 1 правая круглая скобка = дробь: числитель: n левая круглая скобка n плюс 1 правая круглая скобка левая круглая скобка n плюс 2 правая круглая скобка , знаменатель: 3 конец дроби .$

Решение · Помощь

Тип 0 № 3913 Добавить в вариант

Последовательность a_n задана следующим образом: $a_1=2 в степени левая круглая скобка 20 правая круглая скобка ,$ $a_n плюс 1 = s левая круглая скобка a_n правая круглая скобка$ при всех n, где s(a) означает сумму цифр натурального числа а. Найдите a₁₀₀.

Решение · Помощь

Тип 0 № 3923 Добавить в вариант

В квадрате со стороной 1 отметили 53 точки, из которых четыре являются вершинами квадрата, а остальные (произвольные) 49 точек лежат внутри. Докажите, что найдется треугольник с отмеченными вершинами, имеющий площадь не более 0,01.

Решение.

Пусть в квадрате отмечено n точек: 4 вершины квадрата и $n минус 4$ точки внутри $левая круглая скобка n больше 4 правая круглая скобка .$ Докажем по индукции, что квадрат можно разбить на треугольники с отмеченными вершинами, причем число треугольников равно $2 n минус 6.$ К такому выражению нетрудно прийти рассматривая значения $n=5$ и $n=6.$

База индукции очевидна: при $n=5$ имеем 4 треугольника с общей вершиной внутри квадрата.

Пусть для $n= k$ квадрат разбит на $2 k минус 6$ треугольников, и мы добавляем $левая круглая скобка k плюс 1 правая круглая скобка$ -ую отмеченную точку M. Если она оказалась внутри некоторого треугольника ABC данного разбиения, то мы получим три новых треугольника MAB, MBC, MAC вместо «старого») треугольника ABC.

Таким образом, число треугольников при добавлении новой вершины стало равно

$2 k минус 6 плюс 2=2 левая круглая скобка k плюс 1 правая круглая скобка минус 6,$

и тем самым индукционный переход доказан.

Если же точка M попала на сторону, скажем, AB треугольника ABC, то AB является общей стороной треугольника ABC и некоторого другого треугольника разбиения  — скажем, треугольника АВD. В этом случае будем иметь 4 новых треугольника AMD, BMD, AMC, BMC вместо двух «старых» треугольников АBC и АBD, и тем самым опять количество треугольников увеличилось на 2. Итак, при $n=53$ получим разбиение квадрата на $2 умножить на 53 минус 6=100$ треугольников с отмеченными вершинами и поэтому в единичном квадрате найдется треугольник площади не более 0,01.

Решение · Помощь

Тип 0 № 4393 Добавить в вариант

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

Решение.

Достаточность такого количества туземцев доказывается по индукции. Действительно, для $k=1$ достаточно двух туземцев, которые переправляются вместе на другой берег. Если для $k=m$ достаточно 2^m туземцев, то для $k=m плюс 1$ сначала (в соответствии с предположением индукции) могут переправиться на правый берег 2^m туземцев, каждый из которых узнает при этом не менее m анекдотов, а затем каждый из них поочередно переплывает по одному разу на левый берег и перевозит оттуда одного из оставшихся там $2 в степени левая круглая скобка m правая круглая скобка$ туземцев, узнав по дороге его анекдот и рассказав ему не менее $m плюс 1$ анекдота, известного ему на тот момент. В результате каждый из $2 в степени левая круглая скобка m плюс 1 правая круглая скобка$ туземцев узнает не менее $m плюс 1=k$ новых анекдотов.

Остается показать, что меньшего числа туземцев недостаточно.

Способ I. Облегчим задачу: пусть N туземцев не переправляются через реку, а просто совершают не более $N минус 1$ прогулки вдвоем по озеру с возвращением в компанию. Докажем, что даже в этой задаче $N больше или равно 2 в степени левая круглая скобка k правая круглая скобка .$

Построим граф: вершины  — туземцы, ребро соединяет плывших вместе. В этом графе N вершин и $N минус 1$ ребро (если некоторые пары катались вместе более одного раза, то в этом графе есть кратные ребра). Если N для данного k выбрано минимальным, то этот граф связен. Действительно, в противном случае рассмотрим компоненту связности, в которой ребер меньше, чем вершин (при этом их меньше максимум на 1 в силу связности), и выполним только рейсы из этой компоненты. Раз этот граф связен и имеет $N минус 1$ ребро, он является деревом (в частности, не имеет кратных ребер).

Докажем теперь при помощи индукции по k, что $N больше или равно 2 в степени левая круглая скобка k правая круглая скобка .$ База очевидна. Для доказательства шага выкинем из графа ребро, соответствующее первому рейсу. Граф распадется на 2 компоненты связности. В каждой знают не более одного анекдота из другой компоненты. Значит, каждый знает не менее k анекдотов из своей компоненты (считая свой). По предположению индукции, в каждой из компонент не менее $2 в степени левая круглая скобка k минус 1 правая круглая скобка$ туземцев, а всего  — не менее 2^k.

Способ II. Назовем индексом туземца число известных ему анекдотов сверх своего. Туземцев с ненулевым индексом назовем богатыми, остальных  — бедными, а капиталом туземца с индексом z назовем число 2^−m (здесь следует отметить, что так определенный капитал уменьшается с ростом количества анекдотов, известных туземцу).

Для моментов времени, в которые лодка находится на правом берегу, вычислим число S как сумму капиталов всех богатых туземцев (независимо от того, на каком берегу они находятся) минус количество L богатых туземцев на левом берегу. При первом появлении лодки на правом берегу $S=2 в степени левая круглая скобка минус 1 правая круглая скобка плюс 2 в степени левая круглая скобка минус 1 правая круглая скобка минус 0=1.$ Докажем, что S по мере переправы не уменьшается. Между последовательными попаданиями лодки на правый берег возможны 3 вида случаев: количество богатых туземцев в лодке на пути с левого берега на правый оказалось равным 0, 1 или 2.

В случае нуля богатых туземцев в лодке двое бедных по дороге на правый берег стали богатыми и увеличили S на $2 в степени левая круглая скобка минус 1 правая круглая скобка плюс 2 в степени левая круглая скобка минус 1 правая круглая скобка =1.$ Но на левый берег лодку перегонял богатый туземец, который на левом берегу и остался, увеличив L на 1. Значит, в этом случае S не изменилась.

Рассмотрим случай одного богатого туземца в лодке. Число L в этом случае не изменилось. Севший в лодку богатый знал (помимо своего) m анекдотов, его капитал был равен 2^−m. Теперь он и его спутник знают (помимо своих) по $m плюс 1$ анекдоту, и сумма их капиталов равна $2 в степени левая круглая скобка минус m минус 1 правая круглая скобка плюс 2 в степени левая круглая скобка минус m минус 1 правая круглая скобка =2 в степени левая круглая скобка минус m правая круглая скобка ,$ то есть вновь S не изменилась.

Наконец, в случае двух богатых туземцев в лодке число L уменьшается на 1, а сумма капиталов приплывших на правый берег богатых туземцев уменьшается, но, будучи изначально не более $2 в степени левая круглая скобка минус 1 правая круглая скобка плюс 2 в степени левая круглая скобка минус 1 правая круглая скобка =1,$ она уменьшается менее чем на 1. Тем самым, в итоге S увеличилась.

Итак, в конце $S больше или равно 1, L=0,$ а капитал каждого туземца не более 2^–k. Значит, туземцев не менее 2^k.

Ответ: 2^k.

Решение · Помощь

Тип 0 № 4426 Добавить в вариант

На олимпиаду пришло 2018 участников, некоторые участники знакомы между собой. Будем говорить, что несколько попарно знакомых участников образуют «кружок», если любой другой участник олимпиады не знаком с кем-то из них. Докажите, что можно рассадить всех участников олимпиады по 90 аудиториям так, что ни в какой аудитории не сидят все представители какого-либо «кружка».

Решение.

Докажем индукцией по k более общее утверждение: 2k аудиторий хватит для того, чтобы рассадить $n меньше или равно k в квадрате$ участников. Тогда для получения утверждения задачи достаточно будет подставить $k=45,$ поскольку $2018 меньше или равно 2025=45 в квадрате .$

База $k=1,2.$ Поскольку $2 k больше или равно k в квадрате ,$ мы можем посадить каждого участника в отдельную аудиторию.

Пусть утверждение доказано, когда количество участников не больше $левая круглая скобка k минус 1 правая круглая скобка в квадрате .$ Докажем утверждение, когда количество участников не больше $k в квадрате .$ Рассмотрим участника v с наибольшим числом d знакомых. Если $d больше или равно 2 k минус 2,$ то посадим v в одну аудиторию, всех его знакомых во вторую, а оставшихся

$n минус 1 минус d меньше или равно k в квадрате минус 1 минус левая круглая скобка 2 k минус 2 правая круглая скобка = левая круглая скобка k минус 1 правая круглая скобка в квадрате$

по предположению индукции мы можем рассадить в $2 левая круглая скобка k минус 1 правая круглая скобка$ аудиторий так, что в этих аудиториях не будет «кружков». В первой аудитории только один человек, поэтому «кружков» там быть не может, во второй аудитории нет «кружков», так как там нет v, но он знаком со всеми из этой аудитории.

Если же $d меньше 2 левая круглая скобка k минус 1 правая круглая скобка ,$ то заметим, что нам заведомо хватит $d плюс 1 меньше или равно 2 k$ аудиторий. Выделим $d плюс 1$ аудиторий и будем рассаживать участников по очереди так, чтобы никакие два знакомых не сидели в одной аудитории, тогда в одной аудитории не будут образовываться «кружки» (люди, сидящие в одной аудитории, не знакомы друг с другом). У каждого участника не больше чем d знакомых, так как аудиторий $d плюс 1,$ то всегда есть аудитория, где нет его друзей, куда мы его и посадим.

Комментарий.

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

Задача отыскания точных оценок кликового хроматического числа как в общем случае, так и для многих важных классов графов весьма далека от своего решения. В нашем случае речь шла как раз о произвольном графе: фактически в задаче требовалось доказать, что кликовое хроматическое число произвольного графа на n вершинах не превосходит $2 корень из: начало аргумента: n конец аргумента .$ Сейчас наилучшая известная верхняя оценка $корень из: начало аргумента: 2 n конец аргумента ,$ и это лишь в константу раз лучше, чем требует наша задача. Известно также, что для каждого n существует граф на n вершинах, кликовое хроматическое число которого не меньше $c корень из: начало аргумента: дробь: числитель: n , знаменатель: натуральный логарифм n конец дроби конец аргумента$ для некоторой константы c. Таким образом, между верхними и нижними оценками сохраняется зазор в корень из логарифма раз, и этот зазор кому-то предстоит устранить  — возможно, кому-то из читающих эту брошюру!

Отметим и один из интереснейших классов графов. Это так называемые геометрические графы. У них вершины  — точки в пространстве (или даже просто на плоскости), а ребра соединяют пары точек, находящихся на расстоянии не больше 1. Эти графы важны для таких классических задач комбинаторики, как проблема Нелсона-Хадвигера раскраски пространства, проблема Борсука и др. (см. брошюры А. М. Райгородского «Хроматические числа», «Проблема Борсука» (М.: МЦНМО, 2015); про разные вариации на тему этих графов уже бывали задачи на МMO  — например, задача 6 для 10 класса в варианте 2010 года). Так вот для этих графов даже в случае плоскости зазор между верхними и нижними оценками аж от 3 до 9!

Решение · Помощь

Тип 0 № 4463 Добавить в вариант

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

Решение.

Пусть a и b  — числа, стоящие слева и справа от курсора соответственно, и число b состоит из n цифр. Тогда по условию $10 в степени левая круглая скобка n правая круглая скобка a плюс b$ делится на 7. Если между числами a и b вставить одну цифру x, то получим число $10 в степени левая круглая скобка n плюс 1 правая круглая скобка a плюс 10 в степени левая круглая скобка n правая круглая скобка x плюс b.$ Можно подобрать эту цифру так, чтобы это число также делилось на 7, так как при $x=0, 1, 2, \ldots, 6$ такие числа имеют различные остатки при делении на 7. По индукции докажем, что если вставить m цифр x, $m больше или равно 1,$ то получившееся число также будет делиться на 7 База индукции $левая круглая скобка m=1 правая круглая скобка$ проверена выше. Для шага индукции достаточно доказать, что разность

$\overlinea \underbracexx \ldots x _m плюс 1 раз b минус \overlinea \underbracexx \ldots x_m разb$

делится на 7, где $\overlinea b$ означает число, составленное из последовательно приписанных друг к другу записей чисел (цифр) a и b. Эта разность при некотором $k больше m$ равна

$10 в степени левая круглая скобка k плюс 1 правая круглая скобка a минус 10 в степени левая круглая скобка k правая круглая скобка левая круглая скобка x минус a правая круглая скобка =10 в степени левая круглая скобка k минус m правая круглая скобка левая круглая скобка 10 в степени левая круглая скобка m плюс 1 правая круглая скобка a плюс 10 в степени левая круглая скобка m правая круглая скобка x минус 10 в степени левая круглая скобка m правая круглая скобка a правая круглая скобка$

и имеет тот же остаток при делении на 7, что и число

$10 в степени левая круглая скобка k минус m правая круглая скобка левая круглая скобка 10 в степени левая круглая скобка m плюс 1 правая круглая скобка a плюс 10 в степени левая круглая скобка m правая круглая скобка x плюс b правая круглая скобка ,$

а последнее делится на 7 по предположению индукции.

Приведем другое решение.

Пусть а и b  — те Же, что и в первом способе. После вставки m цифр x полученное число имеет вид

$a умножить на 10 в степени левая круглая скобка m плюс n правая круглая скобка плюс \underbrace\overlinex x \ldots x_m \text paз умножить на 10 в степени левая круглая скобка n правая круглая скобка плюс b.$

Подберем цифру x так, чтобы при любом $m принадлежит N$ это число делилось на 7. Вычтем из него по условию делящееся на 7 число $10 в степени левая круглая скобка n правая круглая скобка a плюс b .$ Получим число

$10 в степени левая круглая скобка n правая круглая скобка левая круглая скобка 10 в степени левая круглая скобка m правая круглая скобка минус 1 правая круглая скобка a плюс \underbrace\overlinex x \ldots x_m \text paз умножить на 10 в степени левая круглая скобка n правая круглая скобка =10 в степени левая круглая скобка n правая круглая скобка левая круглая скобка 10 в степени левая круглая скобка m правая круглая скобка минус 1 правая круглая скобка a плюс 10 в степени левая круглая скобка n правая круглая скобка x умножить на дробь: числитель: 10 в степени левая круглая скобка m правая круглая скобка минус 1, знаменатель: 9 конец дроби =10 в степени левая круглая скобка n правая круглая скобка левая круглая скобка 9 a плюс x правая круглая скобка умножить на дробь: числитель: 10 в степени левая круглая скобка m правая круглая скобка минус 1, знаменатель: 9 конец дроби .$

Цифру x можно подобрать в зависимости от остатка от деления числа a на 7 так, чтобы число $2 a плюс x,$ а значит и $9 a плюс x,$ делилось на 7. Это соответствие можно указать явно с помощью следующей таблицы:

a (mod 7)	0	1	2	3	4	5	6
цифра x	0 или 7	5	3	1	6	4	2

Решение · Помощь

Тип 0 № 4472 Добавить в вариант

На доске написано несколько чисел. Разрешается стереть любые два числа a и b, а затем вместо одного из них написать число $дробь: числитель: a плюс b, знаменатель: 4 конец дроби .$ Какое наименьшее число может остаться на доске после 2018 таких операций, если изначально на ней написано 2019 единиц?

Решение.

Пусть m_n  — наименьшее число, которое можно получить из n единиц после $n минус 1$ операций. Заметим, что

$m_n=\min_\substackp плюс q=n, p, q принадлежит N дробь: числитель: m_p плюс m_q, знаменатель: 4 конец дроби$

при всех $n больше или равно 2.$ Действительно, как бы мы ни получили наименьшее число m_n, оно равно $дробь: числитель: x плюс y, знаменатель: 4 конец дроби ,$ где числа x и y были получены на предыдущем шаге. Пусть x получено из p единиц исходного набора, а y  — из оставшихся $n минус p=q$ единиц. Если $x больше m_p$ или $y больше m_q$ (предположим для определенности, что $x больше m_p правая круглая скобка ,$ то из исходного набора p единиц можно было бы получить меньшее число, не затрагивая второй набор.

Значит, на последнем шаге можно получить число, меньшее m_n, что противоречит определению m_n.

Докажем индукцией по n, что $m_n=f левая круглая скобка n правая круглая скобка ,$ где

$f левая круглая скобка n правая круглая скобка = дробь: числитель: 3 умножить на 2 в степени левая круглая скобка k правая круглая скобка минус n, знаменатель: 2 в степени левая круглая скобка 2 k плюс 1 правая круглая скобка конец дроби ,$

a $k=k левая круглая скобка n правая круглая скобка$ определяется из условия $2 в степени левая круглая скобка k правая круглая скобка меньше или равно n меньше 2 в степени левая круглая скобка k плюс 1 правая круглая скобка$ (то есть $k= левая квадратная скобка логарифм по основанию левая круглая скобка 2 правая круглая скобка n правая квадратная скобка правая круглая скобка .$ При $n=1, 2, 3$ это равенство проверяется непосредственно:

$m_1=1= дробь: числитель: 3 умножить на 1 минус 1, знаменатель: 2 в степени левая круглая скобка 1 правая круглая скобка конец дроби ,$ $m_2= дробь: числитель: 1, знаменатель: 2 конец дроби = дробь: числитель: 3 умножить на 2 минус 2, знаменатель: 2 в кубе конец дроби ,$ $m_3= дробь: числитель: 3, знаменатель: 8 конец дроби = дробь: числитель: 3 умножить на 2 минус 3, знаменатель: 2 в кубе конец дроби .$

Предположим, что оно верно для всех $n меньше или равно n_0,$ где $n_0 больше или равно 3,$ и докажем его для $n=n_0 плюс 1.$

Лемма. Наименьшее значение выражения $f левая круглая скобка p правая круглая скобка плюс f левая круглая скобка q правая круглая скобка$ при условии $p плюс q=n$ достигается при $p= левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка ,$ $q= левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка ,$ где обозначено $левая квадратная скобка x правая квадратная скобка = левая квадратная скобка x правая квадратная скобка ,$ [x]  — наименьшее целое число, не меньшеe x.

Доказательство. Обозначим $d левая круглая скобка n правая круглая скобка =f левая круглая скобка n правая круглая скобка минус f левая круглая скобка n плюс 1 правая круглая скобка .$ Пользуясь формулой для f(n), получаем $d левая круглая скобка n правая круглая скобка =2 в степени левая круглая скобка минус 2 k минус 1 правая круглая скобка ,$ где $2 в степени левая круглая скобка k правая круглая скобка меньше или равно n меньше 2 в степени левая круглая скобка k плюс 1 правая круглая скобка$ (это проверяется непосредственно как в случае $n меньше 2 в степени левая круглая скобка k плюс 1 правая круглая скобка минус 1,$ так и при $n=2 в степени левая круглая скобка k плюс 1 правая круглая скобка минус 1 правая круглая скобка .$ Из полученной формулы для d(n) следует, что $d левая круглая скобка n правая круглая скобка больше или равно d левая круглая скобка n плюс 1 правая круглая скобка ,$ поэтому $d левая круглая скобка p правая круглая скобка больше или равно d левая круглая скобка q правая круглая скобка$ при $p меньше или равно q.$

Пусть $1 меньше или равно p меньше или равно q меньше n$ и $p плюс q=n.$ Сравним значения $f левая круглая скобка p правая круглая скобка плюс f левая круглая скобка q правая круглая скобка$ и $f левая круглая скобка p плюс 1 правая круглая скобка плюс f левая круглая скобка q минус 1 правая круглая скобка .$ Их разность равна

$f левая круглая скобка p правая круглая скобка плюс f левая круглая скобка q правая круглая скобка минус f левая круглая скобка p плюс 1 правая круглая скобка минус f левая круглая скобка q минус 1 правая круглая скобка =d левая круглая скобка p правая круглая скобка минус d левая круглая скобка q минус 1 правая круглая скобка .$

Если $p меньше q,$ то $d левая круглая скобка p правая круглая скобка больше или равно d левая круглая скобка q минус 1 правая круглая скобка ,$ а значит,

$f левая круглая скобка p правая круглая скобка плюс f левая круглая скобка q правая круглая скобка больше или равно f левая круглая скобка p плюс 1 правая круглая скобка плюс f левая круглая скобка q минус 1 правая круглая скобка .$

Итак, если p пробегает значения от 1 до $левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка$ (то есть не превосходит q), то сумма $f левая круглая скобка p правая круглая скобка плюс f левая круглая скобка q правая круглая скобка$ не возрастает, а значит, ее наименьшее значение достигается при $p= левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка$ (соответственно, $q= левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка правая круглая скобка .$ Лемма доказана.

Из доказанной леммы и предположения индукции следует, что

$m_n= дробь: числитель: m_ левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка плюс m_ левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка , знаменатель: 4 конец дроби = дробь: числитель: f левая круглая скобка левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка правая круглая скобка плюс f левая круглая скобка левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка правая круглая скобка , знаменатель: 4 конец дроби .$

Остается убедиться, что

$дробь: числитель: f левая круглая скобка левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка правая круглая скобка плюс f левая круглая скобка левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка правая круглая скобка , знаменатель: 4 конец дроби =f левая круглая скобка n правая круглая скобка .$

Пусть k таково, что $2 в степени левая круглая скобка k правая круглая скобка меньше или равно n меньше 2 в степени левая круглая скобка k плюс 1 правая круглая скобка .$ Тогда $2 в степени левая круглая скобка k минус 1 правая круглая скобка меньше или равно левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка меньше 2 в степени левая круглая скобка k правая круглая скобка .$ Если $n меньше 2 в степени левая круглая скобка k плюс 1 правая круглая скобка минус 1,$ то

$2 в степени левая круглая скобка k минус 1 правая круглая скобка меньше или равно левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка меньше 2 в степени левая круглая скобка k правая круглая скобка$ и $f левая круглая скобка левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка правая круглая скобка = дробь: числитель: 3 умножить на 2 в степени левая круглая скобка k минус 1 правая круглая скобка минус левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка , знаменатель: 2 в степени левая круглая скобка 2 k минус 1 правая круглая скобка конец дроби .$

Если же $n=2 в степени левая круглая скобка k плюс 1 правая круглая скобка минус 1,$ то $левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка =2 в степени левая круглая скобка k правая круглая скобка ,$ и

$f левая круглая скобка левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка правая круглая скобка = дробь: числитель: 3 умножить на 2 в степени левая круглая скобка k правая круглая скобка минус 2 в степени левая круглая скобка k правая круглая скобка , знаменатель: 2 в степени левая круглая скобка 2 k плюс 1 правая круглая скобка конец дроби =2 в степени левая круглая скобка минус k правая круглая скобка = дробь: числитель: 3 умножить на 2 в степени левая круглая скобка k минус 1 правая круглая скобка минус 2 в степени левая круглая скобка k правая круглая скобка , знаменатель: 2 в степени левая круглая скобка 2 k минус 1 правая круглая скобка конец дроби = дробь: числитель: 3 умножить на 2 в степени левая круглая скобка k минус 1 правая круглая скобка минус левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка , знаменатель: 2 в степени левая круглая скобка 2 k минус 1 правая круглая скобка конец дроби ,$

то есть в обоих случаях имеем

Следовательно,

$m_n= дробь: числитель: f левая круглая скобка левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка правая круглая скобка плюс f левая круглая скобка левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка правая круглая скобка , знаменатель: 4 конец дроби = дробь: числитель: 3 умножить на 2 в степени левая круглая скобка k правая круглая скобка минус n, знаменатель: 2 в степени левая круглая скобка 2 k плюс 1 правая круглая скобка конец дроби =f левая круглая скобка n правая круглая скобка .$

При $n=2019$ получаем $k=10,$ и

$m_2019= дробь: числитель: 3072 минус 2019, знаменатель: 2 в степени левая круглая скобка 21 правая круглая скобка конец дроби = дробь: числитель: 1053, знаменатель: 2 в степени левая круглая скобка 21 правая круглая скобка конец дроби .$

Ответ: $дробь: числитель: 1053, знаменатель: 2 в степени левая круглая скобка 21 правая круглая скобка конец дроби .$

Приведем другое решение.

Пусть x  — число, получившееся после 2018 операций. Проследим, как было получено это число. Для этого «развернем» все операции в обратном направлении. При прямом применении операции два числа заменялись одним, поэтому при обратном каждое число мы будем заменять на два числа, из которых оно было получено (сохраняя деление на 4):

$дробь: числитель: a плюс b, знаменатель: 4 конец дроби \Rightarrow дробь: числитель: a, знаменатель: 4 конец дроби плюс дробь: числитель: b, знаменатель: 4 конец дроби .$

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

$дробь: числитель: a плюс 1, знаменатель: 4 конец дроби \Rightarrow дробь: числитель: 1, знаменатель: 4 конец дроби плюс дробь: числитель: a, знаменатель: 4 конец дроби = дробь: числитель: 2, знаменатель: 4 в квадрате конец дроби плюс дробь: числитель: 2, знаменатель: 4 в квадрате конец дроби плюс дробь: числитель: a, знаменатель: 4 конец дроби$

(если $a=1,$ то с этой единицей мы проделаем ту же процедуpy). Далее каждую степень двойки, стоящую в числителе и полученную когда-то из единицы, мы снова искусственно превращаем в сумму двух чисел:

$дробь: числитель: 2 в степени левая круглая скобка l правая круглая скобка , знаменатель: 4 в степени левая круглая скобка m правая круглая скобка конец дроби = дробь: числитель: 4 умножить на 2 в степени левая круглая скобка l правая круглая скобка , знаменатель: 4 в степени левая круглая скобка m плюс 1 правая круглая скобка конец дроби = дробь: числитель: 2 в степени левая круглая скобка l плюс 1 правая круглая скобка плюс 2 в степени левая круглая скобка l плюс 1 правая круглая скобка , знаменатель: 4 в степени левая круглая скобка m плюс 1 правая круглая скобка конец дроби = дробь: числитель: 2 в степени левая круглая скобка l плюс 1 правая круглая скобка , знаменатель: 4 в степени левая круглая скобка m плюс 1 правая круглая скобка конец дроби плюс дробь: числитель: 2 в степени левая круглая скобка l плюс 1 правая круглая скобка , знаменатель: 4 в степени левая круглая скобка m плюс 1 правая круглая скобка конец дроби .$

Таким образом, при каждом таком «разворачивании» операции в обратном направлении количество чисел удваивается. Поэтому в итоге мы получим представление числа x в виде дроби, в числителе которой стоит сумма 2048 чисел $левая круглая скобка 2 в степени левая круглая скобка 10 правая круглая скобка меньше 2019 меньше 2 в степени левая круглая скобка 11 правая круглая скобка =2048 правая круглая скобка ,$ каждое из которых есть некоторая степень двойки, а знаменатель равен 4¹¹.

Обозначим через a_k количество слагаемых вида a_k, $k=0, 1, \ldots,$ в числителе дроби, представляющей число x.

С учетом искусственного раздвоения единиц и чисел, получающихся из них, исходное количество единиц равно

$a_0 плюс дробь: числитель: a_1, знаменатель: 2 конец дроби плюс дробь: числитель: a_2, знаменатель: 4 конец дроби плюс \ldots$

Получаем следующую систему условий, равносильную исходной задаче:

$система выражений x= дробь: числитель: a_0 плюс 2 a_1 плюс 4 a_2 плюс \ldots, знаменатель: 4 в степени левая круглая скобка 11 правая круглая скобка конец дроби arrow \min , a_0 плюс дробь: числитель: a_1, знаменатель: 2 конец дроби плюс дробь: числитель: a_2, знаменатель: 4 конец дроби плюс \ldots=2019, a_0 плюс a_1 плюс a_2 плюс \ldots=2048. конец системы .$

Чтобы сделать число x наименьшим, необходимо обнулить как можно больше чисел a_k с большими коэффициентами (или, что то же самое, с большими номерами k). Для 2019 единиц достаточно положить $a_2=a_3=\ldots=0.$ Решением системы

$система выражений a_0 плюс дробь: числитель: a_1, знаменатель: 2 конец дроби =2019, a_0 плюс a_1=2048 конец системы .$

будут числа $a_0=1990$ и $a_1=58.$ Тогда

$x= дробь: числитель: 1990 плюс 116, знаменатель: 4 в степени левая круглая скобка 11 правая круглая скобка конец дроби = дробь: числитель: 2106, знаменатель: 2 в степени левая круглая скобка 22 правая круглая скобка конец дроби = дробь: числитель: 1053, знаменатель: 2 в степени левая круглая скобка 21 правая круглая скобка конец дроби .$

Заметим, что если изначально на доске было написано количество единиц, равное степени двойки, то можно положить $a_1=a_2=\ldots=0,$ то есть в этом случае можно взять отличным от нуля только a₀.

Решение · Помощь

Всего: 96 1–20 | 21–40 | 41–60 | 61–80 | 81–96