Задача 79551

Темы:    [ Последовательности (прочее) ] [ Примеры и контрпримеры. Конструкции ] [ Разбиения на пары и группы; биекции ] [ Десятичная система счисления ]

Сложность: 3+ Классы: 7,8,9

Условие

Подмножество X множества "двузначных" чисел 00, 01, ..., 98, 99 таково, что в любой бесконечной последовательности цифр найдутся две цифры, стоящие рядом и образующие число из X. Какое наименьшее количество чисел может содержаться в X?

Решение

Так как в последовательности цифр n, m, n, m,..., n, m, ... найдутся две цифры, стоящие рядом и образующие число из X, то для любых двух цифр n и m либо число содержится в X, либо число содержится в X. В частности, при n = m получаем, что все числа вида содержится в X. Следовательно, в X не менее, чем 10 + (100 − 10)/2 = 55 чисел.
Осталось доказать, что существует множество из 55 элементов, удовлетворяющее условию задачи. Подходит, например, множество X = {  | m ≤ n}. Действительно, если в бесконечной последовательности цифр не найдутся две подряд идущие цифры, из которых первая не больше второй, то цифры в этой последовательности строго убывают, что невозможно.

Ответ

55.00

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	52
Год	1989
вариант
Класс	8
задача
Номер	4