Почтовая задача

[Overseer]

Как-то с братом сидели за решением лабораторной работы и придумали такую задачу:

всем нам известен шрифт почтового индекса РФ:


из выше-описанных символов будет учитывать лишь цифровые:  0..9

Каждая цифра задана сочетанием 9 черточек, закрашенных или не закрашенных.
Но мы можем определить цифру по гораздо более меньшему количеству этих черточек: так, например, если мы имеем нижнюю диагональную черточку, мы знаем, что это цифра 2,3 либо 9. Если у нас также есть незакрашенная центральная черточка (горизонтальная), то мы точно знаем, что имеем 2. Значит мы можем определить цифру 2 по маске, содержащей 2 черточки (нижнюю диагональную и центральную вертикальную)

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

Внимание, вопрос: что это за количество, сколько вариантов масок с этим количеством черточек существует и что это за маски?

[Overseer]

upd.

[Um_nik]

Из 5 черточек получилось =)

[Overseer]

напомню, что необходимо доказать, что количество черточек минимально, найти все возможные варианты и доказать, что больше их нет (:

[Um_nik]

Я просто делюсь мыслями

[☭-Изделие 20Д]

Показать скрытый текст

Наверное - 3
Вообще то хватило бы - 2 - верх.+ нижн.диагонали, но ещё одна нужна отличить 1 от 7
Всё таки -4
0 -1
1 - 3
2 - 7+9
3 - 3+7
4 - ничего
5 - 1+9
6 - 3+9
7 - 1+3
8 - 7+1
0 - 3+9 правда коряво для запоминания
Используются 1, 3, 7, 9
 

[Леший]

Забавно, по-моему первый шаг очевиден 

[Overseer]

предлагаю ввести единую систему, чтобы легче было обозначать черточки:

===1===
||            ||
2     3     4
||            ||
===5===
||            ||
6     7     8
||            ||
===9===

[Overseer]

* Overseer наверное уже задолбал, но:

Показать скрытый текст

ИСПОЛЬЗУЕМ СПОЙЛЕРЫ!!!

[VVV]

  Достаточно четырех. Очевидно, что трех не хватит, т.к. 2^3<10. Сравнивая 0 и 8, получим, что есть "5" (по системе Overseer'а). Сравнивая 5 и 8, получим, что есть или "4", или "6". После небольшого перебора получим 5 вариантов: 1) "1457", 2) "1458", 3) "4568", 4) "4567", 5) "4579".

[Um_nik]

* Overseer наверное уже задолбал, но:

Вместе с Виталиком

[Overseer]

  Достаточно четырех. Очевидно, что трех не хватит, т.к. 2^3<10. Сравнивая 0 и 8, получим, что есть "5" (по системе Overseer'а). Сравнивая 5 и 8, получим, что есть или "4", или "6". После небольшого перебора получим 5 вариантов: 1) "1457", 2) "1458", 3) "4568", 4) "4567", 5) "4579".

5 вариант - неверен. 5 и 6 неразличимы. А так все супер: именно такого решения я и ждал

[Леший]

Очередное "спасибо Вилли"

[Les]

Очередное "спасибо Вилли"

[Overseer]

Виталик, может стоит кинуть всю Назву под хайд программкой Гийомчика? (:


З.Ы. ну кроме меня