Skip to main content
OlympiadHQ

Browse · MathNet

Print

Ukrainian Mathematical Olympiad

Ukraine algebra

Problem

A positive integer is written on a blackboard. Each minute Andrew looks at his clock and adds the number of minutes the clock is showing (an integer between and ) to the number written on the blackboard.

a) Prove that at some moment a composite number will be written on the blackboard.

b) Will necessarily a number divisible by be written?
Solution
a) У першому, третьому, п'ятому і т.д. записаних числах буде чергуватись парність (адже сума двох послідовних кількостей хвилин непарна). Отже, серед них будуть парні числа. При цьому лише перше з них може дорівнювати (отримане як або ), наступні парні числа будуть більшими за , а тому складеними.

б) Не обов'язково. Якщо на дошці написано число , а перша побачена Андрієм кількість хвилин дорівнює , то остачі записаних чисел від ділення на будуть періодично повторюватись: , , , , , , , , , , .... Серед цих остач не буде остачі .
Final answer
No

Techniques

IntegersPrime numbersOther