четверг, 26 февраля 2015 г.

Точное время

Каждая цифра на электронных часах появляется на позиции, которая состоит из семи сегментов. То есть всего на таких часах 28 сегментов. Примеры показаний показаны на рисунке. При каком максимальном количестве неработающих сегментов можно будет однозначно определить точное время?
Часы
update
Первый - Илья.
Ответ
Испорченными могут быть 13 сегментов.

3 комментария:

  1. Занумеруем сегменты сверху вниз, слева направо, примерно так:
    1
    23
    4
    56
    7

    Первая цифра может быть от 0 до 2, т.е. нужно минимум два бита. Легко убедиться, что двух достаточно, например 2й и 4й (только 2й означает 0, только 4й - 2, и если ни один не горит, то 1).
    Со второй и последней цифрой тоже всё понятно. Там нужно различать цифры от 0 до 9, т.е. по идее было бы достаточно 4 бит, но из-за специфики кодировки меньше чем пятью не обойтись.
    Действительно, нам обязательно нужен 1й (иначе не отличить 1 от 7), 2й (отличать 3 от 9), 3й (6 от 8), 4й (0 от 8) и 5й (8 от 9). Непосредственной проверкой убеждаемся, что этих пяти сегментов достаточно.

    Осталось разобраться с третьей цифрой, где может быть значение от 0 до 5. Меньше чем тремя битами не обойтись. С другой стороны, 3х достаточно: 1й-2й-5й однозначно определяют цифру от 0 до 5.

    Итого, можно испортить 5+2+4+2=13 сегментов из 28.

    ОтветитьУдалить
    Ответы
    1. Правильно! 13 неработающих сегментов не помешают определить точное время.

      Удалить
    2. Жалко, что для третьей цифры трех сегментов достаточно. :)
      Я уже почти доказал, что нужно четыре, когда заметил ошибку :)
      А само доказательство не такое тривиальное было бы, если бы оно было правильным :)

      Любопытно, существуют ли какие-нибудь общие алгоритмы определения избыточности кодирования.

      Удалить