Тема ММО (Московская математическая олимпиада)

ММО - задания по годам → .01 ММО до 2010

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

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

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

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

Подтемы раздела ммо (московская математическая олимпиада)

Разделы подтемы ММО - задания по годам

ММО до 2010

ММО 2010

ММО 2011

ММО 2012

ММО 2013

ММО 2014

ММО 2015

ММО 2016

ММО 2017

ММО 2018

ММО 2019

ММО 2020

ММО 2021

ММО 2022

ММО 2023

ММО 2024

ММО 2025

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

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

Задача 1#106751

На плоскости даны оси координат с одинаковым, но не обозначенным масштабом и график функции

y = sinx, x ∈(0;α)

Как с помощью циркуля и линейки построить касательную к этому графику в заданной его точке, если:

(a) $(π ) α ∈ 2;π ;$

(b) $( ) α ∈ 0;π2 ?$

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

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

Подсказка 1, пункт (a)

На самом деле достаточно построить отрезок длины 1(иными словами, восстановить масштаб), ведь касательная имеет угловой коэффициент, равный cos(x) для заданной точки x. А как можно построить отрезок длины 1?

Подсказка 2, пункт (а)

Если удастся отметить точку π/2 на оси oX, то задача будет решена, ведь перпендикуляр к этой оси, проходящий через эту точку, пересекает график синуса в точке (π/2,1), и отрезок между точками пересечения единичный. А как построить эту точку?

Подсказка 3, пункт (а)

Конечно! Используем свойство sin(a) = sin(π-a)! Тогда отрезок между точками (a, sin(a)) и (a, sin(π-a)) параллелен оси oX. А что хорошего можно сказать о перпендикуляре к этому отрезку?

Подсказка 1, пункт (b)

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

Подсказка 2, пункт (b)

Точно! Выберем на оси oX некоторые a и b и построим отрезок длины sin(a) + sin(b). Легко построить и отрезок длины sin((a+b)/2). А можно ли построить отрезок длины, равной синусу полуразности?

Подсказка 3, пункт (b)

Его можно построить с помощью простых построений середин, но тогда не получится прийти к отрезку длины 1, поэтому нужно найти прямоугольный треугольник. Для этого его нужно построить! Пусть его прямой угол будет в одном конце отрезка длины sin(a) + sin(b) (и его первая вершина соответственно), а вторая — в другом конце этого отрезка. А как получить третью вершину?

Подсказка 4, пункт (b)

Верно! Надо использовать построенный ранее sin((a+b)/2)! Строим окружность радиуса 2sin((a+b)/2) с центром во второй вершине предполагаемого треугольника! Пересечение построенного ранее перпендикуляра к одному из концов отрезка длины sin(a) + sin(b) и этой окружности будет третьей точкой! Чему тогда равен угол этого треугольника при втором конце отрезка длины sin(a)+sin(b)?

Подсказка 5, пункт (b)

Точно! Он равен (a-b)/2! Как уже было отмечено, построить sin((a-b)/2) нетрудно! А как теперь его поместить в наш треугольник, чтобы в нем появился отрезок длины 1?

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

Касательная к графику функции $y = sinx,$ где $x∈ (0;α),$ проведённая в заданной его точке $(x ,sinx), 0 0$ имеет угловой коэффициент, т.е. тангенс угла наклона к оси $Ox,$ равный $cosx0,$ и для её построения при помощи циркуля и линейки достаточно построить отрезок длины $1.$ Действительно, имея отрезки $1$ и $sinx0,$ можно построить отрезок $|cosx0|$ (при помощи тригонометрического круга), а значит, и угол, тангенс которого равен $cosx0.$ Покажем, как построить отрезок длины $1$ (т.е. восстановить масштаб).

(a) Из точки $A =(a,sina),$ где $(π ) a ∈ 2,α ,$ лежащей на графике функции, опустим перпендикуляр на ось $Oy$ (рис. слева). Так как $sin(π− a)= sina,$ то этот перпендикуляр пересечёт график функции $y =sin x$ в точке $B =(π− a,sina).$ Через середину отрезка $AB$ проведём прямую, перпендикулярную оси $Ox.$ Она пересечёт график в точке $(π ) 2,1.$ Отрезок этой прямой от оси $Ox$ до графика функции $y =sinx$ имеет длину $1.$

$PIC$

(b) Здесь несколько труднее построить отрезок единичной длины. Остальные построения будут такими же.

Пусть $a$ и $b$ — произвольные точки на оси $Ox,$ удовлетворяющие условию $0< b< a< α.$ Построим отрезок $AB$ длины $sina+ sinb.$ Через точку $B$ проведём луч $l,$ перпендикулярный отрезку $AB.$ Окружность с центром в точке $A$ и радиусом $2sina+b 2$ пересекает луч $l$ в точке $C$ (рис. справа). Так как $sina+ sinb= 2sina+bcosa−b, 2 2$ то $∠CAB = a−b. 2$ На отрезке $BC$ отметим точку $D$ такую, что $BD = sin a−b. 2$ Через точку $D$ проведём прямую, параллельную отрезку $AB.$ Эта прямая пересечёт отрезок $AC$ в точке $E.$ Длина отрезка $AE$ равна $1,$ так как

a−-b BD- sin∠CAB =sin 2 = AE

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

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

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

Задача 2#60612

В кинотеатре семь рядов по 10 мест каждый. Группа из 50 детей сходила на утренний сеанс, а потом на вечерний. Докажите, что найдутся двое детей, которые на утреннем сеансе сидели в одном ряду и на вечернем тоже сидели в одном ряду.

Источники: ММО-2008, 8.2, автор - И.И.Осипов, (см. mmo.mccme.ru)

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

Подсказка 1

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

Подсказка 2

Теперь подсчитываем, сколько у нас пар из двух чисел, если числа от 1 до 7, и дорешиваем задачу

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

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

Назовём детей котиками, а ряды в кинотеатре — домиками. На утреннем сеансе по принципу Дирихле хотя бы $8$ котиков будут в одном домике (иначе всего котиков было бы не больше $7⋅7= 49$ , а их $50$ ). Назовём этих найденных котиков из одного домика зайчиками. После утра все котики покидают домики и снова приходят уже вечером. На вечернем сеансе заметим, что выбранные нами $8$ зайчиков садятся в $7$ домиков. По принципу Дирихле хотя бы двое будут в одном домике. Эти двое оказались в одном домике и утром, и вечером, что и требовалось.

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

Сопоставим каждому ребёнку пару из двух номеров рядов $(a,b),a,b∈ {1,...7}$ — соответственно для утреннего и вечернего сеанса, на которых он сидел. Всевозможных пар $(a,b)$ всего $7⋅7= 49$ , однако детей $50$ , поэтому по принципу Дирихле найдутся двое, у которых пары $(a,b)$ совпадают и они на утреннем и вечерних сеансах сидели на одинаковых рядах, что и требовалось.

Ответ:

что и требовалось доказать

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

Задача 3#73199

Найдите наименьшее натуральное $n,$ для которого число $nn$ не является делителем числа $2008!$

Источники: ММО-2008, 11.2(см. mmo.mccme.ru)

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

Подсказка 1

Можно ли ограничить n снизу, пользуясь определённой его степенью?

Подсказка 2

Заметим, что если n² ≤ 2008, то 2008! делится на nⁿ. Попробуйте оценить число 2008 через квадраты.

Подсказка 3

44² < 2008 < 45², какие n тогда можно рассматривать?

Подсказка 4

Нам будет достаточно проверять делимость 2008! на nⁿ при n > 45.

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

Если $n2 ≤2008,$ то $2008!$ делится на $nn$ (так как числа $n,2n,...,(n − 1)n$ и $n2$ содержатся среди чисел $1,2,...,2007,2008$ ). Так как $2 2 44 < 2008 <45 ,$ то достаточно проверить делимость $2008!$ на $n n$ при $n >45.$

Ясно, что $2008!$ делится на $45 45 90 45 =5 ⋅3 ,$ так как среди чисел $1,2,...,2007,2008$ заведомо найдётся $45$ чисел, кратных $5,$ и $90$ чисел, кратных $3$ ( $5⋅45= 22< 2008$ и $3⋅90= 270<2008$ ).

$2008!$ делится на $46 46 46 46 = 2 23 ,$ так как среди чисел $1,2,...,2007,2008$ заведомо найдётся $46$ чётных чисел и $46$ чисел, кратных $23$ ( $23⋅46= 1058< 2008$ ).

$2008!$ не делится на $47 47 ,$ так как число $47$ простое, и поэтому среди чисел $1,2,...,2007,2008$ есть лишь $42$ числа, кратных $47$ ( $47⋅42 =1974< 2008 <2021= 43 ⋅47$ ).

Ответ:

$47$

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

Задача 4#94426

Высоты $AA′$ и $CC′$ остроугольного треугольника $ABC$ пересекаются в точке $H$ . Точка $B 0$ — середина стороны $AC$ . Докажите, что точка пересечения прямых, симметричных $BB0$ и $HB0$ относительно биссектрис углов $ABC$ и $AHC$ соответственно, лежит на прямой $′ ′ A C .$

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

Подсказка 1

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

Подсказка 2

Итак, а теперь давайте вспомним следующий факт. Пусть нам дан угол C, на сторонах даны точки A, A', B, B', притом AB и A'B' антипараллельны, тогда медиана CAB будет симедианой у CA'B' и наоборот. Поищите такую конструкцию в задаче.

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

Отметим середину $A′C ′,$ обозначим её за точку $K.$

$PIC$

Так как четырехугольник $′ ′ AA C C$ вписанный, $′′ A C$ антипараллелен $AC$ относительно угла $ABC,$ и так как $BB0$ — медиана в $△ABC,$ то $BK$ является симедианой в $′′ △BA C$ (медианы при отражении переходят симедианы). Также заметим, что $′ ′ A C$ антипараллелен $AC$ относительно угла $AHC,$ и так как $HB0$ — медиана в $△AHC,$ то $HK$ является симедианой в $△AHC.$

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

Задача 5#38870

Чему может быть равно произведение нескольких различных простых чисел, если оно кратно каждому из них, уменьшенному на $1?$ Найдите все возможные значения.

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

Подсказка 1!

1) Давайте попробуем восстанавливать наши множители с самого начала. Важное свойство почти всех простых чисел - нечетность. Значит перемножение будет делиться на двойку!

Подсказка 2!

2) Итак, поняли, что одно из простых чисел это 2. Попробуем понять, что тогда может быть следующим по возрастанию множителем в числе. Пусть это p2. Тогда раз наше число делится на p2-1, чему может быть равно p2?

Подсказка 3!

3) Верно, p2-1 может быть только двойкой, тогда p2 это 3! Теперь попробуйте таким же раскручиванием цепочки довести ее до конца, до момента, когда все множители, которые могут получиться, будут составными!

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

Хотя бы одно из простых чисел нечётно, потому число кратно двум. Пусть это $N =p ⋅...⋅p ,p <p ,i∈ {1,...k− 1}, 1 k i i+1$ где $p =2. 1$ Далее будем находить числа по порядку

Число содержит $p2,$ делителем $p2− 1$ может быть только $2,$ поскольку остальные делители больше $p2− 1,$ откуда оно равно $2$ и $p2 = 3.$ Подойдёт $N = 6,$ пойдём дальше.

Число содержит $p3,$ делителями $p3− 1$ могут быть только $p1,p2,$ но оба они меньше $p3− 1,$ потому $p1⋅p2 = 6 ⇐⇒ p3 =7.$ Подойдёт $N =2 ⋅3 ⋅7 =42.$

Число содержит $p4,p4 − 1$ может быть равно только $p1p3 = 14,p1p2p3 = 42,$ поскольку $p1p2 <p3.$ В первом случае $15= 14+ 1$ составное, во втором $p4 = 43$ и подходит $N = 2⋅3⋅7⋅43 =1806.$

Пусть теперь число содержит $p5,$ отсюда $p5 − 1$ равно одному из чисел $p1p4 =86,p1p2p4 = 258,p1p3p4 = 602,p1p2p3p4 = 1806,$ где все числа, увеличенные на один, будут составными, откуда больше четырёх простых чисел быть не может.

Ответ:

$6,42,1806$

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

Задача 6#38127

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

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

Подсказка 1

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

Подсказка 2

Верно, значит, ветви парабол направлены вверх, причём всех трёх, так как старшие коэффициенты равны 1 и 2. Теперь попробуем использовать второе условие про корни. Что вы можете сказать про значение трёхчленов в точке 1000? Попробуйте подставить и узнать.

Подсказка 3

Ага, получаем, что изначальные трёхчлены в 1000 положительны. Понятно, что тогда и их сумма в точке 1000 положительна. Но разве, когда корни должны быть по разные стороны от 1000, такое может быть?

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

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

По условию трёхчлены приведённые, так что их старшие коэффициенты положительны (равны единичке у обоих), то же можно сказать и для их суммы. Посмотрим на графики двух данных в условии трёхчленов: это параболы с ветвями вверх, которые при $x =1000$ имеют положительные значения. Их сумма также даёт параболу с ветвями вверх и положительным значением в точке $x = 1000$ . Поэтому корни находятся так же по одну сторону, ведь иначе (когда $x= 1000$ находится между корнями) значение суммы при $x = 1000$ было бы отрицательным.

_________________________________________________________________________________________________________________________________________________________________________________

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

Параллельно перенесём графики данных трёхчленов на $1000$ влево. Это эквивалентно замене в условии задачи $1000$ на $0.$ Получим приведённые трёхчлены: $x2+ p1x +q1$ с отрицательными корнями и $x2+ p2x +q2$ с положительными корнями. По теореме Виета $q1 > 0$ и $q2 > 0.$ Сумма этих трёхчленов равна $2x2+ (p1+p2)x+(q1+ q2)$ , где $q1 +q2 > 0,$ поэтому её корни одного знака.

Ответ:

нет

Курсы

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

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

Задача 7#65394

Выражение $x4+ x3− 3x2 +x +2$ возвели в натуральную степень, раскрыли скобки и привели подобные слагаемые. Докажите, что хотя бы один коэффициент полученного выражения будет отрицательным.

Источники: ММО-2006, 9.4, автор М. Малкин (см. mmo.mccme.ru)

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

Подсказка 1

Пусть мы возвели многочлен в степень n. Наверное, один коэффициент-то мы точно сможем найти, например, свободный) Чему он равен?

Подсказка 2

Да, например, можно подставить x = 0 и получить как раз свободный коэф, он будет равен 2^n. А можем ли мы получить еще какую-то информацию, но уже про все коэффициенты многочлена?

Подсказка 3

Можно попробовать получить чему равна сумма всех коэффициенты....а как?

Подсказка 4

Да, можно просто подставить в многочлен x = 1! Тогда получим что сумма коэффициентов = (1^4+1^3-3*1^2+1+2)^n = 2^n! А может ли быть такое, что сумма всех коэффициентов = свободному, если все коэффициенты неотрицательны?)

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

Пусть мы возводим в степень $n.$ Сумму коэффициентов многочлена после раскрытия скобок можно посчитать, если вместо $x$ подставить единицу. Естественно она же равна значению того же многочлена в точке $x =1$ до раскрытия скобок:

4 3 2 n n (1 +1 − 3⋅1 + 1+2) = 2

Свободный член тоже можно посчитать, для этого надо подставить $x= 0.$ Получится

4 3 2 n n (0 +0 − 3⋅0 + 0+2) = 2

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

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

Задача 8#49151

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

Источники: ММО-2005, 10.2, автор - Е.Горский, (см. mmo.mccme.ru)

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

Подсказка 1

Есть две точки, которые лежат на графике, значит их координаты - это, скажем, А(а, Q(a)), B(b, Q(b)). Запишите теперь уравнение полученной прямой через коэффициент угла наклона (нам наверняка хочется, чтобы он был равен нулю).

Подсказка 2

Отлично, теперь запишите расстояние между этими двумя точками через эти заданные координаты (помним, это расстояние целое). Замечаем, что там есть выражение Q(a) - Q(b), подставим его из первого выражения, и теперь уже точно знаем, что коэффициент угла наклона равен 0 (осталось это доказать) :)

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

Пусть этот многочлен $Q(x)= a xn+...+a ,a ∈ℤ n 0 i$ , а на оси абсцисс отмечены $a,b$ , тогда их координаты $A(a,Q(a)),B (b,Q(b))$ . Используем теорему Безу

Q(a)− Q(b)= k(a − b), k∈ ℤ

Запишем квадрат расстояния между точками

2 2 2 2 2 2 ρ (A,B)= (a− b) +(Q(a)− Q(b)) = (a− b) (1+ k )=n , n∈ ℤ

Тогда $1 +k2$ является точным квадратом, что возможно только при $k =0$ , что и означает $AB ∥Ox$ .

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

Задача 9#84471

Дискриминанты трёх приведенных квадратных трёхчленов равны $1$ , $4$ и $9$ . Докажите, что можно выбрать по одному корню каждого из них так, чтобы их сумма равнялась сумме оставшихся корней.

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

Подсказка 1

У нас есть равенство сумм корней, так что можно в нём всё перенести в одну сторону. Тогда у нас появятся разности корней одного и того же трёхчлена. Что интересного можно сказать про них?

Подсказка 2

Попробуйте выразить разность корней через дискриминант квадратного трёхчлена.

Подсказка 3

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

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

Обозначим корни данных трёхчленов $x ≤ x,y ≤ y,z ≤ z 1 2 1 2 1 2$ (одной букве с разными индексами соответствуют корни одного трёхчлена).

Так как дискриминант равен квадрату разности между корнями, то (без ограничения общности для определённости обозначений)

x2 − x1 = 1,y2 − y1 = 2,z2− z1 = 3

Получаем

x2+ y2+ z1 =x1+ 1+ y1+2 +z2− 3

требуемое.

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

Задача 10#93237

Пусть $l ,l,l a b c$ — длины биссектрис углов $A,B$ и $C$ треугольника $ABC,$ а $m ,m ,m a b c$ — длины соответствующих медиан. Докажите, что

la lb lc ma-+ mb-+ mc > 1

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

Подсказка 1

Пусть a ≤ b ≤ c — стороны треугольника. Всякий отрезок внутри треугольника не превосходит длины его наибольшей стороны. Как тогда можно оценить выражение снизу?

Подсказка 2

Верно! Это выражение не меньше отношения суммы длин биссектрис, проведенных к сторонам a и b, к c. Осталось доказать, что сумма длин этих биссектрис превышает c. Можно ли для этого применить неравенство треугольника?

Подсказка 3

Из треугольника AIB имеем AI + IB > AB = c. Как тогда доказать требуемое неравенство?

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

Пусть $a,$ $b,$ и $c$ — длины сторон треугольника $ABC.$ Без ограничения общности можно считать, что $a≤ b≤ c.$ Пусть $I$ — точка пересечения биссектрис треугольника $ABC.$

$PIC$

Тогда

la+ -lb-+ lc-> la-+-lb-≥ la+lb> AI-+IB-> 1 ma mb mc ma mb c c

Здесь второе неравенство выполнено, поскольку любой отрезок внутри треугольника (в частности, любая медиана) не превосходит наибольшей стороны. Третье неравенство выполнено, поскольку $la >AI$ и $l > BI. b$ Последнее неравенство выполнено в силу неравенства треугольника для треугольника $AIB.$

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

Задача 11#67155

В семье $4$ человека. Если Маше удвоят стипендию, общий доход всей семьи возрастет на $5%,$ если вместо этого маме удвоят зарплату — на $15%,$ если же зарплату удвоят папе — на $25%.$ На сколько процентов возрастет доход всей семьи, если дедушке удвоят пенсию?

Источники: ММО-2003, 8.1 и отборочный этап Всесибирской олимпиады - 2016, 8 класс

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

Подсказка 1

Подумаем, откуда же взялись 5%, на которые увеличился доход семьи?) Что в его составе?

Подсказка 2

После того, как к общему доходу добавили 1 зарплату Маши, общий доход увеличился на 5%) Значит, заплата Маши это...?)

Подсказка 3

5% от общего дохода! Аналогично с мамой и папой, тогда несложно посчитать пенсию дедушки)

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

При удвоении стипендии Маши общий доход всей семьи увеличивается ровно на величину этой стипендии, значит, она составляет $5%$ от общего дохода. Аналогично, зарплаты мамы и папы составляют $15%$ и $25%.$ Значит, пенсия дедушки составляет $100 − 5− 15− 25 =55$ процентов. Если её удвоят, то доход семьи возрастёт на $55%.$

Ответ:

$55%$

Интенсивы

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

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

Задача 12#94493

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

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

Подсказка 1

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

Подсказка 2

Если не удалось присоединить все города, то найдется дорога, ведущая из города области (X) в город не из области (Y). Рассмотрите путь из Y в X. Поймите, что его можно пристроить к области. Как это сделать?

Подсказка 3

Закиньте города пути в губернии, где не содержится X. Почему это можно сделать?

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

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

Предположим, что область содержит не все города. Тогда найдётся дорога, ведущая из города области (обозначим его через $X )$ в город, ещё не принадлежащий автономной области (назовём его $Y).$ Рассмотрим несамопересекающийся путь (последовательность дорог), ведущий из $Y$ в $X.$

Предположим, что на этом пути есть город $Z,$ лежащий в автономной области. Тогда из $X$ можно добраться до $Z$ двумя несамопересекающимися путями: один путь идёт через $Y,$ а второй идёт только по городам области (такой путь существует, потому что для области выполнено условие задачи, как и для всей страны). Но это противоречит условию. Следовательно, путь из $Y$ в $X$ не содержит других городов из области, кроме $X.$

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

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

На каждом описанном шаге область увеличивается хотя бы на один город $(Y ).$ Следовательно, рано или поздно все города будут присоединены. В этот момент область совпадёт со всей страной и при этом будет разделена на губернии.

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

Задача 13#97421

В тюрьму поместили 100 узников. Надзиратель сказал им: "Я дам вам вечер поговорить друг с другом, а потом рассажу по отдельным камерам, и общаться вы больше не сможете. Иногда я буду одного из вас отводить в комнату, в которой есть лампа (вначале она выключена). Уходя из комнаты, вы можете оставить лампу как включенной, так и выключенной.

Если в какой-то момент кто-то из вас скажет мне, что вы все уже побывали в комнате, и будет прав, то я всех вас выпущу на свободу. А если неправ - скормлю всех крокодилам. И не волнуйтесь, что кого-нибудь забудут - если будете молчать, то все побываете в комнате, и ни для кого никакое посещение комнаты не станет последним."

Придумайте стратегию, гарантирующую узникам освобождение.

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

Подсказка 1

Мы знаем, что у каждого узника есть неограниченное количество посещений комнаты, могут ли они тогда как-нибудь посчитать количество посетивших?

Подсказка 2

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

Подсказка 3

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

Подсказка 4

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

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

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

Когда число посчитанных узников становится равным $99,$ “счётчик” говорит, что все узники уже побывали в комнате.

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

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

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

Задача 14#88923

Квадрат суммы цифр числа $A$ равен сумме цифр числа $A2.$ Найдите все такие двузначные числа $A.$

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

Подсказка 1

Мы работаем с суммами цифр. Попробуйте определить их отношения для некоторых чисел.

Подсказка 2

Заметим, что если S(n) — сумма цифр числа n, то выполняется S(x + y) ≤ S(x) + S(y).

Подсказка 3

Пусть A = (ab) = 10a + b, оценим сумму цифр его квадрата.

Подсказка 4

Как можно оценить S(10ⁿa) и S(n)?

Подсказка 5

S(10ⁿa) = S(a), S(n) = S(1 + ... + 1) < n.

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

Несложно понять через сложение в столбик, что для суммы цифр $S(n)$ выполняется следующее неравенство $S(x+y)≤ S(x)+S(y).$ Пусть $-- A = ab,$ тогда

2 2 2 2 2 2 S(A )=S ((10a +b))= S(100a + 20ab+ b )≤S(100a )+ S(20ab)+S(b)

Нетрудно понять, что $S(10na)=S(a)$ и $S(n)= S(1+ 1+...+1)≤ n.$ Следовательно,

2 2 2 2 2 2 2 2 S (100a)+ S(20ab)+S(b) =S(a )+S(2ab)+ S(b)≤ a +2ab+ b =(a+ b)= S(A)

Значит, во всех выписанных неравенствах должно достигаться равенство. Заметим, что равенство $S (n)= n$ реализуется лишь при однозначном $n$ (в этом можно убедиться, если записать $n$ в развёрнутой форме и сравнить её с суммой цифр). Таким образом, числа $a2,2ab,b2$ должны быть однозначными. То есть $1≤a ≤3,0≤ b≤ 3,ab≤ 4.$ Отсюда получаем все перечисленные в ответе варианты.

Ответ:

$10,11,12,20,21,22,30,31$

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

Задача 15#76746

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

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

Подсказка 1

Докажем требуемое по индукции. Как сделать переход от n+1 карты к n? Какую карту можно гарантированно не трогать?

Подсказка 2

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

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

Индукция по толщине колоды. База (колода из одной карты) очевидна.

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

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

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

Задача 16#82695

Решите уравнение

63 62 61 2 63 (x +1) +(x+ 1) (x − 1)+ (x +1) (x− 1) + ...+ (x − 1) =0

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

Подсказка 1

Вспомните формулы сокращённого умножения.

Подсказка 2

Конкретно нам поможет формула для aⁿ - bⁿ. Попробуйте вместо a и b подставить (x + 1) и (x - 1).

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

Вспомним формулу сокращенного умножения:

n n n−1 n−2 n−2 n−1 a − b =(a− b)(a + a b+ ...+ ab + b )

Пусть $a= x+1,$ $b= x− 1$ и $n= 64.$ Тогда в разложении вторая скобка равна левой части в уравнении из условия задачи. Тогда умножим и разделим исходное уравнение на $a− b= (x +1)− (x − 1).$

--1- n−1 n−2 n−2 n−1 a − b ×(a− b)(a +a b+ ...+ab + b )= 0

Применим формулу, приведенную выше:

1 a−-b × (an− bn)= 0

Так как $a− b= (x +1)− (x − 1)= 2,$ то на $a− b$ можно сократить, и уравнение примет вид $an = bn.$

Так как $n =64,$ то получаем два случая:

$a =b,$ то есть $x+ 1= x− 1,$ что невозможно.
$a =− b,$ то есть $x+ 1= −x+ 1,$ откуда $x= 0.$

Ответ: 0

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

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

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

Задача 17#68247

Найдите какие-нибудь четыре попарно различных натуральных числа $a,b,c,d,$ для которых числа $a2+ 2cd +b2$ и $c2 +2ab+d2$ являются полными квадратами.

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

Подсказка 1

Мы видим, что оба наших выражения очень уж похожи на квадрат суммы. Вот только попарные произведения отличается. Вот если бы в первом выражении было не cd , а ab, то наше выражение свернулось бы в полный квадрат. И наоборот, если во втором выражении было бы не ab, а cd, то второе выражение свернулось бы в полный квадрат. Но, к сожалению, «реальность полна разочарований», вот только если не «мы сами определяем реальность». Нам же дали свободу выбора a,b,c,d. Может, можно исправить нашу проблему?

Подсказка 2

Да, действительно, если мы возьмем такие числа, что ab=cd, то оба выражения свернутся в полный квадрат, и это как раз то, что нам нужно. Значит, остаётся подобрать такие различные числа a,b,c,d, что ab=cd. Но это сделать совсем просто!

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

Достаточно найти такие $a,b,c$ и $d,$ что $cd =ab,$ тогда оба выражения свернутся в полный квадрат. Например, можно взять $a =1,b= 6,c= 2,d= 3.$

Ответ: (1, 6, 2, 3)

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

Задача 18#81751

Найдите все пары целых чисел $(x,y),$ для которых числа $x3 +y$ и $x+ y3$ делятся на $x2+ y2.$

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

Подсказка 1:

Попробуйте обозначить НОД x и y через d и что-то про него понять.

Подсказка 2:

Итак, у вас должно было получиться, что x и y взаимно просты. Теперь давайте осознаем, что любая линейная комбинация чисел x³ + y и x² + y² или x + y³ и x² + y² будет делиться на x² + y². Попробуйте взять какую-нибудь удобным комбинацию, которая даст интересную делимость.

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

Пусть $d =$ НОД $(x,y).$ Тогда $x= du, y = dv,$ где $u$ и $v$ взаимно просты. По условию $d3u3+ dv$ делится на $d2,$ поэтому $v$ делится на $d.$ Аналогично $u$ делится на $d.$ Значит, $d= 1,$ то есть $x$ и $y$ взаимно просты. Тогда и число $2 2 x + y$ взаимно просто с $y.$ Число $( 2 2) (3 ) x x +y − x +y = y(xy − 1)$ делится на $2 2 x + y.$ Поскольку $2 2 x + y$ и $y$ взаимно просты, то $xy− 1$ делится на $2 2 x + y .$ Но это возможно только при $|xy|≤ 1.$ Действительно, в противном случае $2 2 0 <|xy− 1|< 2|xy|≤x + y .$ Непосредственная проверка всех оставшихся вариантов $(x,y =0,±1)$ дает восемь решений $(±1,±1),(0,±1),(±1,0).$

Ответ:

$(1,1), (1,0), (1,−1), (0,1), (0,−1), (−1,1), (−1,0), (−1,−1)$

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

Задача 19#88474

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

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

Подсказка 1

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

Подсказка 2

Перекрашивать произвольные вершины в разные цвета немного странно. Хочется определенные вершины перекрашивать в определенный цвет. Попробуйте вершины цвета 2 перекрасить в цвет 1?

Подсказка 3

Нам не удастся перекрасить все вершины по условию. Что нам могло помешать? Только вершины цвета 2, соединенные соединенные с цветом 1. А что, если поочередно так сделать со всеми цветами?

Подсказка 4

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

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

Цвета, в которые покрашен граф, занумеруем от $1$ до $k.$ Те вершины цвета $2,$ которые не соседствуют ни с какими вершинами цвета $1,$ перекрасим в цвет $1.$ Новая раскраска будет правильной, поэтому в ней $k$ цветов. Значит, какие-то вершины цвета $2$ не перекрашены и потому соседствуют с вершинами цвета $1.$ Аналогично, вершины цвета $3,$ которые не соседствуют с вершинами цвета $2,$ перекрасим в цвет $2,$ и т. д. вплоть до последнего цвета.

После этого рассмотрим какую-либо вершину цвета $k.$ Она не перекрашена, и потому соседствует с вершиной цвета $k− 1.$ Эта вершина тоже не перекрашена, так как иначе её первоначальный цвет был бы $k,$ и она не могла бы соседствовать с вершиной того же цвета. Раз вершина не перекрашена, то она соседствует с вершиной цвета $k− 2,$ и т. д. Продолжая этот процесс, построим путь из вершин $k$ цветов, которые не были перекрашены.

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

Задача 20#91025

Вписанная окружность треугольника $ABC$ касается сторон $AB$ и $BC$ $(AB >BC )$ в точках $N$ и $M$ соответственно. $PQ$ – средняя линия треугольника $ABC,$ параллельная $AB, K$ – точка пересечения $MN$ и $PQ.$ Докажите, что $AK$ – биссектриса угла $BAC.$

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Каким является ∠AKC?

Подсказка 4

Он прямой! Тогда можно выделить некоторые полезные отрезки в прямоугольном треугольнике :)

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

$PIC$

Существует не более одной точки пересечения средней линии $PQ$ с прямой $NM,$ поэтому если мы покажем, что точка пересечения биссектрисы угла $BAC$ с $NM$ является таковой, задача будет решена.

Пусть $K$ — точка пересечения биссектрисы угла $BAC$ и прямой $NM.$ Докажем, что $KQ$ — средняя линия. По лемме $255$ угол $AKC$ прямой. Заметим, что $KQ$ — медиана в прямоугольном треугольнике, проведённая к гипотенузе, а значит треугольник $AKQ$ — равнобедренный. Следовательно, $∠KQC = ∠AKQ + ∠KAQ = 2∠KAQ = ∠BAC.$ Значит, $KQ ∥AB$ и $KQ$ проходит через середину $AC,$ то есть является средней линией. Получили требуемое.

Следующая подтема