Теория чисел на ФЕ —Каталог задач по Олимпиадной математике

Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Теория чисел на ФЕ

Тема Формула Единства

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

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

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

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

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

Подтемы раздела формула единства

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

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

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

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

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

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

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

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

Задача 3#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$ входят три синих числа.