На доске записано некоторое натуральное число N. Учитель по очереди вызывает учеников, которые выполняют с любым из уже записанных на доске чисел одно из следующих действий: — умножать число на 4; — прибавить к числу 12; — если число не равно 6, то вычеркнуть из числа цифру 6. Затем каждый из учеников записывает новое число на доску. а) Можно ли за несколько действий получить из числа 34 число 1? б) Можно ли за несколько действий получить из числа 35 число 60? в) Какое наибольшее количество чисел, меньших 2000, может быть записано на доске, если N = 1?

а) Да, из числа 34 можно получить число 1 следующим образом: 34 46 4 16 1. б) Заметим, что при выполнении каждой из операций новое число имеет тот же остаток при делении на 3, что и предыдущее. Умножение на 4 не меняет остаток, так как 4 сравнимо с 1 по модулю 3. Прибавление 12 не меняет остаток, так как 12 делится на 3, то есть имеет остаток 0. Вычеркивание цифры 6 также не меняет остаток, так как при выполнении этой операции из числа вида 10a + 6 (где a — натуральное число, не равное 0) получается число a. По признаку равноостаточности при делении на 3 (сумма цифр числа будет иметь тот же остаток, что и само число) числа 10a + 6 и a имеют одинаковый остаток при делении на 3. Таким образом, у всех чисел, которые можно будет получить на доске, остаток при делении на 3 будет одинаковым. Но число 35 имеет остаток 2 при делении на 3, а число 60 — остаток 0. Противоречие. в) Из пункта б) мы видим, что можно получить только числа с тем же остатком при делении на 3. Среди чисел от 1 до 1999 ровно 667 чисел имеют остаток 1 при делении на 3. Покажем, что мы можем получить все числа с остатком 1 при делении на 3: 1 13 52 64 4; 64 76 7; 4 16 28 40 160 10. Таким образом, при помощи прибавления 12 можем получить любые числа вида 1 + 12k; 4 + 12k; 7 + 12k; 10 + 12k, k in N. При этом эти виды задают все числа вида 1 + 3n, где k in N. Так как n — натуральное число, то оно может иметь остаток 0, 1, 2 или 3 при делении на 4, то есть имеет вид 4k; 4k + 1; 4k + 2 или 4k + 3, k in N. Значит, нужно получить числа вида 1 + 3n = 1 + 3(4k) = 1 + 12k; 1 + 3n = 1 + 3(4k + 1) = 1 + 12k + 3 = 4 + 12k; 1 + 3n = 1 + 3(4k + 2) = 1 + 12k + 6 = 7 + 12k; 1 + 3n = 1 + 3(4k + 3) = 1 + 12k + 9 = 10 + 12k. Именно это мы и доказали. Значит, все числа от 1 до 1999, имеющие остаток 1 при делении на 3, мы можем получить. Таких чисел [(1999)/(3)] = 667, где [x] — целая часть x, то есть наибольшее целое, не превышающее x. Ответ: 667.

а) Да, можно; б) Нет, нельзя; в) 667