СПбГУ 2025, 10–11 классы, задача 11

Сложная
Теория чисел
Источник:
Олимпиады школьников СПбГУ, Отборочный этап, 2025, 10–11 классы

( баллов) На доске написано число . Один ход состоит в том, что к числителю и знаменателю дроби прибавляется по , после чего дробь сокращают (конечно, если она сократима). Может ли второе сокращение произойти ровно на -м ходу?

Верно или неверно?

Войдите, чтобы проверять ответы
Ответ

Ответ: Нет.

Решение. Пусть дробь впервые сократилась на -ом шаге. Это значит, что и имеют общий делитель . Но тогда и имеет делитель . Очевидно, подойдёт , где — наименьший простой делитель числа . Так как на -ом шаге числитель и знаменатель будут иметь общий делитель, а на всех предыдущих — нет.

Заметим, что после сокращения дробь будет иметь числитель и знаменатель , поэтому можно аналогично доказать, что следующее сокращение будет на шаге , где — наименьший простой делитель .

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

1

Верное решение

40
Максимум: 40

Похожие задачи

СПбГУ 2026, 10-11 классы, задача 7

(40 баллов) Существует ли такое натуральное число n, что число (6n)!-3n+1 является квадратом целого числа?
Сложная
Теория чисел

СПбГУ 2022, 8–9 классы, задача 11

(40 баллов) Числа от 1 до 600 разбиты на несколько групп. Известно, что если в группе более одного числа, то сумма любых двух чисел из этой группы делится на 6. Какое наименьшее количество групп может быть?
Сложная
Теория чисел
Комбинаторика

СПбГУ 2022, 10–11 классы, задача 11

(40 баллов) Назовём хвостом натурального числа любое число, которое получается из него отбрасыванием одной или нескольких первых цифр. Например, 234, 34 и 4 — хвосты числа 1234. Существует ли шестизначное число без нулей в десятичной записи, которое делится на каждый из своих хвостов?
Сложная
Теория чисел

СПбГУ 2026, 10-11 классы, задача 8

(40 баллов) В ячейках таблицы 19 × 19 расставлены натуральные числа. Оказалось, что сумма чисел в любых двух соседних по стороне ячейках равна 29 или 30. Посчитаем сумму чисел в каждой строке и каждом столбце. Могут ли все эти 38 сумм быть попарно различны?
Сложная
Теория чисел
Комбинаторика