Тема ТурГор (Турнир Городов)

Теория чисел на устном туре Турнира Городов

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

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

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

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

Подтемы раздела тургор (турнир городов)

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

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

Задача 1#67556

Существует ли целое $n > 1$ , удовлетворяющее неравенству

[√---- √----] [√ ----] n − 2+ 2 n+ 2 < 9n+ 6?

(Здесь $[x]$ обозначает целую часть числа $x$ , то есть наибольшее целое число, не превосходящее $x$ .)

Источники: Тургор-2023, 11.2 (см. www.turgor.ru)

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

Подсказка 1

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

Подсказка 2

Для этого примените неравенства, возникающие из определения целой части числа. Что ж, дальше попробуем пользоваться возведением в квадрат. И... в итоге получается тривиальное неравенство, не содержащее n :( Что это может значить? Вероятно, надо как-то ещё преобразовать исходное неравенство, чтобы такой способ сработал. Если и пытаться это делать, то для правой части, она выглядит получше. Не поможет ли возведение её в квадрат?

Подсказка 3

Хм, можно оценить, что квадрат правой части (к слову, целой) не больше, чем 9n + 6. Подумаем, а когда в таком неравенстве достигается равенство?

Подсказка 4

Вообще, при равенстве получится, что квадрат целого числа даёт остаток 6 по модулю 9. Стоп, а такое вообще возможно?

Подсказка 5

Нет, квадраты чисел по модулю 9 не дают остаток 6! Более того, остаток 5 они тоже не дают, а вот остаток 4 уже может получиться. А тогда можно оценить правую часть более строго!

Подсказка 6

Действительно, получается, что квадрат правой части на самом деле не больше, чем 9n + 4, давайте преобразуем исходное неравенство, а дальше опять будем возводить в квадрат, остаётся надеяться, что в результате получится более содержательное неравенство

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

Предположим целое $n> 1$ удовлетворяет этому неравенству. Имеем

[√----]2 9n+ 6 ≤ 9n+ 6,

Но квадрат целого числа не может давать ни остаток 6, ни остаток 5 от деления на 9, значит,

[√-----]2 9n+ 6 ≤9n+ 4

[√-----] [√ ----] 9n+ 6 ≤ 9n +4

Тогда исходное неравенство влечёт неравенство

√n-− 2+ 2√n-+2< √9n-+4

Возводя в квадрат и приводя подобные слагаемые, получаем, что

∘ ----- 4 n2− 4< 4n− 2

1 n2− 4< n2− n+ 4

n <4,25

Однако, прямая проверка показывает, что при $n∈ {2,3,4}$ исходное неравенство не выполняется — противоречие.

Ответ: нет

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

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

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

Задача 2#92426

Возрастающая последовательность натуральных чисел $a < a <... 1 2$ такова, что при каждом целом $n> 100$ число $a n$ равно наименьшему натуральному числу, большему чем $an−1$ и не делящемуся ни на одно из чисел $a1,a2,...,an−1$ . Докажите, что в такой последовательности лишь конечное количество составных чисел.

Источники: Тургор - 2021, 11.4, устный тур (см. turgor.ru)

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

Подсказка 1

Нам нужно доказать, что начиная с какого-то m все числа нашей последовательности станут простыми. Допустим, что для какого-то n > m выполняется aₙ = d*t, где t ≤ d. Из условия мы понимаем, что d у нас не является числом вида aₖ, где k < m. Тогда как мы можем оценить d?

Подсказка 2

Точно! Мы можем тогда сказать, что aₖ < d < aₖ₊₁ для k < m. Тогда если мы возьмём достаточно большое m (например, 100), то мы также знаем, что d > a₁₀₀. Что теперь можно сказать про делители числа d, если мы знаем, что d не является членом нашей последовательности?

Подсказка 3

Верно! Мы получаем, что d делится на какое-то aₚ, где p ≤ k. Тогда какое противоречие мы получаем для aₙ?

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

Докажем, что все $a m$ , большие $(a )2 100$ , — простые числа. Предположим противное, тогда некоторое $a >(a )2 m 100$ раскладывается как $am = dt$ , где $1< t≤ d< am$ , и следовательно $a100 < d< am$ . Согласно определению $am,d$ не является ни одним из $a1,a2,...,am−1$ . Тогда $ak < d< ak+1$ для какого-то $k∈ {100,101,...,m− 1}$ . Раз $d$ не было выбрано в качестве $ak+1$ , оно делится на какое-то $ai,i∈ {1,2,...,k}$ . Но тогда и $am$ делится на $ai$ . Противоречие.

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

Задача 3#81384

Имеется натуральное $1001$ -значное число $A.$ $1001$ -значное число $Z$ — то же число $A,$ записанное от конца к началу (например, для четырёхзначных чисел это могли быть $7432$ и $2347$ ). Известно, что $A> Z.$ При каком $A$ частное $A∕Z$ будет наименьшим (но строго больше $1$ )?

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

Первое решение. Пусть $A = a--a---...a. 1000 999 0$ Поскольку $A >Z,$ среди цифр $a,a ,...,a 0 1 499$ есть хотя бы одна недевятка. Значит, $Z ≤ Z0 = 99◟. ◝4.◜99.9◞89◟95..◝◜0.19◞.$ Покажем, что $501 499 A − Z ≥10 − 10 .$ Отсюда будет следовать, что

A 10501− 10499 Z-− 1≥ ----Z0----

Эта оценка достигается при $Z =Z0,$ что и даёт ответ. Имеем

( ) ( ) ( ) A− Z =(a1000− a0) 101000− 1 + (a999− a1) 10999− 10 + ⋅⋅⋅+ (a501− a499)10501− 10499 =

= φ499Δ499+φ498Δ498 +⋅⋅⋅+ φ0Δ0

где $φi =a501+i− a499−i$ и $501+i 499−i Δi = 10 − 10$ при $i= 0,1,...,499.$ Заметим, что $Δi+1 > 10Δi.$ Пусть $j−$ наибольший индекс, при котором $φj ⁄= 0.$ Тогда

|φjΔj + φj−1Δj−1+ ⋅⋅⋅+ φ0Δ0|≥|φjΔ(j|− |φj−1Δj−1|− ⋅⋅⋅− |φ)0Δ0|≥ ≥Δj 1− 9-− -9-− ⋅⋅⋅− -9j- = Δjj ≥ Δ0 10 100 10 10

что и требовалось.

Второе решение. Ясно, что можно минимизировать (положительное) число $AZ-− 1= A−ZZ.$ Пронумеруем цифры в $A$ слева направо $a ,a,...,a . 1 2 1001$ Пусть $k$ — наименьший номер, для которого $a ⁄= a k 1002−k$ (тогда $k≤ 500$ и $a >a , k 1002−k$ ибо $A > Z$ ).

Рассмотрим произвольный оптимальный пример. Заменим первые и последние $k− 1$ цифр на девятки. $A− Z$ не изменится, $Z$ не уменьшится, то есть наша дробь не увеличится. По этой же причине $a501$ можно заменить на $9.$ Заменим $ak$ на $9,$ а $a1002−k$ на $8.$ При этом $A− Z$ не увеличится, а $Z$ не уменьшится. Заменим все цифры $ak+1,...,a500$ на нули, а $a502,...,a1001−k$ на девятки. Тогда $A − Z$ не увеличится, а $Z$ если и уменьшится, то на меньшую величину (это произойдёт только тогда, когда вторая половина и так была девятками!). Поскольку в оптимальном примере $A− Z <Z$ (в первом просто меньше цифр), то, ясно, $A−Z- Z$ не возрастёт. Итак, можно считать, что $A$ имеет вид

9◟9.◝.◜.9 ◞0◟0.◝.◜.0◞999◟ ◝..◜.9◞89◟9..◝◜.9◞ k 500−k 500−k k−1

В этом случае

501 500 k k−1 A − Z = 10 +10 − 10 − 10

Это выражение достигает минимума при $k= 500,$ и при этом же $k$ достигается максимум значения рассматриваемых $Z.$ Значит, это и есть ответ.

Ответ:

При $A,$ запись которого (слева направо) такая: $501$ девятка, восьмёрка, $499$ девяток

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

Задача 4#89082

Для каких натуральных $n$ верно следующее утверждение: для произвольного многочлена $P(x)$ степени $n$ с целыми коэффициентами найдутся такие различные натуральные $a$ и $b,$ для которых $P (a)+ P(b)$ делится на $a+ b?$

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

Подсказка 1

Условие задачи сильно напоминает формулировку теоремы Безу для многочленов: "Пусть P(x) является многочленом с целыми коэффициентами. Тогда для любых чисел целых чисел a, b число P(a)-P(b) делится на a-b." Доказательство данного утверждения опирается на тот факт, что для любых целых чисел a, b и натурального числа n a^n-b^b кратно a-b В данной задаче разность многочленов меняется на их сумму. К нашему счастью, для нечетных n и произвольных целых чисел a и b верно, что a^n+b^n кратно a+b. Что позволяет понять данное соображение в условиях нашей задачи?

Подсказка 2

Если представить произвольный многочлен P(x) в виде сумму многочленов P₀(x)+P₁(x), где в P₀(x) входят все мономы P(x) четной степени, а в P₁(x) - нечетной. Тогда, аналогично доказательству теоремы Безу, для любых натуральных чисел a, b верно, что P₁(a)+P₁(b) кратно a+b, тем самым мы показали, что число P(a)+P(b) сравнимо с P₀(a)+P₀(b) по модулю a+b. Что можно сказать о многочленах, для которых P₀(x) является константой?

Подсказка 3

Пусть P₀(x)=с для некоторого целого с. Тогда P(a)+P(b) сравнимо с 2c по модулю a+b, и по условию 2с кратно на a+b. Существует ли число c такое, что для любых различных чисел a и b число 2c не кратно a+b?

Подсказка 4

Существует! Например, число c=1. Таким образом, 2с=2<a+b, следовательно, 2с не кратно a+b. Таким образом, мы показали, существует многочлен P(x) = P₁(x)+1 произвольной нечетной степени, для которого искомые числа a, b не существуют. Осталось показать, что для любого многочлена четной степени утверждение задачи верно.

Подсказка 5

Покажем, что существуют такие числа натуральные числа a и b, что для многочлена P(x) верно, что P₀(a)+P₀(b) кратно a+b. Зафиксируем произвольное число a=m. Тогда P₀(m)+P₀(b) должно быть кратно m+b. Если b=P₀(m)-m, то m+b=P(m), то есть достаточно показать, что P₀(P₀(m)-m) кратно P₀(m). Это правда, поскольку P₀(P₀(m)-m) сравнимо c P₀(-m) по модулю P₀(m) и, в свою очередь, P₀(-m)=P₀(m), поскольку P₀(x) состоит из лишь мономов четной степени. В чем проблема данных рассуждений?

Подсказка 6

Число b=P₀(m)-m не обязательно является целым. Для решения задачи осталось показать, что существует для любого многочлена четное степени существует такое натуральное m, что число P₀(m)>m.

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

Нечётные $n$ не подходят. В самом деле, рассмотрим многочлен $P(x)=xn +1$ и различные натуральные $a,b.$ Так как $n$ нечётно, $n n a + b$ делится на $a+ b,$ а тогда $n n P (a)+ P(b)= (a + b)+ 2$ не делится, поскольку $a +b> 2.$

Осталось доказать, что все чётные $n$ подходят. Рассмотрим произвольный многочлен $P(x)$ степени $n.$ Представим его в виде суммы $P (x)= P0(x)+ P1(x),$ где в $P0(x)$ все мономы чётной степени, а в $P1(x)$ — нечётной. Заметим, что при всех натуральных $a,b$ сумма $P1(a)+P1(b)$ делится на $a+ b.$ Докажем, что найдутся такие $a,b,$ что и $P0(a)+P0(b)$ делится на $a+ b.$ Заметим, что степень $P0$ равна $n.$

Рассмотрим случай, когда старший коэффициент $P0(x)$ положителен (в случае отрицательного старшего коэффициента проведём дальнейшее доказательство для многочлена $−P0(x)).$ Так как $n> 1,$ то найдётся такое натуральное $m,$ что $P0(m )>2m.$ Докажем, что $a =m,b =P0(m)− m$ подходят. В силу выбора $m,$ они оба натуральные, причём $b> a.$ Далее, по модулю $a +b= P0(m)$ выполняются сравнения $P0(a)=P0(m)≡ 0$ (очевидно) и $P0(b)=$ $P0((b+a)− a)≡P0(−a)= P0(m )≡0$ (в силу чётности многочлена $P0)$ . Значит, $P0(a)+P0(b)≡ 0$ $(mod a+b),$ что и требовалось.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. В случае чётного $n$ можно проделать подобное рассуждение и без разбиения на чётную и нечётную компоненты. Поскольку степень многочлена $P(x)+P (−x)$ равна $n >1,$ существует такое натуральное $m$ , что $P(m)+ P(−m)> 2m$ . Тогда подойдут числа $a= m,b= P(m)+ P(−m )− m.$ Действительно, тогда $b> a> 0,$ и по модулю $a+ b= P(m)+ P(−m)$ верно сравнение $P (a)+ P(b)≡ P(a)+P (−a)= P(m)+ P(−m )≡0.$

Ответ:

При всех чётных $n$

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

Задача 5#79884

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

Источники: Тургор-2013, 11.4(см. www.turgor.ru)

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

При любом натуральном $n$ положим $a = 7n+ 7n−1+...+7+ 1. n$ Покажем, что к $a n$ можно прибавить несколько различных степеней семёрки, не превосходящих $n 7 ,$ чтобы получилось число $bn$ без нулей в десятичной записи. Тогда семеричная запись $bn$ будет состоять из единиц и двоек. Ясно, что таким образом мы построим бесконечно много различных чисел $bn,$ удовлетворяющих условию.

Итак, рассмотрим десятичную запись числа $an;$ рассмотрим первый слева ноль в ней (если он есть). Пусть он стоит в $i$ -м разряде справа (разряд единиц считаем нулевым). Найдётся степень семёрки $k 7,$ лежащая между $i 10$ и $i 7 ⋅10 ;$ заметим, что она меньше $an,$ и поэтому меньше $n+1 7 .$ После прибавления её к $an$ перехода из $i$ -го разряда не произойдёт (так как первая цифра $k 7$ меньше $9$ ), при этом в $i$ -м разряде окажется не ноль. Значит, в полученном числе первый слева ноль в десятичной записи (если он есть) расположен правее, чем в $an;$ применим к этому нулю то же действие (при этом мы прибавим меньшую степень семёрки, чем в предыдущий раз). Продолжая так дальше, в результате мы построим требуемое число $bn.$