Задача №1419

Автор: А. Н. Журинский

Условие

Чтобы проводить сортировку писем автоматически, Министерство связи ввело специальные индексы, которые состоят из цифр, имеющих вполне определённое начертание. В состав каждой цифры могут входить отрезки девяти типов:

Представьте себе, что машина «опознаёт» цифры, совершая ряд проверок. При каждой проверке определяется, есть ли в начертании цифры какой-то один отрезок; результатом каждой проверки является ответ «да» или «нет». После k проверок каждой цифре будет приписана цепочка из k ответов, например: «да-нет-нет-...» (В определённой последовательности для всех цифр проверяются одни и те же k отрезков, и для каждой цифры должны быть проверены все k отрезков.). Будем говорить, что цифры «опознаются» за k проверок, если в результате k проверок цепочки ответов оказываются у всех цифр различными.

Задание 1. Каково минимальное число проверок, необходимое для опознания 10 цифр в принятом для них начертании?

Задание 2. Определите минимальное число проверок, которое потребовалось бы для 10 цифр в случае, если бы цифры 2, 3, 6 и 9 имели следующие начертания:

Решение

Комментарии