Эту задачу я придумал давным-давно, когда пытался формализовать задачу о передаче информации по каналу с помехами. Итак.
Господин Вход, господин Выход и Чертик и Канал.
Вход собирается передать Выходу N бит информации.
Для этого у него есть Канал, по которому можно послать Пакет — число от 0 до X-1.
Каждый раз, когда вход посылает число, чертик прибавляет к нему свое — от 0 до Y-1.
Чертик может прибавить любое число на свой выбор, но он не знает, какие числа посылаются или посвылались.
До сеанса связи Вход и Выход догавариваются о том, каким образом Вход будет передавать информацию. Чертик подслушивает разговор и знает, как они собираются это делать.
С того момента, когда Вход узнает информацию, которую нужно передать, Вход и Выход не могут никак общаться иначе как по Каналу.
Вопрос.
1. Передать за фиксированное число посылок информацию фиксированного размера с максимальной достоверностью. Т.е. Выход должен назвать N бит с минимальной вероятностью ошибки по всему набору вцелом.
2. Передать фиксированное число бит за наименьшее гарантированное и/или матожидаемое число пакетов.
3. То же, в случаях, когда чертик знает , что передавалось в пакетах, предшествующих данному.
