Разбор самой простой задачи международной олимпиады по математике

Всем привет! С вами Георгий Вольсон. Это летний дачный выпуск реальной математики на канале Кверцу. Но пока мы с вами, многие, по крайней мере, отдыхаем, некоторые работают не покладая рук и шариковых ручек.

Буквально недавно прошла международная олимпиада школьников по математике. Наши ребята, шестеро бойцов, представляли сборную России. При этом сама Олимпиада проходила в Японии, но наши писали из Владивостока дистанционно, и результаты получились очень приличными. Пять человек получили золотые медали: это Александр Гнусов, Алиса Волкова, Ратибор Коптилин, Роман Кузнецов и Ильдар Химутдинов. А также Павел Прозоров получил серебро.

В неофициальном командном зачёте, когда складываются результаты всех учеников, мы заняли четвертое место после сборных Китая, Южной Кореи и США. Можно было бы, если не считать США, сказать, что это триумф Восточной школы математики. Но если посмотреть на сборную США, вы увидите, что, таки да, даже её восточная школа доминирует.

Но интересно, что многие, даже близкие к математике, преподавания математики люди считают: "О Боже мой, как так? У нас серебро, это же так плохо! Все должны получать только золотые медали!" Наши ученики... Люди просто не понимают, какого уровня задачи предлагаются на Международной олимпиаде.

Вообще регламент там такой, что есть два дня, каждый день по три задачи, и за каждую задачу максимум можно получить по 7 баллов, общий максимум — 42 балла. Так вот, сегодня мы попробуем разобрать одну самую простую первую задачку, и на примере этой задачи мы поймем, насколько все-таки нетривиальной является международная олимпиада. Я думаю, в этом случае мы и серебро будем ценить более чем заслуженно.

Прежде чем мы приступим к решению этой задачи, даже до этого, мне придется сделать кое-какие пояснения. Во-первых, натуральные числа — что это такое? Это числа, которые у нас получаются при счёте: 1, 2, 3, 4 и так далее. Простые числа и составные числа. Напомню, что простым числом называют такое число, у которого ровно 2 натуральных делителя, то есть оно само и единица.

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