Тема ИТМО (Открытка)

Теория чисел на ИТМО

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

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

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

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

Подтемы раздела итмо (открытка)

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

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

Задача 1#82288

Натуральные делители натурального числа $n$ занумеровали по возрастанию: $d = 1, d ,...,d = n 1 2 k$ . Оказалось, что $d =120 18$ . Какое наименьшее значение может принимать число $n$ ?

Источники: ИТМО-2024, 11.3 (см. olymp.itmo.ru)

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

У числа $120 =23⋅5⋅3$ шестнадцать делителей и все они являются делителями числа $n$ . Если $n$ делится на $24$ , то к этим делителям добавляются ещё числа 16,48 и 80 , то есть 120 — это уже как минимум девятнадцатый делитель.

Если $n$ делится на $2 3$ , то к исходным шестнадцати делителям добавляются 9,18 и 45 . Если $n$ делится на $2 5$ , то к исходным шестнадцати делителям добавляются 25,50 и 75.

Значит, $n$ делится на какое-то простое число $p$ , кроме 2,3 и 5 . Если это число не превосходит 40 , то числа $p,2p$ и $3p$ являются делителями $n$ , меньшими 120 , и мы опять получаем слишком много делителей. Значит, $p$ хотя бы 41 , то есть $n≥ 120⋅41$ . Заметим, что это число нас как раз устраивает.

Ответ: 4920

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

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

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

Задача 2#68640

Простые числа $p,q$ и $r$ таковы, что

2 2 2 p< q,p +q =r,p +q = r − 116

Найдите $p,q$ и $r.$

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

Возведём первое равенство в квадрат:

2 2 2 p +2pq+ q = r

Далее вычтем из полученного второе исходное равенство:

2 2pq =116= 2 ⋅29

Значит, учитывая, что $p< q,$ получаем:

p= 2,q = 29⇒ r= p+ q = 31

Ответ:

$p =2,q = 29,r= 31$

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

Задача 3#68709

Последовательность $x n$ задана рекуррентным соотношением $x = x + {x } n+1 n n$ и начальным условием $x = 1-. 0 67$ Найдите $[x66000].$

( $[a]$ — целая часть числа $a,$ ${a}$ — дробная часть числа $a).$

Источники: ИТМО-2023, 11.7 (см. olymp.itmo.ru)

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

Пусть оказалось так, что ${x }= {x} k+i i$ для некоторого $k >0$ . Тогда выполнено $x − x = x − x k+i i 2k+i k+i$ . Действительно, на каждой следующей итерации мы учитываем только дробную часть исходного числа (целая же часть определяет только нашу “точку старта”). Поэтому выполнено равенство ${x2k+i}= {xk+i}$ . Также отсюда будет следовать $[xk+i]− [xi]= [x2k+i]− [xk+i]$ , то есть наш сдвиг по целой части будет таким же. Нетрудно видеть, что оба условия вместе дадут $xk+i− xi = x2k+i− xk+i$ (если известно ${xk+i}= {xi}$ ). Далее остаётся только найти цикл нужной длины. Оказывается, что $1 x66 = 337$ и выполнено ${x0}= {x66}$ , мы получили цикл, получаем

[x66000]= [x0+66⋅1000]= 1000 ⋅([x66− x0])= 1000⋅33= 33000

Замечание. Как же найти такой цикл, не считая вручную все $66$ значений до него? Во-первых, уже $66 1- {x33}= 67 = 1− 67$ , что явно нам намекает, когда мы снова встретим единицу (по сути мы каждый раз умножаем дробную часть на 2, поэтому можно сразу сделать вывод, что на $66$ шаге, поскольку за столько же шагов результат возведётся в квадрат по модулю $67$ ). Во-вторых, уже на шестом шаге мы получим $3- {x6}= 1− 67$ , поэтому далее можно попробовать идти по кратным шести индексам, чтобы быстрее добраться до $66$ . Почему вообще всё это имеет смысл? Потому что $66000$ делится и на 6, и на 33, и на 66 — именно в них мы и ждём больше всего увидеть цикл, чтобы задача после этого решилась быстро и легко.

Ответ: 33000

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

Задача 4#88135

Сумма двух различных натуральных делителей натурального числа $n$ равна 100. Какое наименьшее значение может принимать число $n?$ (Среди указанных делителей могут быть единица и само число.)

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

Если один из наших делителей — само число $n$ , а второй — некоторое число $d$ и $n= dk$ , то мы получаем

100= d+ dk =d(k+ 1)

n ( 1) 100= n+ k = n⋅ 1+ k

Чем $k$ больше, тем и само $n$ больше.

Наименьшее $k >1$ такое, что $k+ 1$ является делителем 100, это 3. При таком $k$ получаем $n =75$ .

Если же $n$ нет среди двух наших делителей, то $n n 2 + 3 ≥100$ , откуда $n ≥120$ .

Ответ: 75

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

Задача 5#74576

$427000− 82$ делится на $3n.$ Какое наибольшее натуральное значение может принимать $n?$

Источники: ИТМО-2022, 11.3 (см. olymp.itmo.ru)

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

27000 27000 27000⋅26999-⋅32- 27000⋅...⋅26998⋅33- 4 =(1+ 3) = 1+ 27000⋅3+ 2 + 6 +

27000⋅...⋅26997⋅34 27000 ⋅...⋅26996⋅35 + ------24-------+ -------120-------...

Два последних выписанных слагаемых делятся на $36,$ как и все остальные слагаемые, заключённые в многоточие.

2 3 1+ 27000⋅3+ 27000⋅26999-⋅3--+ 27000⋅26999⋅26998⋅3-= 1+ 81000+ 2 6

+27000⋅26999⋅32+27000⋅26999⋅26998⋅32 2

Заметим, что

1+ 81000= 1+ 81(1+ 999)= 1+ 81+ 81 ⋅999= 82+ 81 ⋅999

Это даёт остаток $82$ при делении на $36,$ так как последнее слагаемое делится на $36.$

2 2 2 27000⋅26999-⋅3-+-272000⋅26999-⋅26998⋅3-= 27000⋅26999⋅32-⋅(1+26998)-

А это число, очевидно, делится на $35,$ но не на $36.$ Значит, $427000 − 82$ также делится на $35,$ но не на $36.$

Ответ: 5

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

Задача 6#99641

Найдите сумму натуральных чисел от $1$ до $3000$ включительно, имеющих с числом $3000$ общие делители, большие $1.$

Источники: ИТМО - 2021, 11.2 (см. olymp.itmo.ru)

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

$3000= 23 ⋅3 ⋅53$ , то есть нас интересуют числа, деляющиеся на $2,3$ или $5.$ Найдём сначала количество таких чисел. Для этого воспользуемся принципом включений и исключений. Чётных чисел от $1$ до $3000$ ровно $3000 2 = 1500$ , кратных трём — $3000 3 =1000$ , кратных пяти — $3000 5 =600$ . Однако, если просто сложить числа 1500,1000 и 600 , мы посчитаем некоторые числа 2 раза, а именно, числа, делящиеся на $2⋅3= 6,2⋅5= 10$ и $3⋅5= 15$ , поэтому из полученной суммы надо вычесть $3000 6 =$ $3000 500,10 = 300$ и $3000 15 = 200$ . Однако, $1500+1000+ 600− 500− 300− 200=2100$ всё ещё неправильный ответ, Поскольку в этом выражение числа, имеющие все три простых множителя, сначала считаются три раза, а потом их количество вычитается опять же три раза, поэтому надо снова добавить эти числа. Количество таких чисел $3000 − 2⋅3⋅5 =100$ , значит, количество чисел, имеющих с $3000$ общие делители и не превосходящих его, это $2200.$

Заметим теперь, что если какое-то число $x$ имеет с числом $N$ общие делители, то число $N − x$ тоже имеет с $N$ те же самые общие делители. Значит, все интересующие нас числа, кроме чисел $1500$ и $3000,$ разбиваются на пары с суммой $3000$ (числу 3000 в пару пришлось бы сопоставить $0,$ а числу $1500−$ само себя). Таких пар получаается $1099,$ поэтому итоговый ответ $1099⋅3000+ 3000+ 1500 =$ $1100⋅3000+ 1500 =3301500.$

Замечание.

Числа, меньшие $3000$ и взаимно простые с ним разбиваются на пары таким же образом, поэтому участники, знакомые с функцией Эйлера, могли получить формулу для ответа в виде

N(N +-1)−-N ⋅φ(N). 2

Ответ:

$3301500$

Курсы

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

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

Задача 7#77773

Докажите, что число $33n+ 173n +313n$ при нечётном $n$ раскладывается в произведение хотя бы четырёх (не обязательно различных) натуральных чисел, больших единицы.

Источники: ИТМО - 2020, 11.1 (см. olymp.itmo.ru)

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

$3+ 31= 34$ делится на $17,$ а значит то же самое выполняется и для суммы любых нечётных степеней. Это верно, т.к. $am + bm$ на $a+ b$ при нечётном $m.$ По-другому можно это доказать так: $31≡ −3(mod 17),$ значит $3n 3n 3n 31 ≡ (−3) ≡ −3 ,$ т.к. $3n$ нечётно.

Теперь рассмотрим остатки по модулю $9.$ $3n 3$ делится на $9.$ $17$ в нечётной степени даёт при делении на $9$ остаток $8$ , а в чётной - остаток $1.$ Число $3 31$ даёт остаток $1$ при делении на $9,$ а значит и любая нечётная степень куба даёт такой же остаток. Таким образом, сумма $3n 3n 3n 3 + 17 + 31$ делится на $9.$

Мы получили уже три множителя: $3,3 и 17.$ Кроме того $3n 3n 3n 3 + 17 + 31 >3⋅3⋅17= 153,$ поэтому есть хотя бы ещё один делитель.

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

Задача 8#79995

Девочка Катя не любит число $239.$ Она выписала несколько различных чисел, ни одно из которых не содержит последовательность цифр $239$ (подряд и именно в таком порядке). Докажите, что сумма обратных к этим числам не больше $30000.$

Источники: ИТМО 2019

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

Количество подходящих $3n+ 1$ -значных чисел не больше, чем $9 ⋅999n :9$ вариантов для первой цифры и не более 999 вариантов для каждой следующей тройки цифр. Каждое из них не меньше $3n 10 .$