Тема ТЕОРИЯ ЧИСЕЛ

Делимость и делители (множители)

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

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

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

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

Подтемы раздела теория чисел

Разделы подтемы Делимость и делители (множители)

Условия про НОД и НОК

Разложение на множители, основная теорема арифметики

Количество, сумма, произведение делителей

Степени вхождения простых

Оценки для доказательства делимости

Алгоритм Евклида

Теоретико-числовые свойства биномиальных коэффициентов

Теоретико-числовые свойства чисел Фибоначчи

Целые гауссовы числа

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

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

Задача 1#34950

Докажите, что

02 12 n2 n (C n)+ (Cn)+ ...+ (Cn) =C 2n

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

Подсказка 1

Решение будем строить комбинаторно, а, значит, пора определяться, для какого множества (из скольки элементов) и какие объекты будем считать.

Подсказка 2

Правая часть чётко говорит брать 2n элементов и считать число подмножеств из n элементов. Слева же в каждом слагаемом перемножают цешки из n. Что бы это могло значить?

Подсказка 3

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

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

Пусть имеется множество $N$ из $n$ элементов. Тогда справа $Cn 2n$ количество его подмножеств мощности $n.$

Посмотрим теперь, что будет слева. Разделим $N$ на два непересекающихся подмножества $A$ и $B$ по $n$ элементов в каждом. В силу $k n−k Cn = Cn$ верно $k2 k n−k (Cn) =(Cn)⋅(C n ).$ Тогда $k 2 (Cn)$ количество способов выбрать в $N$ подмножество мощности $n,$ что $k$ элементов лежат в $A,$ остальные $n − k$ в $B.$ Проходясь по всем $k$ получаем всевозможные подмножества $N$ мощности $n.$

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

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

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

Задача 2#76655

Сумма всех натуральных делителей числа $n$ более чем в 100 превосходит само число $n$ . Докажите, что есть сто идущих подряд чисел, каждое из которых имеет общий делитель с $n$ больший 1.

Источники: ЮМШ-2023, 11 класс, отборочный тур (см. yumsh.ru) | ЮМШ-23/24, 11 класс, 1 отборочный тур (см. yumsh.ru)

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

Сначала докажем лемму.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма.

Пусть $φ (n)$ - функция Эйлера числа $n.$ (Количество чисел от $1$ до $n$ взаимно простых с $n.$ ) Тогда для любого натурального числа $n >1$ справедливо неравенство

∑ n2 d < φ(n)- d|n

_________________________________________________________________________________________________________________________________________________________________________________

Доказательство леммы.

Запишем сумму делителей числа через произведение сумм степеней его простых делителей. Если $n =pα1pα2...pαk, 1 2 k$ то

∑ 2 α1 2 α2 2 αk d =(1+ p1+p1+ ...+ p1 )(1+ p2+ p2+ ...+ p2 )...(1+ pk +pk+ ...+ pk ) d|n

Используя формулу суммы геометрической прогрессии, получаем:

∑ d= (1+ p + p2 +...+ pα1)(1+ p +p2+ ...+ pα2)...(1+ p +p2+ ...+ pαk)= d|n 1 1 1 2 2 2 k k k

(pα11+1 − 1)(pα22+1− 1)...(pαk+1− 1) = ----(p1−-1)(p2-− 1)...(pkk− 1)--.

Функция Эйлера вычисляется по формуле $φ(n)=pα11−1(p1− 1)pα22−1(p2− 1)...pαkk− 1(pk− 1).$ Тогда чтобы получить $φ(n)$ в знаменателе, домножим числитель и знаменатель на $pα11−1pα22−1...pαkk−1$

(pα11+1−-1)(pα22+1−-1)...(pαkk+1−-1)= (p1− 1)(p2− 1)...(pk− 1)

α1−1 α2−1 αk−1 α1−1 α2−1 αk−1 = p1--p2α1−.1..pk--(pα12−1-− 1)(p2-α−k−11)...(pk---−-1)= p1 (p1− 1)p2 (p2− 1)...pk (pk− 1)

(p2α1 − pα1−1)(p2α2− pα2−1)...(p2αk− pαk−1) p2α1p2α2...p2αk n2 = --1----1-----2--φ(2n)------k----k----< -1--2φ(n)--k--= φ(n)

_________________________________________________________________________________________________________________________________________________________________________________

Решение задачи.

По условию и лемме

∑ -n2- 100n < d|nd< φ(n).

Тогда

100n< -n2-⇒ φ(n)< n-. φ(n) 100

То есть количество чисел от $1$ до $n$ взаимно простых с $n$ меньше $-n- 100.$

Рассмотрим два случая: $n$ делится на $100$ и $n$ не делится на $100.$

1. Число $n$ делится на $100.$ Тогда можно разбить числа от $1$ до $n$ на $n-- 100$ групп по $100$ идущих подряд чисел. Если количество чисел от $1$ до $n$ взаимно простых с $n$ меньше $n-- 100$ , то хотя бы в одной группе не будет числа взаимно простого с $n$

2. Число $n$ не делится на $100.$ Тогда среди чисел $2$ до $n$ можно выделить $-n- [100]$ групп по $100$ идущих подряд чисел. Если в каждой группе будет число взаимно простое с $n$ , то чисел взаимно простых с $n$ хотя бы $n [100]+ 1$ ( $1$ тоже взаимно проста с $n$ ). Это противоречит тому, что количество чисел от $1$ до $n$ взаимно простых с $n$ меньше $n 100-$

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

Задача 3#78889

Можно ли вычеркнуть из произведения $1!⋅2!⋅3!⋅...⋅56!$ один из факториалов так, чтобы произведение оставшихся было квадратом целого числа?

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

2 2 2 28 2 1!⋅...⋅56!=(1!) ⋅2⋅(3!) ⋅4 ⋅...⋅(55!) ⋅56=2 ⋅(1!⋅3!⋅...⋅55!)⋅28!

Отсюда видно, что, вычеркнув $28!,$ мы получим квадрат числа $214⋅1!⋅3!⋅...⋅55!.$

Ответ:

Да, можно

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

Задача 4#78899

Дано $41$ различное натуральное число, меньшее $1000.$ Известно, что среди любых трех из них есть два, дающих в произведении точный квадрат. Докажите, что среди этих чисел есть точный квадрат.

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

Предположим, что среди этих чисел нет точного квадрата. Обозначим через $p ,...,p 1 n$ все простые числа, меньшие $1000.$ Заметим, что по условию каждое выписанных чисел раскладывается в произведение $p1,...,pn$ в некоторых степенях. Каждое из наших простых чисел входит в одно выписанное число в четной или нечетной степени. Сопоставим каждому выписанному числу последовательность из $0$ и $1$ длины $n.$ Число на $i$ - ой позиции будет равно $1,$ если $pi$ в ходит в выписанное число в нечетной степени и $0$ в противном случае (на самом деле это и есть бесквадратная часть, про которую мы говорили в теории). Предположим, что среди последовательностей выписанных чисел есть три различные. Тогда для трех соответствующих этим последовательностям чисел не выполнено условие (два числа в произведении могут давать точный квадрат, только если четности вхождения каждого $pi$ - ого одинаковые).

То есть мы показали, что различных последовательностей может быть не больше $2.$ Обозначим эти последовательности через $a1,...,an$ и $b1,...,bn.$ Обозначим через $a a b b a =p11⋅⋅⋅pnn,b= p11 ⋅⋅⋅pnn .$ Очевидно что $a⁄= b.$ Считаем. что $a< b,$ тогда $a ≥2,b≥ 3,$ так как при $a= 1$ мы получим, что числа являются квадратами, а мы предположили, что их нет. Каждое из выписанных чисел дает точный квадрат либо при делении на $a,$ либо при делении на $b.$ Причем для чисел, которым соответствуют одинаковые последовательности, эти квадраты должны быть различными. Рассмотрим наибольшее выписанное число, которому соответствует последовательность $a$ -шек. Оно равно $a⋅s2$ для некоторого натурального $s,$ откуда $s2 ≤ 500,$ то есть $s≤ 22.$ Но тогда количество выписанных чисел, которым соответствует первая последовательность, не превосходит $22.$ Аналогично поступаем со второй последовательностью. Опять рассматривает наибольшее число $bh2 ≤1000,$ откуда $h2 ≤ 1000∕3,$ то есть $h≤ 18,$ откуда таких чисел не больше $18.$ То есть всего чисел не больше, чем $22+ 18 =40.$ Получили противоречие с количеством данных чисел.

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

Задача 5#78906

Найдите все такие составные числа $n,$ что для любого разложения на два натуральных сомножителя $n= xy$ сумма $x +y$ является степенью двойки.

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

Подставив $x= 1,y = n,$ получим, что $n= 2k− 1$ для некоторого натурального $k.$ Пусть $n =ab,$ где $a≥ b>2,$ и пусть $a +b= 2t$ для некоторого натурального числа $t.$ Очевидно, что $k >t.$ Тогда

k t 2 +2 = ab+ a+b+ 1= (a+ 1)(b+1), 2k− 2t = ab− a− b+ 1= (a− 1)(b− 1)

Перемножив эти равенства, получим, что число $(a − 1)(a +1)× (b− 1)(b+ 1)$ делится на $2t 2 .$ Но двойка входит в одно из чисел $b− 1$ или $b+1$ в первой степени, а во второе — в степени, не большей $t− 1.$ Аналогично для чисел $a − 1$ и $a+ 1.$ Следовательно, делимость на $2t 2$ возможна, только если в обеих упомянутых оценках двойки входит в степени ровно $t− 1.$ Это возможно, лишь если $t−1 t−1 b= 2 − 1,a =2 + 1$ (поскольку $a≥ b$ и $t a+b =2$ ). Тогда $k= 2t− 2$ и $k 2 − 1$ делится на $3.$ Значит, можно считать, что в наших рассуждениях выбрано $b =3.$ Тогда $a= 5,$ и $n= 15$ — единственное подходящее число.

Ответ:

$n =15$

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

Задача 6#79329

Докажите, что если $n+ 1$ делится на $24,$ то сумма всех делителей натурального числа $n$ тоже делится на $24.$

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

Подсказка 1

Видим, что задача на остатки! Тогда сразу же нужно разложить число 24 на степени простых и понять, какие остатки имеет n при делении на эти числа.

Подсказка 2

Число n имеет остаток 2 при делении на 3 и остаток 7 при делении 8. Теперь наша задача — понять что-то про сумму всех делителей числа n. Поскольку мы ничего не знаем про эти делители в совокупности, можно попробовать разбить их на пары определённым образом. (Почему делителей у n чётное число?)

Подсказка 3

Наши пары делителей — d и n/d. Произведение каждой пары равно n и имеет соответствующие остатки при делении на 3 и 8. Осталось осуществить небольшой перебор и понять, какие пары остатков могут давать d и n/d при делении на 3 и 8!

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

Так как $n+ 1$ делится на $3$ и $8,$ то $n$ при делении на $3$ даёт остаток $2,$ а при делении на $8$ — остаток $7.$

Разобьём делители на пары вида $(d,n∕d),$ так как число $n$ не может быть полным квадратом ввиду противоречия с делимостью на $3.$ Заметим, что если $d$ даёт остаток $1$ при делении на $3,$ то $n∕d$ даёт остаток $2$ и наоборот. Поэтому сумма делителей в каждой такой паре кратна $3.$

Аналогично, сумма делителей в каждой такой паре кратна $8.$

Курсы

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

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

Задача 7#79759

Даны натуральные числа $a$ и $b$ такие, что число $a+-1+ b+-1 b a$ является целым. Докажите, что наибольший общий делитель чисел $a$ и $b$ не превосходит числа $√ ---- a+b.$

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

Имеем:

a+-1 b+-1 a2+-b2+a-+b b + a = ab

Пусть $d$ — наибольший общий делитель чисел $a$ и $b.$ Так как $ab$ делится на $2 d ,$ то $2 2 a + b+ a+ b$ делится на $2 d.$ Число $2 2 a +b$ также делится на $2 d .$ Поэтому $a+b$ делится на $2 d$ и $√---- a +b≥ d.$

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

Задача 8#79760

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

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

Давайте докажем, что если числа $a$ и $b$ различны, то НОД $(a,b)≤ a+b 3$ . Пусть $a< b$ , тогда НОД $(a,b)≤a$ , а 2НОД $(a,b)≤ b$ (так как $b$ делится на НОД $(a,b)$ , но равно быть не может, так как числа не равны и $b$ большее число, значит, 2НОД $(a,b)≤ b$ ). Получили, что 3НОД $(a,b)≤a +b$ . Давайте для каждого ребра запишем полученную оценку и сложим все неравенства, каждая вершина используется в трех неравенствах, поэтому сумма всех НОДов меньше либо равна суммы всех чисел. Предположим, что эти суммы равны, тогда равенство достигается в каждом неравенстве, выше. То есть равенство возможно только при $b= 2a$ или $a =2b$ (для каждого ребра).

Не теряя общности пусть $a= 2b$ , но тогда: либо $c=b$ , тогда нашлись два равных числа, либо $c= 4b$ , но также $d =b$ или $d= 4b$ , то есть в любом случае найдутся хотя бы два равных числа, противоречие, значит, равенства быть не могло. Таким образом, сумма всех НОДов меньше суммы всех чисел.

Ответ:

Нет

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

Задача 9#82085

Про натуральные числа $a,b,c$ известно, что $ab$ делится на $2c,bc$ делится на $3a$ , а $ac$ делится на $5b$ . Найдите наименьшее возможное значение их произведения $abc$ .

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

Подсказка 1

Обратите внимание, что если w является делителем x и y является делителем z, то xz кратно wy. Как это можно применить относительно нашего условия?

Подсказка 2

Правильно, перемножив попарно все три условия кратности и сократив лишнее, получим, что a² ⫶ 10, b² ⫶ 6 и c² ⫶ 15. Все эти числа не включают в себя полные квадраты. Что это говорит о числах a, b и c?

Подсказка 3

Правильно, сами числа тогда тоже делятся на 10, 6 и 15 соответственно, а значит, не могут быть меньше них. Тогда и abc тоже будет не меньше произведения этих чисел.

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

.. .. 2 .. 2.. ab.2c,bc.3a =⇒ ab c.6ac =⇒ b .6

Но раз квадрат $b$ делится на 2 и на 3, то и само $b$ делится на 2 и на 3. Тогда $b...6$ , значит, $b≥ 6.$

.. .. 2 .. 2.. ab.2c,ac.5b =⇒ a bc.10bc =⇒ a .10

Но раз квадрат $a$ делится на 2 и на 5, то и само $a$ делится на 2 и на 5. Тогда $a...10$ , значит, $a≥ 10.$

bc...3a,ac...5b =⇒ abc2...15ab =⇒ c2...15

Но раз квадрат $c$ делится на 3 и на 5, то и само $c$ делится на 3 и на 5. Тогда $. c..15$ , значит, $c≥ 15.$

В итоге $abc≥ 10⋅6⋅15= 900,$ причём при $a =10$ , $b= 6$ , $c= 15$ достигается равенство.

Ответ: 900

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

Задача 10#83298

Найти сумму максимальных нечетных делителей каждого из целых чисел на отрезке $[61;120]$ .

Источники: Росатом - 2024, московский вариант, 11.3 (см. olymp.mephi.ru)

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

Подсказка 1

Интересно, что чисел от 61 до 120 ровно столько же, сколько нечётных от 1 до 120.

Подсказка 2

Чем нечётные отличаются от чётных? Наличием степени двойки. Тогда как удобно представить все числа?

Подсказка 3

Из первого замечания про количество нечётных хочется посмотреть, а сколько чисел вида n * 2ᴷ для каждого нечётного n (меньшего 120) лежит в промежутке от 61 до 120.

Подсказка 4

Оказывается, для каждого такого n одно своё n * 2ᴷ в промежутке от 61 до 120. Попробуйте понять, почему это так, и досчитать искомую сумму нечётных n!

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

Для каждого нечетного числа $n$ в промежутке 1 до 119 рассмотрим числа вида $n⋅2k$ , где $k∈ ℕ∪ {0}.$ Докажем, что для каждого $n$ найдётся ровно одно число вида $k n⋅2$ на промежутке от 61 до 120.

Пусть на нашем промежутке не нашлось нужного числа. Тогда должна найтись такая пара чисел $k k+1 (n⋅2 ;n ⋅2 )$ , что

k k+1 n⋅2 ≤ 60, n⋅2 ≥121,

что невозможно, поскольку из первого следует, что

k+1 n ⋅2 ≤ 120

Тогда из нашего утверждения следует, что для любого нечётного числа $n$ , меньшего 120, найдётся число от 61 до 120, что его наибольшим нечетным делителем будет $n$ . Причём для каждого $n$ такое число уникально. При этом нечётных чисел от 1 до 120 ровно 60, как и чисел от 61 до 120. Получается, что искомая сумма равна сумме всех нечётных чисел от 1 до 120.

1+-119- 1+3+ ...+ 119= 2 ⋅60= 3600

Ответ: 3600

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

Задача 11#85447

На доске в ряд написаны $2n$ простых чисел. Известно, что среди них менее $n$ различных. Докажите, что можно выбрать несколько подряд идущих написанных чисел, произведение которых является точным квадратом.

Источники: Ломоносов-2016, 11.8 (см. olymp.msu.ru)

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

Рассмотрим произведения первых $k$ чисел в ряду. Всего таких произведений $2n+ 1$ (также учитваем произведение, в котором $0$ простых чисел, будем считать, что оно равно $1$ ).

Ясно, что произведение чисел любой подпоследовательности этого ряда — частное каких-то двух произведений первых чисел.

Пусть ряд состоит из чисел $p1,p2,...,pk(k ≤n − 1).$ Тогда любое произведение первых чисел имеет вид $α1 α2 αk p1 p2 ...pk .$ Если мы найдём два произведения первых чисел, у которых чётности соответствующих $αi$ совпадают, то мы найдём подпоследовательность ряда, произведение чисел которой равно квадрату.

Всего существует $k 2$ наборов чётностей $αi$ (каждое $αi$ либо чётное, либо нет). Осталось заметить, что $k n−1 n 2 ≤ 2 < 2 + 1.$ Значит, найдутся два произведения с одинаковым набором чётностей у $αi,$ получили требуемое.

Интенсивы

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

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

Задача 12#85451

Для любых натуральных $a,b$ и $c$ докажите неравенство

(a,b− 1)(b,c− 1)(c,a − 1)≤ ab+bc+ ca

(Как обычно, $(x,y)$ обозначает наибольший общий делитель чисел $x$ и $y.$ )

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

Заметим, что

ab+ bc+ ca> ab+bc+ ca− a− b− c+1 =abc− (a− 1)(b− 1)(c− 1)

Но эта разность делится на произведение НОДов. Действительно, $a$ делится на $(a,b− 1),b$ делится на $(b,c− 1)$ и $c$ делится на $(c,a− 1),$ следовательно $abc$ делится на произведение НОДов. Аналогично $(a− 1)(b− 1)(c− 1)$ делится на произведение НОДов, а тогда и разность делится. Но тогда эта разность не меньше, а $ab+bc+ ca$ больше произведения НОДов.

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

Задача 13#85914

Докажите, что уравнение

5m2−-n n2+ 3m =1

имеет бесконечно много решений в целых числах.

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

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

Подсказка 1

Для начала просто решим уравнение 5m^2 - 3m = n^2 + n. У нас есть квадраты обеих переменных, а значит нужно попробовать выделить два полных квадрата.

Подсказка 2

Заменим один получившийся квадрат на х, а другой на y. Должно получиться уравнение x^2 - 5y^2 = 4. Нам нужно доказать, что у уравнения бесконечное число решений. В таком случае, решение уравнения может быть связано с каким-либо бесконечным числовым рядом. Какую известную последовательность чисел вы знаете?

Подсказка 3

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

Подсказка 4

В конце не забудьте проверить, что m и n получаются целые. Для этого можно заметить, что последовательность остатков чисел Фибоначчи по модулю 10 периодична. Так же нужно понять, зануляется ли в этих случаях знаменатель.

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

Решим сначала уравнение

2 2 5m − n = n +3m

______________________________________________________________________________________________________________________________________________________

5m2 − 3m = n2+ n

Умножим на 4 и прибавим 1 к обеим частям, чтобы выделить полный квадрат справа:

20m2− 12m+ 1= (2n+1)2

Теперь домножим обе части на 5 и выделим полный квадрат слева:

(10m− 3)2 =5(2n+ 1)2+ 4

Сделаем замену $x= 10m− 3,y = 2n +1$ . У получившегося уравнения

x2− 5y2 =4

имеются решения

x= ±(F2k−1+F2k+1),y =±F2k,k≥ 0,

где $Fk$ — числа Фибоначчи (мы пользуемся нумерацией $F0 = 0,F1 = 1,Fk+1 = Fk+ Fk−1$ при всех целых $k$ ). На самом деле

(Fk−1+ Fk+1)2− 5F2k = 4F2k− 1+4Fk−1Fk− 4F 2k

равно $k (−1)4$ для всех $k$ , что легко проверить по индукции: при $k= 0$ это выполняется, а если $2 2 k Fk−1+Fk−1Fk− Fk =(−1)$ , то и

F2k + FkFk+1− F2k+1 =Fk2− Fk−1Fk− F2k−1 = (−1)k+1

(Можно доказать с помощью теории уравнений Пелля, что $2 2 x − 5y = 4$ не имеет других решений.)

Теперь нужно найти бесконечно много $x$ и $y$ таких, для которых соответствующие $x+3 m = 10$ и $y−1 n= 2$ целые. Заметим, что последовательность остатков чисел Фибоначчи по модулю 10 периодична (так как пара ( $Fk−1,Fk$ ) может принимать конечное количество вариантов по модулю 10, а остаток следующего и предыдущего чисел Фибоначчи однозначно определяются по остаткам этой пары). Кроме того, $x =F2 =1$ и $y =F1 +F3 = 3$ подходят, они соответствуют тривиальному решению $m = n= 0$ . Значит, уравнение $5m2 − n =n2 +3m$ имеет бесконечно много решений.

_________________________________________________________________________________________________________________________________________________________________________________

Осталось понять, что они все не могут обнулять знаменатель. Действительно, если $(m,n)$ — решение уравнения $5m2− n= n2+ 3m$ , при котором $n2+ 3m =0$ , то и $5m2− n= 0$ . Следовательно, $25m4 + 3m = 0$ . Так как $m$ целое, то обязательно $m = 0$ (иначе $|| 4|| 25m > |3m|$ ), а значит, и $n= 0$ . Остальные пары $(m,n)$ нам подходят.

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

Задача 14#88062

На какое самое большое натуральное число будет гарантированно делиться произведение любых шести подряд идущих натуральных чисел?

Ответ обоснуйте.

Источники: Межвед - 2024, 11.1 (см. v-olymp.ru)

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

Подсказка 1

Давайте сначала попробуем найти верхнюю границу (число больше которого искомое точно быть не может)

Подсказка 2

Теперь осталось доказать что (n + 1)(n + 2)...(n + 6) делится на 720 для любого натурального n. Давайте вспомним сочетания из комбинаторики

Подсказка 3

Действительно,

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

Поскольку произведение первых 6 натуральных чисел равно $6!= 720,$ то искомое число не больше $720.$

Осталось доказать, что произведение любых подряд идущих 6 натуральных чисел $n+ 1,n +2,...,n+ 6$ делится на $720$ . Поделим:

(n +1)(n +2)...(n+ 6) (n +6)! 6 --------6!--------= -6!n!--= Cn+6

и получим натуральное число способов выбрать шестёрку из $n+ 6$ элементов. Действительно, делится.

Ответ: 720

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

Задача 15#88133

В тюрьме находятся 100 камер, пронумерованных числами от 1 до 100. Тюремщик Джон Фридом, осуществляя частичную амнистию, поступил следующим образом. Сначала он открыл все камеры. Затем запер каждую вторую камеру. На третьем этапе он повернул ключ в замке каждой третьей камеры (открыл запертые и запер открытые). Продолжая действовать таким образом, на сотом этапе он повернул ключ только в замке последней сотой камеры, а затем выпустил всех заключенных, которые оказались в открытых камерах. Укажите номера камер, в которых сидели счастливчики.

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

Подсказка 1

Подумаем, что с точки зрения теории чисел значит, что в момент k-го прохода (когда тюремщик проходится по камерам k-й раз и поворачивает замок в каждой k-й) повернулся замок в камере с номером n? Например, в третий раз он меняет состояние 3, 6,… 99 двери, что нам это напоминает?

Подсказка 2

Верно, такое действие означает, что n является кратным числа k, или же k — делитель n. Если в конце дверь оказалась открыта, значит, замок поворачивали нечетное количество раз. Что мы получим, сопоставив эти две мысли?

Подсказка 3

Таким образом, отрыты в конце те двери, у номеров которых нечетное число делителей. У любого числа все (или почти все) делители можно поделить на пары. Подумаем, когда же реализуется это “почти”, которое нас и приведет к решению задачи!

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

Назовем проходом с номером $k$ изменение состояний каждой $k$ -той камеры. Рассмотрим камеру с номером $n$ . Найдем сколько раз она меня свое состояние с открытой на закрытую или наоборот. Пусть камера поменяла свое состояние на проходе с номером $m$ , тогда номер камеры $n$ делится на $m$ . Таким образом, камера с номером $n$ меняла свое состояние столько раз, сколько различных делителей она имеет.

Заметим, что после каждой нечетной смены состояний камеры она является открытой, а после каждой четной — закрытой. Таким образом, в конце камера будет открыта тогда и только тогда, когда количество смен ее состояний, то есть количество делителей ее номера является нечетным числом. Докажем, что число имеет нечетное количество делитей тогда и только тогда, когда является полным квадратом. Как известно, число делителей числа $a1 a2 al n = p1 p2 ...al$ равно $σ(n)= (1 +a1)(1+ a2)...(1+ al)$ — нечетное число, но тогда число $1+ ai$ нечетно при всех $i= 1,...,l$ , следовательно, каждое из чисел $ai$ при всех $i=1,...,l$ делится на 2, то есть степень вхождения любого простого числа в $n$ четна, а значит $n$ является квадратом. Аналогично, если $n$ суть полный квадрат, то числа $ai$ при всех $i= 1,...,l$ делятся на 2, следовательно, $σ(n)= (1+ a1)(1+a2)...(1+al)$ — нечетно.

Наконец, открытыми будут те и только те камеры, номера которых есть полный квадарт, то есть 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.

Ответ: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100

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

Задача 16#88137

Найдите сумму максимальных нечётных делителей всех чисел от 601 до 1200 включительно.

Источники: по мотивам Росатома - 2024, 11.3

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

Подсказка 1

Зададимся вопросом, что означает тот факт, что у двух чисел из отрезка [601; 1200] одинаковый наибольший нечётный делитель. Если это так, как могут отличаться эти два числа?

Подсказка 2

Если у двух чисел одинаковый наибольший нечётный делитель, то состав нечётных простых, в них входящих, идентичен у двух чисел, и отличаться эти числа могут только степенью вхождения двойки. Может ли такое случиться для двух чисел из данного отрезка?

Подсказка 3

Такая ситуация невозможна, ведь на отрезке нет чисел, которые отличаются друг от друга хотя бы в два раза. Какой вывод можно сделать из этого рассуждения?

Подсказка 4

Тогда мы получили, что искомые делители у всех наших чисел различны. Делитель не может быть больше самого числа, поэтому мы не получим делители, превосходящие 1200. Тогда не остаётся выбора, какие нечётные числа брать :)

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

Пусть $S =a +a + ...+a 601 602 1200$ — сумма максимальных нечётных делителей чисел на отрезке $[601,1200]$ , причём $a i$ является максимальным нечётным делителем числа $i$ для всех $i∈{601,602,...,1200}.$

Пусть $n$ — натуральное нечётное число на отрезке $[1;1200]$ . Докажем, что $n$ совпадает с $aj$ для некоторого $j ∈ {601,602,...,1200}$ . Предположим противное. Рассмотрим ряд

2 n,2n,2 n,...

Поскольку $n< 1200$ , то существует натуральное число $i$ такое, что $2in< 601$ , а $2i+1n> 1200$ , что невозможно.

Таким образом, каждое нечётное число на отрезке $[1;1200]$ совпадает с $a j$ для некоторого $j ∈ {601,602,...,1200}$ . Осталось заметить, что на отрезке $[1,1200]$ каждое второе число является нечётным, следовательно, количество нечётных чисел равно 600, ровно из стольких слагаемых состоит $S$ , то есть никаких других чисел там нет. Наконец, по формуле суммы членов арифметической прогрессии

1200 1+ 3+...+1199= 1200⋅-4--= 1200⋅300= 360000.

Ответ: 360000

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

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

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

Задача 17#89087

Докажите, что

0 2 4 2[n2] n−1 C n+ Cn+ Cn+ ...+ Cn = 2

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

Подсказка 1

Хотим построить комбинаторное решение. Надо определиться, из скольких элементов множество мы будем рассматривать и какие объекты считать.

Подсказка 2

Судя по левой части, мы должны выбирать по сколько-то из n элементов, тогда логично взять множество из n элементов. Число каких объектов тогда считается слева?

Подсказка 3

Верно, количество подмножеств, состоящих из чётного числа элементов. Теперь хочется понять, что с правой частью. Двойка в степени n-1, работать с двойкой в степени мы умеем (всевозможные подмножества). Только для этого нужен n-1 элемент, так что один отложим.

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

Пусть имеется множество $N$ из $n$ элементов.

Поймём что слева слагаемое $2k Cn$ это количество подмножеств $N$ мощности $2k,$ а вся сумма тогда равна количеству подмножеств $N,$ содержащих чётное число элементов.

Теперь посчитаем число этих же объектов так: выделим в $N$ элемент $A,$ тогда для каждого подмножества $M$ из оставшегося числа элементов, либо $M$ содержит чётное число элементов, либо $M$ в объединении с $A$ содержит чётное число элементов. Причём таким образом рассмотрены всевозможные чётные подмножества, а значит их $n−1 2 .$

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

Задача 18#89088

Докажите тождество

1 2 3 n n− 1 Cn+ 2Cn+ 3C n+ ...+nC n = n2

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

Подсказка 1

Нетрудно понять, какое множество хотим рассматривать (из скольки элементов). Вопрос в том, что за объекты будем считать.

Подсказка 2

Справа непонятно совсем, поэтому давайте думать что за цешка из n по k, умноженная на k.

Подсказка 3

Отлично, цешка из n по k, умноженная на k - это количество подмножеств из k элементов с выделенным главным элементиком. Теперь не составляет труда понять, почему справа считается то же самое.

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

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

Слагаемое слева $k kCn$ означает число способов выбрать группу из $k$ школьников, а затем дежурного в ней. Сложив по всем $k$ получаем число всевозможных групп с дежурным.

Можно же сначала $n$ способами выбрать дежурного, затем оставшихся распределить в группу или нет. Получаем справа также посчитано число искомых объектов.

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

Задача 19#89089

Для $n> 2$ докажите тождество

1 2 2 2 32 n−12 2 n− 2 1⋅(n− 1)⋅(Cn) +2 ⋅(n− 2)⋅(Cn) + 3⋅(n − 3)⋅(Cn)+ ...+ (n− 1)⋅1⋅(Cn ) =n ⋅C2n−2

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

Подсказка 1

Выглядит, конечно, мощно давайте разбираться, что у нас считается слева. Что могут значит квадраты цешек?

Подсказка 2

Действительно, квадраты намекают на деление на две группы по n, коэффициенты перед цешками на выбор одного из них. Давайте совмещать идеи.

Подсказка 3

Осталось понять, как сделать так (как хорошо преобразовать цешки), чтобы слева было во всех слагаемых что-то разумное (похожее) по смыслу. Затем осознать, что справа тот же объект, посчитанный с другой стороны

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

Пусть имеются два класса $A$ и $B$ по $n$ школьников, из которых требуется выбрать по дежурному, а также включающую их группу из $n$ активистов.

В силу $k n−k Cn =C n$ верно $k 2 k n−k k⋅(n− k)⋅(Cn) = k⋅Cn⋅(n− k)⋅Cn .$

Слагаемое слева $k 2 k⋅(n− k)⋅(Cn)$ количество способов выбрать $n$ активистов из которых в $A$ классе $k$ школьников, один из которых дежурный, остальные в $B$ классе с одним дежурным в нём. Сложив по всем $k$ получаем число всевозможных групп из $n$ активистов, в которых по одному дежурному в каждом из классов.

Можно же сначала $2 n$ способами выбрать в группу активистов по дежурному с классов, а затем из остальных школьников добрать группу. Получаем справа также посчитано число искомых объектов.

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

Задача 20#89090

Даны натуральные $n,m$ такие, что $m < n.$ Докажите, что

0 m 0 1 m 1 n m n (− 1) ⋅0 ⋅C n+(−1) ⋅1 ⋅Cn +...+ (−1) ⋅n ⋅Cn =0

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

Подсказка 1

Ищем комбинаторный смысл. Что первое приходит в голову? А вот над объектом, который будем подсчитывать стоит подумать, всё-таки плюсы/минусы весьма непонятно.

Подсказка 2

Ага, вполне логично рассмотреть множество из n элементов (пусть уж они будут детьми), и будем в слагаемых слева выбирать группу и раздавать её участникам m различных шариков. Может есть идеи для объекта?

Подсказка 3

Подсчитать можно следующий объект: распределение шариков детям. Ясно, что любое распределение слева посчитано в нескольких слагаемых. Давайте посчитаем вклад данного распределения шариков в ответ.

Подсказка 4

Для этого можно зафиксировать детей, у которых окажутся шарики при данном распределении (это не все дети, поскольку m<n), и посмотреть на группы добираемые к ним.

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

Предположим, что у нас есть $n$ детей и $m$ разных шариков. И мы хотим эти шарики раздать детям (некоторые дети могут получить больше одного шарика). В левой части в слагаемом $m k k C n$ мы сначала выбираем $k$ детей, которым будем давать шарики, а затем считаем количество способов раздать выбранным $k$ детям эти шарики. То есть один способ раздачи шариков посчитан в нескольких слагаемых. Зафиксируем произвольный способ раздачи шариков. Пусть в нем ровно у $x$ детей есть хотя бы один шарик. Тогда в слагаемом $m k k Cn$ этот способ посчитан 0 раз, если $k <x$ и $k−x Cn−x$ раз, если $k ≥x$ (то есть мы к зафиксированным $x$ детям добавляем еще $k− x$ ). Таким образом, суммарно в левой части наш зафиксированный способ посчитан следующее число раз.

(− 1)xCxn−−xx+ (−1)x+1Cxn+−1x−x+ ...+ (− 1)nCnn−−xx =0

Так как сумма $ℓ Cn−x$ по всем $ℓ$ равна $n− x 2 ,$ а сумма по всем четным $ℓ$ числа $ℓ Cn−x$ равна $n−x−1 2 .$ То есть сумма по всем нечетным $ℓ$ чисел $ℓ Cn−x$ также равна $n−x−1 2 .$ Тогда знакопеременная сумма $ℓ Cn−x$ по всем $ℓ$ равна $0.$ То есть любой зафиксированный способ посчитан в левой части $0$ раз. Значит, и все выражение в левой части равно $0.$

Предыдущий раздел

Следующий раздел