Maths Olympiad Prep

Library / /38 of 61

Algebra Difficulty 5.9 AIME, harder Prove it Ukraine

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 00 and 5959) 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 55 be written?

Solution

a) У першому, третьому, п'ятому і т.д. записаних числах буде чергуватись парність (адже сума двох послідовних кількостей хвилин непарна). Отже, серед них будуть парні числа. При цьому лише перше з них може дорівнювати 22 (отримане як 2+02 + 0 або 1+11 + 1), наступні парні числа будуть більшими за 22, а тому складеними.

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.