Тема ФЕТТ (Формула Единства / Третье Тысячелетие)

Теория чисел на ФЕ

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

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

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

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

Подтемы раздела фетт (формула единства / третье тысячелетие)

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

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

Задача 1#120576

Существует ли $2025$ -значное натуральное число без нулей в десятичной записи, которое увеличивается в $4$ раза, если записать его задом наперёд?

Источники: ФЕ - 2025, 11.2(см. www.formulo.org)

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

Подсказка 1

Запишем наше число в виде abc...xyz. Теперь попробуем что-нибудь сказать про цифры на концах (a, b, c, x, y, z), используя условие о том, что abc...xyz * 4 = zyx...cba. Какие ограничения можно наложить на эти цифры?

Подсказка 2

Во-первых, подумаем о том, что a не может быть слишком большим, иначе при увеличении в 4 раза у нас увеличится количество разрядов. Ещё можно воспользоваться тем, что zyx...cba делится на 4 – это дает условия на ba и a. Что можно ещё сказать о других цифрах?

Подсказка 3

Из ограничений выше однозначно получается найти a и z, также выразить несколько вариантов для xy, bc. При продолжении рассуждений получается однозначно выразить всё число.

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

Легко проверить, что число

2023 219◟9.◝..◜99◞78= 22⋅10 − 22 2021девятка

подходит. Действительно, при записи задом наперед оно равно

8799...9912= 88⋅102023− 88 ◟202◝1◜дев◞ятка

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Покажем, как можно было бы придумать такое число на олимпиаде. Обозначим это число $-------- abc...xyz,$ где $a,b,c,x,y,z$ — первые три и последние три числа в его записи. На месте многоточие стоят какие-то цифры.

Тогда $abc...xyz⋅4= zyx...cba.$ Значит, $z ≥4,$ так как $zyx...cba$ — результат умножения натурального числа с первой цифрой, не меньшей $1,$ на $4;$ $abc< 250,$ так как иначе при умножении на $4$ в числе $abc...xyz-$ увеличится количество знаков. Тогда $a∈ {1,2}.$ Помимо того, $ba$ делится на $4,$ значит, $a$ четно, поэтому $a =2.$ Также $yz⋅4$ кончается на $2$ при $z ∈ {3;8}.$ Так как $z ≥4,$ то $z =8.$

Далее из равенства $...y8 ⋅4 =...b2$ по цифре $y$ можно однозначно определить цифру $b,$ которая к тому же должна быть нечетная и меньше $5.$ Получаются варианты $23...08⋅4= 80...32$ и $21...78⋅4= 87 ...12,$ из которых подходит только второй.

Аналогичным образом пытаясь найти $c$ и $x,$ получаем два возможных варианта: $217...178$ и $219...978.$ Развивая второй вариант, можно понять, что все числа вида $2199...9978$ подходят.

Ответ:

Да, существует — например, $21 99...99 78 202◟1д◝◜евят◞ка$

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

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

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

Задача 2#120577

Решите уравнение в целых числах: $x= x2+ xy+y2+ 2y+ 2.$

Источники: ФЕ - 2025, 11.3(см. www.formulo.org)

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Вообще, уже получили достаточно хороший вид, однако остаётся x² - 2x. Добавим 1 к обоим частям уравнения, чтобы получить полный квадрат. Теперь все слагаемые — полные квадраты, а справа — 1. Что нам это дает?

Подсказка 4

У нас остается не так много случаев из-за того, что эти квадраты — целые и неотрицательные. В частности, тогда одно из них равно 1, а другие два равны 0. Достаточно разобрать эти случаи, чтобы получить ответ!

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

Перенесем $x$ вправо и получим

2 2 x +xy +y + 2y+2 − x =0

Домножим на два и переставим слагаемые

2 2 −2x+ 2x + 2xy+ 2y + 4y+ 4= 0

Добавим к обеим частям $1$ и разделим оба квадрата на два слагаемых:

1− 2x+x2+ x2+ 2xy+y2+ y2+ 4y +4 =1

Выделим полные квадраты!

(1− x)2 +(x+ y)2+ (y+2)2 = 1

Так как $x$ и $y$ — целые, каждое из слагамых в левой части является целым неотрицательным числом. Тогда их сумма может быть равна $1$ только если одно из слагамых равно $1,$ а два других равны $0.$

Разберем случаи, когда два слагаемых равны $0.$ В случае $x= 1,x= −y$ получаем $y+ 2= 1$ — подходит. Если $x= 1,y =− 2,$ то $x +y = −1$ — тоже подходит. Наконец, при $y = −2,x= −y$ получаем $x − 1= 1,$ оно тоже подходит.

Ответ:

$(1,− 1),(1,−2),(2,−2)$

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

Задача 3#126640

У $n$ -значного числа первые две его цифры различаются на 1, вторая и третья — на $2,$ $...,$ предпоследняя и последняя — на $n− 1$ , последняя и первая — на $n.$ При каком наибольшем $n$ такое возможно?

Источники: ФЕ - 2025, 10.1 ( см. www.formulo.org)

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

Подсказка 1

Сколько всего у нас цифр? С учётом этого мы можем получить самую первую оценку на n.

Подсказка 2

Попробуем подобрать пример! Что можно сразу сказать про первую и последнюю цифры числа при таком n? А получится ли дальше заполнить число?

Подсказка 3

Как будто бы составить пример простым подбором не выходит. Значит надо искать противоречия или как-то ограничивать перебор! Попробуйте поработать с чётностью ;)

Подсказка 4

Ну что же, мы пришли к противоречию! Значит надо рассмотреть следующее подходящее n. Зафиксируйте начало и конец числа, а потом попробуйте также поработать с чётностью!

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

Так как разница между десятичными цифрами не превосходит 9, то $n≤ 9.$ Если бы такое девятизначное число существовало, то оно бы начиналось на 9 и заканчивалось на 0 (так как разность между первой и последней цифрой — $n).$ Из условия на разности соседних цифр, если выписать чётности, получится последовательность нччннччнн, но последнее число должно быть нулем — противоречие.

Пусть $n= 8,$ есть несколько примеров: 12473829, 87526170, 98637281.

Ответ:

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

Задача 4#126643

Коля выписал каждый натуральный делитель числа $2025n$ по одному разу, после чего покрасил некоторые из них в красный цвет, а остальные — в синий. При этом он действовал так, чтобы разность между суммой всех красных делителей и суммой всех синих делителей оказалась минимально возможным (при данном $n$ ) положительным числом. Какими могут оказаться две последние цифры этой разности? (Найдите все варианты и докажите, что других нет.)

Источники: ФЕ - 2025, 10.5 ( см. www.formulo.org)

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

Подсказка 1

Разложите 2025 на простые множители. Как выглядит сумма всех его делителей? Почему максимальный делитель 2025ⁿ больше суммы остальных? Сумма делителей растёт медленнее, чем само число, из-за степеней в разложении.

Подсказка 2

Чтобы разность сумм красных и синих делителей была минимальной положительной, как нужно раскрасить делители? Что произойдёт, если покрасить только 2025 в красный, а остальные — в синий? Разность будет 2 × 2025ⁿ.

Подсказка 3

Докажите, что искомая разность = 70n + 81 (mod 100). Какие остатки при делении на 100 могут быть у 70n + 81 при разных n? Переберите n от 1 до 20. Остатки будут циклически повторяться!

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

Если $n = 0,$ разность равна $1.$ Пусть $n >0.$ Сумма всех делителей числа 2025 равна

2 4n 2 2n (1 +3+ 3 + ...+ 3 )(1+ 5+ 5 +...+5 )=

n−1 n−1 =(1+ 120(1+ 81+...+81 ))(1 +30(1 +25+ 25 ))≡

≡ 1+ 120n+ 30(6+ 5n)≡ 81 +70n (mod 100)

По формуле суммы геометрической прогрессии, сумма делителей меньше, чем

( ) ( ) 34n⋅ 3 52n⋅ 5 =2025n⋅ 15 2 4 8

Значит, максимальный делитель (само число $2025n)$ превосходит сумму остальных, поэтому для получения минимального положительного результата перед ним должен стоять плюс, а перед остальными делителями — минус. Получается, что ответ имеет вид $50− 81− 70n (mod 100) ∈$ ${9;19;29;39;49;59;69;79;89;99}.$ Заметим, что разность больше $2025 8 > 9,$ то есть по крайней мере двузначная.

Ответ:

1, 09, 19, 29, 39, 49, 59, 69, 79, 89, 99

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

Задача 5#74784

Пусть $a + ...+ a = n 1 m$ , где $a ,...,a 1 m$ - натуральные числа. Докажите, что $n$ ! делится на произведение

a1!⋅a2!⋅...⋅am!

Источники: ФЕ-2022, 11.1 (см. www.formulo.org)

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

Подсказка 1

Мы знаем, как представить n в виде суммы. Попробуем представить n! в виде произведения, используя данные о сумме.

Подсказка 2

Заметим, что мы можем выразить n! как произведение a_1 подряд идущих чисел на a_2 подряд идущих чисел…и так далее…теперь нужно доказать делимость на произведение каждого из факториалов.

Подсказка 3

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

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

Давайте для начала докажем вспомогательную лемму: произведение $k$ подряд идущих чисел делится на $k!$

.. (n+ 1)(n+ 2)⋅...⋅(n +k).k!

Заметим, что количество способов выбрать $k$ человек из $k +n$ равно

(n+-k)(n+-k−-1)⋅...⋅(n-+1) k!

Но количество способов - целое число, поэтому числитель делится на знаменатель. Лемма доказана.

Так как $a1+ a2+...+am = n,$ то $n!$ можно представить в виде произведения $a1$ подряд идущих чисел на $a2$ следующих чисел $...$ на $am$ последних чисел:

n!= (1⋅2⋅...a1)⋅((a1+ 1)⋅(a1+ 2)⋅...⋅(a1+ a2))⋅...⋅((n − am +1)⋅...⋅n)

Произведение $ai$ подряд идущих чисел делится на $ai!,$ поэтому $n!$ делится на произведение факториалов $a1!⋅...⋅am!$

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

Задача 6#74789

Клетки кубической таблицы $7× 7× 7$ (то есть маленькие кубики) пронумеровали по порядку числами от 1 до 343. (Сначала нумеруются клетки верхнего слоя: в первой строке слева направо от 1 до 7, в следующей от 8 до 14, и так далее до 49. Далее в таком же порядке нумеруются Клетки второго слоя и т. А.) После этого из таблицы удалили несколько непересекающихся кубов $2× 2× 2$ , а все оставшиеся числа сложили. Чему может равняться остаток от деления полученной суммы на 8 ?

Источники: ФЕ-2022, 11.6 (см. www.formulo.org)

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

Подсказка 1

Попробуем выразить числа на удаленном кубе через переменную. Так мы сможем посчитать их сумму.

Подсказка 2

Заметим, что сумма всех числе равна 8a+4*57. Что тогда можем сказать об изменении остатка от деления на 8?

Подсказка 3

Он либо сохраняет, либо изменяет остаток на 4!

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

Рассмотрим произвольный вырезаемый куб $2×2 ×2$ . Если наименьшее число обозначить $a$ , то остальные числа будут $a+ 1,a+7,a+ 8,a +49,a+49+ 1,a +49+ 7$ , $a+ 49 +8$ . Значит, их сумма $− 8a +4× 1+ 4× 7+4 ×49= 8a+ 4×57$ , то есть имеет остаток 4 от деления на 8. Значит, вырезание кубиков либо сохраняет суммарный остаток от деления на 8, либо изменяет его на 4. Осталось узнать, чему этот остаток равнялся изначально. Сумма чисел от 1 до 343 равна их среднему арифметическому $(1+343 ) 2 = 172$ на их количество 343. 172 делится на 4 , но не на 8 , а 343 нечётно, поэтому исходный остаток равен 4.

Ответ:

0 или 4

Курсы

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

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

Задача 7#91340

Можно ли в выражении $A⋅5n+ B ⋅3n−1+ C$ подобрать натуральные коэффициенты $A,B$ и $C$ так, чтобы ни один из них не делился на 8, но результат при любом натуральном $n$ делился на $8?$

Источники: ФЕ - 2021, 10.1 (см. www.formulo.org)

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

Если $n ..2 .$ , то $A⋅5n+ B⋅3n−1+ C ≡A +3B + C (mod 8).$

Если $n$ не делится на 2, то $n n−1 A ⋅5 +B ⋅3 +C ≡ 5A + B+ C (mod 8).$

Тогда если $A = 2$ , $B = 4$ и $C =2$ , то оба выражения делятся на 8.

Ответ: да

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

Задача 8#94758

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

Источники: ФЕ - 2021, 11.1 (см. www.formulo.org)

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

Подсказка 1

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

Подсказка 2

Ага, 00000 мы не можем получить! А могла ли сумма цифр равняться 1? Можем ли получить какую-то из комбинаций такими операциями?

Подсказка 3

Ага, и тут не можем (обратите внимание на сумму цифр)! А можем ли получить сумму 2?

Подсказка 4

А вот тут уже можем! Попробуйте рассмотреть все комбинации с суммой цифр 2 и попробовать восстановить число Пети "обратным ходом".

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

Запись 00000 на экране появиться не может, поскольку она может получиться только из 00000 . Запись из четырёх нулей и единицы тоже не может, поскольку тогда последняя цифра не равна остатку от деления суммы четырёх первых на 10.

А вот сумма цифр 2 возможна. Например, “обратным ходом” можно найти пример получения записи 00011 (или 10001):

00011 ← 10001← 91000← 09100← 00910← 20091 ← 72009← 17200 ← 01720← ← 40172 ←24017 ← 52401← 95240← 89524.

Ответ: 2

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

Задача 9#94761

Территория Тридесятого царства состоит из всех целых чисел. Княжеством будем называть множество вида ${ak+ b|k∈ ℤ}$ , где $a ⁄=0$ и $b−$ некие целые числа (то есть бесконечную в обе стороны арифметическую прогрессию). Царь хочет разделить всю территорию царства, кроме чисел 3 и 10 , на бесконечное количество непересекающихся княжеств. Возможно ли это?

Источники: ФЕ - 2021, 10.4 (см. www.formulo.org)

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

Подсказка 1

Разбить все числа на княжества означает придумать правило, по которому мы их будем добавлять в княжества. Давайте для начала подумаем, чем схожи и чем отличаются числа 3 и 10.

Подсказка 2

Чётное и нечётное, делится на 3 и даёт остаток 1... Давайте попытаемся отдельно разбить чётные и нечётные числа. Одно из ключевых свойств — делимость. Попробуйте разбить все чётные числа кроме 0 (в том числе 10) на непересекающиеся княжества.

Подсказка 3

Для этого можно воспользоваться делимостью — брать число в княжество в том случае, если оно делится на какое-то число, а на другое не делится. Тогда 0 никуда не попадёт!

Подсказка 4

Тут можно поиграться со степенями двойки — брать число в княжество, если оно делится на 2ⁿ, но не делится на 2ⁿ⁺¹. Чему в таком случае будут равны a и b? И останется только придумать, как исключить 3 и 10 при помощи того, что 0 не в княжествах.

Подсказка 5

Выходит, что a = 2ⁿ⁺¹, b = 2ⁿ. А чтобы исключить 3 и 10, нужно сделать "сдвиг" княжеств. Брать число в них не в случае делимости, а в случае каких-то остатков от деления.

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

Будем отдельно разбивать чётные числа и нечётные, тогда надо дважды разбить прогрессию без одной точки. Покажем, как это сделать для нечётных: поместим нечётное число $x$ в княжество $s$ , если $x− 3$ кратно $s 2$ , но не кратно $s+1 2$ . Для чётных аналогично.

Ответ: да

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

Задача 10#73601

При каком наибольшем $n$ множество ${3,4,5,...n}$ можно так покрасить в синий и красный цвета, чтобы произведение двух любых (в том числе одинаковых) чисел одного цвета имело другой цвет?

Источники: ФЕ-2020, 11.5 (см. www.formulo.org)

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

Подсказка 1

Попробуйте придумать число, которое вот вообще не получится нормально покрасить ни в один из цветов) Тогда сразу ясно что n меньше этого числа.

Подсказка 2

Удобнее всего строить это число на основе лишь одного простого числа - почти все делители его будут известны из цвета этого простого числа)

Подсказка 3

Докажите, что 243 вообще нельзя раскрасить. А дальше придумайте раскраску на n = 242. Удобнее всего раскрасить числа так, чтобы произведения были либо достаточно маленькие, либо уже очень большие)

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

Докажем, что число $35 = 243$ не может быть покрашено. Действительно, пусть $3,$ например, синее, тогда $9 =3⋅3$ красное, $81= 9⋅9$ синее, $243= 3⋅81$ красное. Заметим, что $27$ не может быть ни красным, ни синим: если $27$ красное, то в пример $27⋅9= 243$ входят три красных числа, а если $27$ синее, то в пример $27⋅3= 81$ входят три синих числа.

Пример. Числа от $3$ до $8$ покрасим синим, числа от $9$ до $80$ — красным, числа от $81$ до $242$ — снова синим.

Ответ:

$242$

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

Задача 11#123420

Юлианский календарь устроен так: каждый год с номером, кратным $4$ — високосный; в обычном году $365$ дней, а в високосном — на $1$ больше; кроме этого, есть семидневная неделя. В результате существуют $14$ видов года: невисокосный год, начинающийся в понедельник, во вторник, . . ., в воскресенье; високосный год, начинающийся в понедельник, во вторник, . . ., в воскресенье.

Когда земляне поселились на планете Ялмез, то ввели календарь, в котором каждый год с номером, кратным $v(v > 1)$ — високосный; в обычном году $x$ дней, а в високосном — на $1$ больше; неделя по-прежнему состоит из $7$ дней. Оказалось, что в таком календаре ровно $n$ видов года. Найдите все возможные значения $n.$

Источники: ФЕ - 2020, 11.2 (см. www.formulo.org)

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

Подсказка 1

Сосредоточьтесь на остатках при делении длины года на 7. Обычный год дает остаток х, високосный — х+1. Как это влияет на день начала следующего года? Есть ощущение, что именно остаток определяет, на какой день недели сдвинется начало следующего года

Подсказка 2

Рассмотрите полный цикл из v лет. Суммарный сдвиг составит vx+1 дней. Что происходит, когда это число кратно 7? А когда не кратно?

Подсказка 3

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

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

Лемма. Если $a$ не кратно $7,$ то среди чисел

m,m + a,m + 2a,...,m +6a

встречаются числа со всеми остатками от деления на $7.$

Если это не так, то какие-то два из семи остатков совпадают, но разность между соответствующими числами равна $ka,$ где $0< k< 7,$ а $a$ взаимно просто с $7,$ то есть не кратна $7.)$

Заметим, что нас интересует не сама длина года, а только её остаток от деления на $7,$ который далее и будем обозначать (для обычного года) $x.$ Ежегодно номер начального дня недели сдвигается на $x$ для обычного года и на $x +1$ для високосного. Например, если на планете Земля $2019$ год обычный и начинался во вторник, т. е. в день $2,$ то $2020$ год начинается в день $2+ 1= 3$ (где $1$ — остаток от деления $365$ на $7),$ а $2021$ — в день $3+2 =5$ (где $2$ — остаток от деления $366$ на $7).$

Тогда за $v$ лет номер начального дня сдвигается на $vx +1$ (например, для Земли на $5$ ). Если $vx +1$ не кратно $7,$ то встречаются все $7$ типов високосных лет (см. лемму); но тогда все годы перед ними («предвисокосные») тоже различаются, итого имеем все $14$ типов лет. Если $vx+1$ кратно $7,$ то последовательные високосные годы всё время одинаковы. Примеры (указаны длины лет по модулю $7):$

$pict$

Получить ровно $7$ типов лет невозможно: если в цикле $6$ обычных лет и один високосный (то есть $v =7),$ то число дней в цикле $6x+ (x+1)$ не кратно $7;$ если в цикле больше $6$ обычных лет и длина каждого из них не кратна $7,$ то все $7$ типов обычных лет встречаются; если длина бычного года кратна $7,$ то длина цикла не кратна $7.$

Ответ:

$2,3,4,5,6,8,14$

Интенсивы

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

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

Задача 12#91341

Натуральное число $n$ назовём кубоватым, если $n3+ 13n− 273$ является кубом натурального числа. Найдите сумму всех кубоватых чисел.

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

При $n= 21$ это число равно $213$ , то есть кубу.

Если $n> 21$ , то $3 3 2 3 3 (n +1) = n +3n + 3n+ 1> n +13n− 273> n$ , то есть это не может быть квадратом.

Если $n< 21$ , то $3 3 n + 13n− 273< n$ . Значит $3 3 3 2 n +13n− 273 ≤(n− 1) =n − 3n + 3n − 1$ . Отсюда получается, что $2 3n + 10n − 283< 0$ и $2 n < 100$ .