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

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

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

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

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

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

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

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

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

Задача 1#67556

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

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

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

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

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

Предположим целое $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)

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

Докажем, что все $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?$

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

Нечётные $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.$

Ответ:

Бесконечно

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

Задача 6#104432

Найдите все такие пары натуральных чисел $a$ и $b,$ что $a1000 +1$ делится на $b619$ и $b1000+ 1$ делится на $a619.$

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

Если $a =1,$ то, очевидно, $b=1;$ при этом пара $(1,1)$ подходит. Осталось разобрать случай $a,b>1.$ Заметим сразу, что $a$ и $b$ взаимно просты; пусть $a> b.$

Число

1000 1000 1000 ( 1000 ) A =a + b + 1=a + b + 1

делится на $a619;$ аналогично, $A$ делится на $b619,$ а из взаимной простоты и на их произведение. Итак, $a1000+b1000+ 1≥ a619b619,$ а значит, $1001 1000 619619 a ≥ 2a ≥ a b ,$ или $382 619 a ≥ b .$ С другой стороны, $1001 1000 619 b > b + 1≥ a .$ Итак,

1001⋅382 619⋅382 619⋅619 b > a ≥ b

Но $1001⋅382< 6192$ — противоречие.

Ответ:

$(1,1)$