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

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

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

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

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

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

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

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

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

Задача 1#74784

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

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

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

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

Подсказка 1

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

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

Давайте для начала докажем вспомогательную лемму: произведение $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!$

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

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

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

Задача 2#74789

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

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

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

Подсказка 1

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

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

Рассмотрим произвольный вырезаемый куб $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

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

Задача 3#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.

Ответ: да

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

Задача 4#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

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

Задача 5#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$ . Для чётных аналогично.

Ответ: да

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

Задача 6#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$

Курсы

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

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

Задача 7#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$ .