Задача 78778

Тема:    [ Двоичная система счисления ]

Сложность: 3+ Классы: 10

Условие

Доказать, что среди чисел [2^k · ] бесконечно много составных.

Решение

Покажем, что среди таких чисел бесконечно много чётных.
Заметим, что k-я цифра двоичного разложения числа равна 1, если число [2^k] нечётно, и равна 0, если это число чётно. Если среди чисел [2^k] конечное число чётных, то начиная с какого-то места в двоичной записи числа встречаются только единицы. Тогда оно представимо в виде двоичной дроби, а значит, рационально. Получили противоречие.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	34
Год	1971
вариант
Класс	9
Тур	1
задача
Номер	5