Home » Работа и карьера » Тесты при приеме на работу в ABBYY Software – Ответы 1

Тесты при приеме на работу в ABBYY Software – Ответы 1

Как и обещал, привожу ответ на первую задачу.

1. Царь построил своих чиновников в колонну (лицом к затылку следующего), надел по колпаку одного из цветов — красного или белого.. и сказал поочереди назвать цвет своего колпака. Кто не угадает — смерть. Первый отвечал тот кто видит всех и т.д. попорядку.. Вопрос: о чем должны договориться чиновники чтобы минимизировать кол-во смертей.

Исходим из предположения, что колпаки одеты случайным образом, а колонна достаточно длинная.

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

Если каждый нечетный по счету чиновник (1-й, 3-й, 5-й и т.д.) будет называть цвет колпака, находящегося перед ним, а каждый четный повторять названный цвет, то выживут все четные чиновники и половина нечетных. Это становится легко понятным если расписать возможные комбинации пар (Б – белый, К – красный):

БК – 1-й убит
ББ – 1-й жив
КК – 1-й жив
КБ – 1-й убит

Т.е. выживут 75% чиновников.

Обновлено: это решение оказалось не оптимальным, вот более правильное решение.