Тема КФУ (олимпиада Казанского Федерального Университета)

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

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

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

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

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

Подтемы раздела кфу (олимпиада казанского федерального университета)

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

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

Задача 1#103995

Пусть $a =√0,99...99$ (2024 девятки). Какова в этом числе:

а) 2024-ая;

б) 2025-ая

цифра после запятой?

Источники: КФУ - 2025, 11.2 (см. malun.kpfu.ru)

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

Подсказка 1

Мы знаем, что 0,9 = 1 - 10⁻¹, тогда наше подкоренное выражение можем записать как 1 - 10⁻²⁰²⁴. Хочется как-то ограничить a, попробуем ограничить через связь с (- 10⁻²⁰²⁴) = x, то есть, хотим получить f(x) < √(1+x) < g(x). Ведь в таком случае мы сможем что-то сказать о 2024-й и 2025-й цифре после запятой!

Подсказка 2

Так как значение под корнем меньше 1, то 1 + x < √(1+x) < 1, но нужна более точная оценка. Поможет, например, возведение в квадрат или деление.

Подсказка 3

Попробуем ограничить снизу 1+x/2 -x²/8, а сверху 1+ x/2, после доказательства сможем получить сразу и 2024-ую цифру, и 2025-ую!

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

$a =√1-− 10−2024.$ Обозначим $x= −10−2024.$ Докажем, что

x x2 √---- x 1+ 2 − 8 < 1 +x <1+ 2

Это неравенство из-за области значений $x$ эквивалентно возведённому в квадрат:

x2 x4 x2 x3 x2 1 +-4 + 64-+x − 4-− 8-< 1+ x< 1+x + 4-

Теперь правое неравенство очевидно в силу $2 0< x4-$ , а левое тоже в силу $4 3 x64 < x8 .$

Тогда получаем, что

−4048 1 − 5⋅10−2025− 10---< a< 1− 5⋅10− 2025 8

1− 6⋅10−2025 < a< 1− 5⋅10− 2025

a =0,9◟9..◝.◜99◞+4⋅10−2025+ 𝜀, 2024

где $−2025 𝜀 <10 .$

Ответ:

а) 9;

б) 4

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

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

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

Задача 2#83854

Найти трехзначное число, которое в 9-ричной системе счисления записывается теми же цифрами, но в обратном порядке.

Источники: КФУ - 2024, 11.1 (см. malun.kpfu.ru)

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

Подсказка 1

Запишем искомое число в виде 100а+10b+c. Как нам схожим образом записать это число в девятеричной системе?

Подсказка 2

Верно, 81c+9b+a. Приравняем эти выражения и получим уравнение на три неизвестных. Найти и выразить их из него мы не сможем, но можем выявить некоторые характеристики этих чисел. Например, о равенстве каких-то двух переменных. Как бы нам переписать это уравнение так, чтобы какая-нибудь разница равнялась нулю?

Подсказка 3

Конечно, записав 100а-80b =a-b, получим, что разница a и b кратна 10, но так как обе переменные однозначны, то и их разность равна только нулю. Тогда а=b. Подставив в известное нам равенство и пользуясь однозначностью чисел, можем так же точно определить значения наших переменных

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

Пусть искомое число записано цифрами $a,b,c,$ то есть

--- n= abc= 100a+10b+ c

Запишем условие задачи:

100a +10b+ c=81c+ 9b +a

99a+ b− 80c= 0

Перепишем это равенство в виде:

100a− 80c= a− b

Левая часть делится на 10, значит $a− b$ также делится на 10. В силу того, что $a$ и $b$ — однозначные числа, эта разность может быть равна только 0, т.е. $b= a.$ Подставив в полученное ранее равенство, получим

100a= 80c, 5a= 4c

Итак, возможен только один вариант: $c=5,$ $a =b= 4.$

Ответ: 445

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

Задача 3#83856

Выписаны 100 положительных чисел, сумма которых равна $S,$ а сумма квадратов больше, чем $P.$ Доказать, что среди этих чисел есть число, большее, чем $P∕S.$

Источники: КФУ - 2024, 11.3 (см. malun.kpfu.ru)

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

Подсказка 1

Пусть х₁ - наибольшее из чисел. Тогда очевидно х₁>P/S. С таким выражением работать куда проще, чем с абстрактным условием на неизвестное число. Перезапишем его в виде Sx₁>P. Как бы нам доказать это неравенство?...

Подсказка 2

Давайте домножим выражение для суммы всех чисел на х₁. Попарного сравним каждое слагаемое со слагаемыми из суммы квадратов. Что получается?

Подсказка 3

Верно, Sx₁ оказывается не меньше суммы квадратов! А теперь можно заменить всё на введённые в условии обозначения и доказать неравенство.

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

Расположим наши числа по убыванию, $x ≥ x ≥ x ≥...≥x . 1 2 3 100$ Имеем

S = x1+ x2+x3 +...+ x100

x2+x2 +x2+ ...+ x2 > P 1 2 3 100

Умножим первое равенство на $x1,$ получим, что

Sx1 = x2+x1x2+ x1x3+ ...+ x1x100 ≥ x2+ x2 +x2+ ...+ x2 > P 1 1 2 3 100

Следовательно, $x1 > P. S$

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

Задача 4#76417

Пусть $p$ — нечётное простое число. Найдите все целые $x$ и $y$ такие, что

3 3 3 2 2 x + y + p =x y+ xy

Источники: КФУ-2022, 11.1 (см. kpfu.ru)

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

Подсказка 1

Такс, нам говорят, что p простое. Это очень сильное условие, поэтому давайте попробуем перенести p в правую часть, а всё остальное в левую! И после этого попробуем левую часть разложить на множители.

Подсказка 2

Да, она раскладывается не так уж и легко. Так что, попробуйте вынести (x+y), а дальше подобрать не так сложно)

Подсказка 3

В итоге, должно получиться равенство (x+y)(x-y) ² = -p³. А теперь нам сильно помогает условие на простоту p, ведь мы теперь точно понимаем, чему может равняться каждая из скобок! Всего два случая, в первом квадрат это ±p, а во втором ±1. Осталось решить каждый из случаев

Подсказка 4

Верно, для того, чтобы решить каждую систему, достаточно просто сложить или вычесть её уравнения!

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

Перепишем уравнение в виде $x3 +y3− x2y− xy2 = −p3$ и разложим левую часть на множители:

( 2 2) 3 (x +y) x − xy+ y − (x+ y)xy =− p

2 3 (x+ y)(x− y) = −p

Таким образом, числа $x+y$ и $(x− y)2$ являются степенями простого числа $p$ . Но $(x − y)2$ — чётная степень $p,$ значит, множитель $x +y$ — это нечётная степень $p,$ и так как $x+ y ≤ 0,$ то

{ x+ y = −p { x+ y = −p3 x− y = ±p или x− y = ±1

В первом случае имеем

x= 0,y =− p или x =−p,y = 0,

Во втором

− x= − 1 (p3− 1),y =− 1(p3+ 1) или x= − 1(p3+1),y = − 1 (p3− 1) 2 2 2 2

Так как $p$ — нечётное, то числа $x$ и $y$ в этих наборах — целые.

Ответ:

$(0;− p),(−p;0),(− 1 (p3− 1);− 1(p3+1)),(− 1(p3+1);− 1(p3− 1)) 2 2 2 2$

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

Задача 5#76418

Сумма нескольких натуральных чисел, в записи каждого из которых участвуют только цифры $3$ и $0,$ равна $777...77$ ( $2022$ семёрки). Какое наименьшее число слагаемых может быть в этой сумме?

Источники: КФУ-2022, 11.3 (см. kpfu.ru)

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

Подсказка 1

Может нам как-нибудь немного упростить себе задачу? Например, упростив сумму чисел. Число с 2022 одинаковыми цифрами должно делиться на 3, тогда составим уравнение, где сумма n чисел равна 77...7 и поделим обе части

Подсказка 2

В новом уравнении каждое из чисел сумме в 3 раза меньше соответствующего элемента из первого уравнения, то есть все числа состоят из единиц и нулей и в сумме дают 259259...259. Как могла получится девятка в таком числе?

Подсказка 3

Верно, эти девятки говорят о том, что число получалось из суммы как минимум 9 чисел (при меньшем количестве суммы единиц не могло бы хватить). Остаётся только подобрать подходящий пример)

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

Пусть $M = 777...77= a +a + ...+ a , 1 2 n$ где числа $a k$ записываются только нулями и тройками. Сумма цифр числа $M$ равна $2022⋅7$ и делится на $3.$ Тогда

1 3M = 25◟9259◝◜...259◞= c1+ c2+...+cn, 2022цифры

где числа $ck = 1ak 3$ записываются только нулями и единицами. Поскольку $1M 3$ содержит девятку, наименьшее количество слагаемых в этой сумме равно $9.$ Эти слагаемые легко находятся для числа $259:259 =2 ⋅111+ 3⋅11+4 ⋅1.$ Умножая на три, получим: $777= 2⋅333 +3⋅33+ 4⋅3.$ Умножая на степени 1000 и складывая, получим

77◟72.◝0.◜22.77◞= 2⋅3◟332.◝0..◜22333◞+3⋅3◟30332.◝◜02.1.033◞+4 ⋅3◟0032.◝◜02..0003◞

Ответ: 9

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

Задача 6#94246

Даны три целых числа. Из первого числа вычли сумму цифр второго числа, из второго вычли сумму цифр третьего, а из третьего вычли сумму цифр первого числа. Могут ли эти разности равняться соответственно

a) $2,3,4$ ?

б) $3,4,5$ ?

Источники: КФУ - 2021, 11.1 (см. malun.kpfu.ru)

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

Подсказка 1

Давайте подумаем даже не про пункты, а про общую идею задачи. Если мы хотим доказывать, что ответ — "да", то надо бы придумывать пример. Пример хотелось бы строить простой, а если числа хотя бы двузначные, то уже суммы цифр какие-то надо считать. Не годится. Поэтому если в каком-то пункте ответ "да", то надо попробовать привести пример с цифрами. Если же ответ — "нет", то первое, что можно сделать с суммой цифр — использовать равноостаточность числа и его суммы цифр по какому-то хорошему модулю.

Подсказка 2

Действительно, в первом пункте легко придумывается пример, а во втором пункте можно использовать факт, что разность числа и его суммы цифр всегда кратна 9. Но вот незадача, вычитаем-то мы не собственную сумму цифр, а сумму цифр числа, следующего по циклу. Что нам нужно сделать с результатами этих разностей, чтобы получить разности числа и его суммы цифр?

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

a) Например, подходят числа $10,8,5$ . Тогда соответствующие разности равны $10 − 8= 2$ , $8− 5= 3,5− 1= 4$ .

б) Пусть $a,b,c$ — исходные числа. Обозначим через $S(n)$ сумму цифр числа $n$ . По признаку делимости на 9 числа $n$ и $S(n)$ имеют равные остатки при делении на 9 , и значит, разность $n− S(n)$ кратна 9.

По условию разности $a− S(b),b− S(c),c− S(a)$ равны числам $3,4,5$ соответственно. Тогда их сумма

(a− S(b))+(b− S(c))+(c− S(a))= (a− S(a))+ (b − S(b))+ (c− S(c))

должна делиться на 9 . С другой стороны, эта сумма равна $3+4 +5= 12$ и на 9 не делится, противоречие.

Ответ:

а) да

б) нет

Курсы

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

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

Задача 7#94247

Натуральное число $n$ назовём удачным, если его можно единственным образом разбить в сумму 10 различных натуральных чисел (порядок слагаемых не важен). Найдите все удачные числа.

Источники: КФУ - 2021, 11.3 (см. malun.kpfu.ru)

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

Подсказка 1

Если у нас число представляется единственным образом, то это значит, например, что мы не можем как-то уменьшить одно число на 1, увеличить другое на 1 и получить новое разбиение. Положим, что у нас есть числа a₁ < a₂ < … < a₁₀, что тогда можно сказать, в соответствии с нашими рассуждениями выше, об a₁? Перекладывается ли это на a₂?

Подсказка 2

Мы можем сказать, что a₁ = 1, так как если a₁ > 1, то выходит, что мы можем уменьшить на 1 a₁, увеличить на 1 a₁₀, и это будет новым разбиением. Но ведь аналогично можно рассуждать и относительно a₂, a₃, … Когда этот процесс должен закончиться?

Подсказка 3

Мы можем проводить такие рассуждения вплоть до a₉, но вот с a₁₀ так же не получится. Подумайте, может ли a₁₀ быть равен, скажем, 100? А 20? А какие тогда он может принимать значения и почему (рассуждайте похожим образом, как с остальными a_i)?

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

Пусть число $n$ — удачное, $n =a + a + ...+a 1 2 10$ , где $a < a <...<a 1 2 10$ — натуральные слагаемые. Если предположить, что $a >1 1$ , то $n$ можно разбить в сумму различных натуральных слагаемых еще одним способом:

n =(a1− 1)+ a2+ ...+(a10+1)

Таким образом, $a1 = 1$ .

Далее, если предположить, что $a >2 2$ , то для $n$ опять можно привести другое разбиение:

n =a1+ (a2− 1)+ a3+...+(a10 +1)

Значит, $a2 =2$ . Продолжая так далее, получаем $a3 = 3$ , $a4 = 4,...,a9 = 9$ . Если $a10 >11$ , то $a9+ 1< a10− 1$ , и снова можно сконструировать другое разбиение.

Наконец, нетрудно видеть, что при $a10 = 10$ или $a10 = 11$ получающиеся числа 55 и 56 являются удачными.

Ответ: 55 и 56

Интенсивы

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