Monday, October 30, 2006

Занимательная задача: тестирование приборов

Есть множество приборов, часть которых исправна, а часть неисправна. Приборы умеют тестировать друг друга. Для тестирования приборы подключаются друг к другу и каждый сообщает про другого, исправен ли тот. При этом исправный прибор всегда верно диагностирует любой другой прибор, а неисправный выдает произвольный результат: иногда он выдаст верный диагноз, а иногда неверный. Задача:
  1. При условии, что исправных приборов больше половины, установить, какие приборы верные.
  2. Доказать, что если исправных приборов половина или меньше, то невозможно определить, какие приборы верные.

Задача рассказана мне Г.М. Фельдманом.

Post a Comment