Тема ПитерГор (Санкт-Петербургская олимпиада)

ПитерГор - задачи по годам → .05 ПитерГор 2018

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

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

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

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

Подтемы раздела питергор (санкт-петербургская олимпиада)

Разделы подтемы ПитерГор - задачи по годам

ПитерГор 2014 и ранее

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

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

Задача 1#71900Максимум баллов за задание: 7

У Васи есть $100$ карточек трёх цветов, карточек каждого цвета не больше $50.$ Докажите, что он может выложить из них квадрат $10 ×10$ так, чтобы любые две соседние (по стороне) карточки оказались разного цвета.

Источники: СпбОШ - 2018, задача 11.2(см. www.pdmi.ras.ru)

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

Подсказка 1

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

Подсказка 2

Пусть наши цвета: красный, синий, зелёный — а их количества К, С, З соответственно. Не умоляя общности будем считать, что K ≥ С ≥ З. Разберёмся сначала с красными. В какой одной из самых известных раскрасок одноцветные точно не соседние?

Подсказка 3

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

Подсказка 4

Да! Не умоляя общности, в чёрные клетки шахматной раскраски. Только делать нужно это упорядоченно, а не случайным образом. Как же это сделать?

Подсказка 5

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

Подсказка 6

Ну, можно например делать также, как с чёрными, только начать с самой левой нижней белой клетки. Только вот что там будет наверху квадрата? Может быть там потом зелёные станут соседними. Не годится. Как бы нам сделать так, чтобы после расставления синих, соседних клеток не осталось вообще? Напомним, что C = min(К, С, З) и К + С + З = 100.

Подсказка 7

Будем раскладывать синие, симметрично красным! То есть начнём с правого верхнего угла и пойдём по белым. Знаем, что K + C ≥ 67. Что теперь происходит с квадратом?

Подсказка 8

Синяя и красная змейка не оставляют за собой соседних незанятых клеток. Докажите, что в итоге эти змейки "схлопнуться" и не оставят таких клеток вообще. А дальше останется сказать пару слов про зелёные. У вас всё получится! Успехов!

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

Пусть для определённости карточки были красного, синего и зеленого цветов и меньше всего было карточек зелёного цвета. Тогда зелёных карточек не более $33.$ Покрасим клетки квадрата $10× 10$ в шахматном порядке так, что левый нижний угол квадрата чёрный. Начнём раскладывать красные карточки на черные клетки, начиная с левого нижнего угла квадрата. Сначала будем заполнять слева направо чёрные клетки из нижней строки, затем также слева направо чёрные клетки из второй снизу строки и т.д. до тех пор, пока не разложим все красные карточки. Далее разложим синие карточки на белые клетки, начиная с левого верхнего угла доски. Сначала будем заполнять слева направо белые клетки из верхней строки и т.д. до тех пор, пока не разложим все синие карточки. На оставшиеся клетки разложим зелёные карточки. Покажем, что никакие зелёные карточки не могут оказаться рядом (для красных и синих карточек это очевидно). Поскольку красных и синих карточек вместе не менее $67$ штук, а в строке лежит не более пяти карточек каждого из этих цветов, количество строк, занимаемых красными карточками, и количество строк, занимаемых красными карточками, вместе не меньше $12.$ Поэтому есть строка, которая целиком заполнена красными и синими карточками. Но тогда зелёные карточки над этой строкой лежат на белых клетках (и значит, не рядом), а зелёные карточки под этой строкой лежат на чёрных клетках(и значит, тоже не рядом).

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

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

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

Задача 2#71901Максимум баллов за задание: 7

Известно, что квадратный трёхчлен

2 (b+c)x +(a+ c)x+ (a+ b)

не имеет корней. Докажите, что $4ac− b2 ≤ 3a(a +b+ c).$

Источники: СпбОШ - 2018, задача 11.4(см. www.pdmi.ras.ru)

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

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

Обозначим через $P (x)$ квадратный трёхчлен из условия задачи:

2 P(x)= (b+ c)x + (a+c)x+ (a+ b).

Если одновременно поменять знаки у всех коэффициентов трёхчлена $P(x),$ то у него по-прежнему не будет корней, а требуемое неравенство не изменится. Поэтому можно считать, что $b+c> 0$ и $P(x)> 0$ при всех $x.$

Решение 1.

Поскольку $P(x)$ не имеет корней, его дискриминант отрицателен:

2 (a +c) − 4(a+ b)(b+c)< 0.

После деления на $4$ и приведения подобных получим неравенство

2 a2 c2 ac b + ab> 4 + 4 − 2 − bc. (∗)

Нам требуется доказать, что $2 4ac− b ≥3a(a+ b+c),$ или, что то же самое, $2 2 6a + 6ab+ 2b ≤2ac.$ Заменим в этом неравенстве $2 b + ab$ на правую часть неравенства (*), тем самым уменьшив левую часть. Останется доказать неравенство

2 2 a2 c2 ac 6a + 5ab+ b + 4-+ 4-− 2-− bc≥ 2ac.

После приведения подобных оно примет вид

( )2 ( )2 ( ) 5a + 5ab+b2+ c2= 5a+ b + c2≥ 5a+ b c, 2 4 2 4 2

и теперь оно очевидно в силу неравенства о средних.

Решение 2.

Положим

u= b+c,v = c+a,w =a +b.

Тогда $1(v+ w − u),b= 1(u− v+ w),c = 1(u+ v− w). 2 2 2$ По условию квадратный трёхчлен $ux2+vx+ w$ не имеет корней. Тогда его дискриминант $v2− 4uw$ отрицателен, значит, $4uw> v2.$ Перепишем в новых обозначениях неравенство, которое нужно доказать:

2 0≤ 3a(a+ b+c)− 4ac+ b =

v-+w-− u u+-v+-w v+-w-− u u+-v−-w (u-− v+-w )2 =3 2 ⋅ 2 − 4 2 ⋅ 2 + 2 =

2 2 = u-+-2vw+-4w-−-3uw-−-uv 2

Это равносильно неравенству $(u− 2w)2+ uw ≥v(u− 2w),$ и в таком виде оно очевидно, поскольку

(u− 2w)2 +uw > (u− 2w)2+ v2≥ 2(u− 2w)v= v(u− 2w ). 4 2

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

Задача 3#71902Максимум баллов за задание: 7

Положительные иррациональные числа $α$ и $β$ таковы, что при всех $x >0$ выполнено равенство $[α[βx]]= [β[αx]].$ Докажите, что $α =β.$

Источники: СпбОШ - 2018, задача 11.6(см. www.pdmi.ras.ru)

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

Подсказка 1

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

Подсказка 2

С одной стороны x ≥ |n/a|/b, а с другой? ( обозначение: |m| — наименьшее целое число, которое больше либо равно x)

Подсказка 3

Для любого x выполняется условие x ≥ |n/a|/b и x ≥ |n/b|/a, но эти неравенства следуют из одного и того же равенства. Что это значит?

Подсказка 4

|n/a|/b = |n/b|/a. Докажите, что так бывает лишь при a = b.

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

Введём обозначение: будем считать, что нам даны два таких иррациональных параметра $α$ и $β,$ что при всех $x >0$ выполнено равенство $1 1 -11 [α[βx]]= [β [αx]].$ По-прежнему требуется доказать, что $α =β.$
Обозначим через $⌈x⌉$ верхнюю целую часть числа $x,$ т.е. наименьшее целое число, которое больше либо равно $x.$ Положим $1 1 fα,β(x)= [α[βx]]$ и найдём, при каких натуральных $n$ выполняется неравенство $fα,β(x) ≥n.$ Имеем

[1[ 1 ]] 1 [1 ] fα,β(x)≥n ⇔ α- βx ≥n ⇔ α- βx ≥ n⇔

[ ] [ ] ⇔ 1x ≥ αn ⇔ 1x ≥ ⌈αn⌉⇔ 1x ≥⌈αn⌉⇔ x ≥β⌈αn⌉. β β β

Аналогично неравенство $fβ,α(x)≥ n$ равносильно неравенству $x ≥α ⌈βn⌉.$ Поскольку $fβ,α(x)= fα,β(x),$ мы приходим к выводу, что при всех натуральных $n$ выполняется равенство $β⌈αn⌉=α⌈βn⌉,$ или

α-= ⌈αn⌉- β ⌈βn⌉

Теперь понятно, что это равенство верно только при $α= β.$

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

Задача 4#71903Максимум баллов за задание: 7

Прямая $l$ на координатной плоскости не параллельна осям координат. При каком наименьшем $d$ можно утверждать, что расстояние от некоторой точки с целыми координатами до прямой $l$ не превосходит $d?$

Источники: СпбОШ - 2018, задача 11.1(см. www.pdmi.ras.ru)

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

Подсказка 1

У нас есть прямая и координатные оси. На какой объект можно посмотреть, чтобы начать двигаться к оценке?)

Подсказка 2

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

Подсказка 3

Верно! Он не превосходит 45°! (пусть этот угол α прямая составляет с осью абсцисс) Давайте теперь проведём прямые x=n и y=n для всех n∈ℤ. Мы хотим прийти к расстоянию от целой координаты.... Что будем делать?)

Подсказка 4

Да! Давайте посмотрим на один из единичных квадратов, на которые мы разбили плоскость. Как его пересекает прямая? Какой хороший объект появляется?

Подсказка 5:

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

Подсказка 6

Конечно! Катет не превосходит половины стороны квадрата, т.е. 1/2, а угол не больше 45°. Осталось выразить высоту через синус угла и катет и завершить оценку!

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

Прямая $l$ образует с одной из осей координат угол, не превосходящий $45∘,$ поскольку сумма углов между прямой $l$ и осями координат равна $∘ 90.$ Пусть для определённости угол с осью абцисс не превосходит $∘ 45 ,$ обозначим его через $α.$ Нарисуем сетку, образованную прямыми $x= n$ и $y = n$ при всех целых $n.$ Она разбивает плоскость на единичные квадратики. Рассмотрим квадратик, который пересекает прямая $l.$ Тогда она пересекает одну из горизонтальных сторон. Их точка пересечения $A$ делит сторону на две части. Рассмотрим меньшую из них, соответствующую ей вершину квадратика обозначим через $C.$

$PIC$

Тогда $AC ≤ 12.$ Расстояние от точки $C$ до прямой $l$ равно длине перпендикуляра, опущенного из точки $C$ на $l,$ значит, оно равно $AC sinα ≤ 12sin45∘ =-1√-. 2 2$

Легко видеть, что расстояние от любой точки с целыми координатами до прямой $y = x+ 12$ не меньше $-1√-. 2 2$ Этот пример подтверждает точность полученной оценки.

Ответ:

при $d = √1- 2 2$

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

Задача 5#71904Максимум баллов за задание: 7

На биссектрисе угла $B$ остроугольного треугольника $ABC$ выбрана точка $T.$ Окружность $S,$ построенная на $BT$ как на диаметре, пересекает стороны $AB$ и $BC$ в точках $P$ и $Q$ соответственно. Окружность, проходящая через вершину $A$ и касающаяся $S$ в точке $P,$ вторично пересекает прямую $AC$ в точке $X.$ Окружность, проходящая через вершину $C$ и касающаяся $S$ в точке $Q,$ вторично пересекает прямую $AC$ в точке $Y.$ Докажите, что $TX = TY.$

Источники: СпбОШ - 2018, задача 11.3(см. www.pdmi.ras.ru)

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

Подсказка 1

Благодаря теореме об угле между касательной и хордой, касание двух окружностей можно переформулировать в условие равенства двух вписанных углов. Что можно сказать об углах PXC и QYA?

Подсказка 2

Несложно показать, что они равны соответственно углам PTB и QTB. Что это говорит об окружностях (TPX) и (TQY)?

Подсказка 3

Каждая из них проходит через основания L биссектрисы BT. Какое условие на окружности (TPX) и (TQY) является достаточным для равенства TX и TY, учитывая, что прямая XY проходит через вторую точку пересечения данных окружностей

Подсказка 4

Достаточно показать, что они равны. Почему это так?

Подсказка 5

Они описаны около равных треугольников TPL и TQL.

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

Решение 1.

Отметим сначала полезное свойство касающихся окружностей, а потом перейдём к решению задачи. Если секущая $UW$ проходит через точку $V$ касания двух окружностей, то вписанные углы, опирающиеся на высекаемые ей дуги, равны. Действительно, поскольку вписанный угол равен углу между касательной и секущей, имеем равенство $∠UU1V = ∠UVY = ∠XV W =∠W W1V.$

$PIC$

Теперь перейдем к решению задачи. Пусть $L$ — основание биссектрисы угла $B.$ Точки $P$ и $Q$ симметричны относительно прямой $BT,$ поэтому $∠BT P =∠BT Q$ и треугольники $LPT$ и $LQT$ равны. Из касания окружностей в точке $P$ имеем равенство $∠BT P =∠P XA,$ поэтому четырёхугольник $LTP X$ вписанный. Из касания окружностей в точке $Q$ имеем равенство $∠BT Q =∠QY L,$ значит, четырёхугольник $LTQY$ также вписанный. Отметим, что описанные окружности четырёхугольников $LTPX$ и $LTQY$ равны, поскольку они являются описанными окружностями равных треугольников $LP T$ и $LQT.$ Хорды $TX$ и $TY$ этих окружностей лежат напротив углов $∠TLX$ и $∠T QY =180∘− ∠TLY = ∠TLX.$ Поскольку равны углы, эти хорды также равны.

$PIC$

_________________________________________________________________________________________________________________________________________________________________________________

Решение 2.

Рассмотрим гомотетию с центром $P,$ переводящую окружность, проходящую через вершину $A$ и касающуюся $S$ в точке $P,$ в окружность $S.$ Эта гомотетия переводит точку $A$ в точку $B,$ а точка $X$ — в точку $K$ вторичного пересечения прямой, параллельной $AC$ и проходящей через $B,$ с окружностью $S.$ Тогда точки $X,P,K$ лежат на одной прямой. Аналогично точки $Y,Q,K$ тоже лежат на одной прямой. Рассмотрим прямую $KT.$ С одной стороны, она является биссектрисой угла $P KQ,$ поскольку $T$ — середина дуги $P Q.$ С другой стороны, угол $BKT$ опирается на диаметр, значит, он прямой и $KT$ не только биссектриса, но и высота треугольника $XKY.$ Тогда $KT$ — серединный перпендикуляр к $XY,$ поэтому $TX = TY.$

$PIC$

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

Задача 6#71905Максимум баллов за задание: 7

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

Источники: СпбОШ - 2018, задача 11.5(см. www.pdmi.ras.ru)

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

Подсказка 1

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

Подсказка 2

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

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

Пусть в графе нашёлся цикл, и пусть он проходит по горизонтальному отрезку $a 0$ слева направо. Возьмём ромб, примыкающий к стороне $a0,$ и отметим в нём параллельную сторону $a1.$ Возьмём ромб, примыкающий к стороне $a1,$ и отметим в нём параллельную сторону $a2$ и т.д.

Такую же конструкцию провернём в другую сторону: возьмём ромб, примыкающий к отрезку $a0$ с другой стороны, и отметим в нём параллельную сторону $a−1,$ и т.д.

$PIC$

Мы получили “полосу ширины $a$ ”, которая рассекает наш шестиугольник. При этом цикл заведомо пересекает эту полосу, но всё время в направлении слева направо. Это невозможно.

Курсы

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

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

Задача 7#71906Максимум баллов за задание: 7

На окружности $S$ отмечены точки $A$ и $B.$ Касательные к окружности $S,$ проведённые в точках $A$ и $B,$ пересекаются в точке $C.$ Пусть $M$ — середина отрезка $AB.$ Окружность $S1,$ проходящая через точки $M$ и $C,$ вторично пересекает отрезок $AB$ в точке $D$ и окружность $S$ — в точках $K$ и $L.$ Докажите, что касательные, проведенные к окружности $S$ в точках $K$ и $L,$ пересекаются на отрезке $CD.$

Источники: СпбОШ - 2018, задача 11.7(см. www.pdmi.ras.ru)

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

Подсказка 1

Часто, в задачах с окружностями на доказательство о том, что что-то где-то пересекается, полезно воспользоваться теоремой о степени точки! Заметим, что M — середина хорды AB. Что из этого следует?

Подсказка 2

Выяснили, что AM — высота в прямоугольном трегольнике! Какое тождество будет следовать из подобия? Хотим получить что-то похожее на теорему о степени точки. А что тогда можно сказать про CD?

Подсказка 3

OK — касательная к S1! А значит касательные к S пройдут через центр S1 — мы уже знаем, что он лежит на CD!

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

Обозначим через $O$ центр окружности $S.$ Поскольку $AM$ — высота прямоугольного треугольника $OAC,$ то

2 2 OK = OA = OM ⋅OC,

поэтому $OK$ (и аналогично $OL$ ) — касательные к окружности $S1.$ Но тогда касательные к окружности $S$ в этих точках перпендикулярны касательным к $S1$ из точки $O,$ и значит, они проходят через центр $S1,$ лежащий на диаметре $CD.$

$PIC$

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

Задача 8#72171Максимум баллов за задание: 7

На круглом ожерелье висят $2n > 3$ бусинок, каждая покрашена в красный или синий цвет. Если у какой-то бусинки соседние с ней бусинки покрашены одинаково, ее можно перекрасить (из красного в синий или из синего в красный). Можно ли из любой исходной раскраски бусинок сделать ожерелье, в котором все бусинки покрашены одинаково?

Источники: СпбОШ - 2018, задача 9.4(см. www.pdmi.ras.ru)

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

Подсказка 1

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

Подсказка 2

Какой самый простой инвариант мы знаем? Инвариант по четности какой-то величины. Посмотрите на количество пар соседних красных бусинок...

Подсказка 3

Это действительно инвариант, ведь если мы имели участок ожерелья (к)(c)(к) и мы перекрасили центральный, количество увеличилось на 2, а если (к)(к)(к), уменьшилось на 2 (если мы меняли участок вида (с)(?)(c) эта величина не изменилась). В любом случае четность не поменялась. Не трудно увидеть, что тоже самое можно сказать про четность количества пар соседних синих бусинок. Как тогда построить контрпример?

Подсказка 4

Давайте посмотрим на значение инвариантов при одноцветной раскраске: в любом случае бусинок какого-то цвета не будет, а это значит, что количество таких пар будет просто 0, т.е. четное число. Тогда нам нужно придумать такой пример, что изначально количество пар соседних красных и количество пар соседних синих бусинок были нечетными числами. Я в вас верю!

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

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

Варианты правильных ответов:

нет
Нет
нельзя
Нельзя

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

Задача 9#73376Максимум баллов за задание: 7

Коэффициенты многочлена $f(x)$ — целые числа, по модулю не превосходящие 5000000. При этом каждое из уравнений $f(x)= x,f(x)=2x,...,f(x)= 20x$ имеет целый корень. Докажите, что $f(0)= 0.$

Источники: СпбОШ - 2018, задача 10.4(см. www.pdmi.ras.ru)

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

Подсказка 1

Попробуйте обратить внимание на простые числа. Понятно, что если f(0) делится на большое количество простых чисел, то оно либо равно 0, либо больше 5000000. Как мы знаем, второе невозможно.

Подсказка 2

Причём логично рассматривать простые числа, меньшие 20, потому что, используя уравнения из условия, можно манипулировать остатками.

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

Докажем, что $f(0)$ делится на все простые числа, меньшие $20,$ из этого будет следовать, что либо $f(0)= 0,$ либо оно по модулю больше $2⋅3⋅5⋅7⋅11⋅13⋅17⋅19 >5000000.$

Действительно, пусть $f(0)$ не кратно какому-то $p,$ меньшему $20.$ Тогда $x≡ 0 (mod p)$ не может являться решением ни одного из уравнений из условия (левая часть не делится на $p,$ а правая часть делится).

Но очевидно, что решения уравнений $f(x)= x,f(x)= 2x,...,f(x)= px$ должны давать попарно различные остатки при делении на $p$ при условии, что эти остатки ненулевые(иначе вычтем из первого уравнения второе, левая часть сравнима с 0 по модулю $p,$ а правая нет). Однако уравнений у нас $p,$ а возможных остатков $p− 1$ — противоречие.

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

Задача 10#80968Максимум баллов за задание: 7

Даны два нечетных натуральных числа $a$ и $b.$ Докажите, что существует такое натуральное $k,$ что хотя бы одно из чисел $bk− a2$ и $k 2 a − b$ делится на $2018 2 .$

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

Подсказка 1

Попробуйте рассмотреть обобщенную задачу. "Дано натурально число n и два нечетных натуральных числа a и b. Докажите, что существует такое натуральное k, что хотя бы одно из чисел b²ᵏ - a² и a²ᵏ - b² делится на 2ⁿ".

Подсказка 2

Припомните известное утверждение об остатке от деления c²-1 на 2ᵏ⁺², если остаток от деления c-1 на 2ᵏ⁺¹ равен 2ᵏ, где с — некоторое число.

Подсказка 3

Рассмотрим числа a² - 1, которое делится на 2ᵅ и не делится на 2ᵅ⁺¹, и b² - 1, которое делится на 2ᵝ и не делится на 2ᵝ⁺¹. Подумайте, какие ограничения на α и β накладывают приведенные нами условия. Воспользовавшись вышеприведенной леммой, подумайте, какой остаток при делении на 2ᵝ⁺¹ дает число a²ᵐ - 1 (где m = β-α при условии β>α).

Подсказка 4

Примените индукцию по n. Чтобы доказать базу индукции, подумайте, какое число нам подойдет при n ≤ β+1 и почему.

Подсказка 5

Для доказательства шага индукции рассмотрите два случая: когда a²ᵏ - b² делится на 2ⁿ⁺¹ и, соответственно, когда не делится.

Подсказка 6

Если всё ещё испытываете затруднения, положите r = 2ⁿ⁻ᵝ + 1. В очередной раз воспользуйтесь леммой и ответьте на вопрос, какой остаток дает b²ʳ при делении на 2ⁿ⁺¹.

Подсказка 7

Воспользуйтесь формулой разности степеней. Разложив a²ᵏʳ - b²ʳ, Вы получите произведение двух скобок. Оцените делимость какой-либо из них на 2ⁿ⁺¹.

Подсказка 8

a²ᵏʳ - b² = (a²ᵏʳ - b²ʳ) - (b²ʳ - b²). С остатком от деления левой скобки на 2ⁿ⁺¹ разобрались, а что насчёт правой?

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

Будем решать обобщенную задачу. Дано натуральное число $n$ и два нечетных натуральных числа $a$ и $b.$ Докажите, что существует такое натуральное $k,$ что хотя бы одно из чисел $2k 2 b − a$ и $2k 2 a − b$ делится на $n 2 .$

Воспользуемся следующим известным утверждением: пусть число $c− 1$ дает остаток $k 2$ при делении на $k+1 2 ,$ где $k ≥2.$ Тогда $2 c − 1$ дает остаток $k+1 2$ при делении на $k+2 2 .$

Пусть $2 a − 1$ делится на $α 2$ и не делится на $α+1 2 ,$ а $2 b − 1$ делится на $β 2$ и не делится на $β+1 2 .$ Очевидно, что при этом $α,β ≥ 2.$ Тогда $2 a − 1$ дает остаток $α 2$ при делении на $α+1 2 ,$ а $2 b− 1$ дает остаток $β 2$ при делении на $β+1 2 .$ Пусть $α ≤β,$ положим для краткости $β−α 2 = m.$ По лемме число $2m 22 2 a − 1= (((a) )...)− 1$ даёт остаток $β 2$ при делении на $β+1 2 .$

Будем решать задачу индукцией по $n.$ Если $n≤ β+ 1,$ то нам подойдет $k= m,$ поскольку $2m a$ и $2 b$ дают равные остатки при делении на $2β.$ Сделаем переход от $n$ к $n+ 1.$ По индукционному предположению при некотором $k$ число $a2k− b2$ делится на $2n.$ Если оно делится и на $2n+1,$ то переход сделан. Иначе оно дает остаток $2n$ при делении на $2n+1.$ Пусть $r= 2n−β + 1.$ Тогда по лемме $b2(r−1)− 1$ дает остаток $2n$ при делении на $2n+1.$ Следовательно, $b2r− b2$ дает остаток $2n$ при делении на $2n+1.$ Воспользуемся формулой разности степеней:

a2kr− b2r = (a2k− b2)(a2k(r−1)+ a2k(r−2)b2+ ...+ b2(r−1))

Первая скобка дает остаток $2n$ при делении на $2n+1,$ вторая состоит из $r$ нечетных слагаемых и, значит, нечётна. Стало быть, разность $a2kr− b2r$ дает остаток $2n$ при делении на $2n+1.$ Но тогда $a2kr − b2 = (a2kr− b2r)− (b2r − b2)$ делится на $2n+1,$ поскольку выражения в скобках дают одинаковые остатки при делении на $2n+1.$

Предыдущая подтема

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