Генералы и голуби.

[Шшок]

Поскольку все имеют возможность прочитать написанный Чивой ответ, я все-таки осмелюсь привести его крупными буквами и указать на принципиальную (ИМХО) ошибку в этом решении.

Итак:

Допустим, решение существует. И именно N - минимальное количество пролетов голубя, которых будет достаточно, чтобы генералы были абсолютно уверены, что они поняли друг друга и договорились.

Но тогда получается, что генералу, отправившего голубя в последний, N-ный полет, совершенно безразлично, долетит он до адресата или нет. Ведь он не ждет подтверждения. Значит, этот последний, N-ный полет голубя вообще не нужен во всей ситуации, если не важно, получит его другой генерал или нет. Значит, этого последнего голубя можно было и не посылать вообще. А соответственно, для успешного завершения компании хватило бы и N-1 - го пролета голубя. Но мы же объявили, что N - это минимальное необходимое количество пролетов. Мы пришли к противоречию. Следовательно, исходное предположение (о возможности договоренности у этих параноиков) - неверно. Финиш


В этом решении есть серьезнейшая логическая ошибка:

Но тогда получается, что генералу, отправившего голубя в последний, N-ный полет, совершенно безразлично, долетит он до адресата или нет. Ведь он не ждет подтверждения.

Ошибка именно здесь. То, что он не ждет подтверждения, означает, что не нужно именно подтверждение, т. е N+1-е сообщение. Из того, что он не ждет подтверждения, вовсе не следует , что последнее N-е сообщение не нужно. Оно не просто нужно. Оно совершенно необходимо. Правда, точно так же необходимо, чтобы оно дошло до адресата (БЕЗ ПОСЛЕДУЮЩЕГО ПОДТВЕРЖДЕНИЯ!!!). Ведь вопрос задачи заключается в том, сколько первых сообщений должно ГАРАНТИРОВАННО дойти до адресатов, то есть где можно оборвать цепочку "я знаю, что ты знаешь, что я знаю....."

А теперь давайте порассуждаем.

1-й генерал пишет: Наступаем в 9 вечера.
2-й генерал пишет: Понял. Наступаем в 9 вечера.

На этой стадии обоим генералам известно время наступления. При этом 1-й уже ТОЧНО знает, что 2-му известно время наступления.

1-й генерал пишет: Ваше сообщение получил и понял.

И если 2-й получит это сообщение, то на этой стадии практически уже все согласовано! Ведь теперь оба знают, что наступление в 9 часов, и оба знают, что их партнер осведомлен об этом.
Теперь 2-й отсылает уведомление о том, что он получил это сообщение, и уже не ждет никакого ответа. Ему этот ответ просто-напросто не нужен. Все равно наступление начнется в 9, потому что никакие дополнительные согласования практически (повторяю, ПРАКТИЧЕСКИ) уже не нужны.
Зато 1-й, получив последнее сообщение 2-го, будет уже совсем спокоен, и голубя с ответом отправлять просто-напросто не будет.

Итак, четыре успешные ходки голубя ГАРАНТИРОВАННО обеспечат синхронизированное наступление. Пятая уже СОВЕРШЕННО не нужна.


Это все равно, как если бы переговоры велись по рации, и в какой-то момент в рации садится аккумулятор:

- Наступаем в девять! Прием!
- Вас понял. Наступаем в девять! Прием!
- Вас понял. Прием!
- Вас понял. Прием!... А впрочем, можете уже и не отвечать. И так все ясно.
- Хрррррр... бля... хррррр... шшшшшшш.... пи-пи-пи-пи......

Как видите, ситуация полностью аналогична задаче с голубиной почтой. Но кто скажет, что в момент отключения рации еще были какие-то неясности?

[dP]

Зато 1-й, получив последнее сообщение 2-го, будет уже совсем спокоен, и голубя с ответом отправлять просто-напросто не будет.

А какие гарантии у второго, что первый это сообщение получил и уже спокойно будет нападать???

А общение по рации, кстати, полагает что адресат все-таки гарантировано получает сообщение. А если есть шанс, что оно может не дойти, то то же самое и с тем же возражением.

[Semak]

Первый отсылает голубя. Ответный не прилетает. Вариатны:
1) первый голубь не долетел
2) второй голубь с подтверждением не долетел
3) второй голубь вообще не был отправлен, за ненадобностью

В случае (1) атака будет сорвана. Генерал не может знать, получил его коллега сообщение или нет. В чем прикол опять не понял.

[Dendr]

Первый отсылает голубя. Ответный не прилетает. Вариатны:
1) первый голубь не долетел
2) второй голубь с подтверждением не долетел
3) второй голубь вообще не был отправлен, за ненадобностью

В случае (1) атака будет сорвана. Генерал не может знать, получил его коллега сообщение или нет. В чем прикол опять не понял.

Я так понял по условию, что голубь ровно один (и эти двое его гоняют туда-сюда, но при этом-таки боятся, что он не долетит). Если два голубя - то решение, видимо, должно существовать.

[Semak]

Я условие понял, что голубей у них много, но нет 100% гарантии, что голубь долетит до адресата.

[Шшок]

А какие гарантии у второго, что первый это сообщение получил и уже спокойно будет нападать???

А общение по рации, кстати, полагает что адресат все-таки гарантировано получает сообщение. А если есть шанс, что оно может не дойти, то то же самое и с тем же возражением.

А зачем второму какие-то гарантии? Он же получил от первого самое первое письмо с уведомлением о времени атаки! Он уже давно знает, что атака в девять и даже уведомил первого о том, что выступает вместе с ним.

[dP]

А какие гарантии у второго, что первый это сообщение получил и уже спокойно будет нападать???

А общение по рации, кстати, полагает что адресат все-таки гарантировано получает сообщение. А если есть шанс, что оно может не дойти, то то же самое и с тем же возражением.

А зачем второму какие-то гарантии? Он же получил от первого самое первое письмо с уведомлением о времени атаки! Он уже давно знает, что атака в девять и даже уведомил первого о том, что выступает вместе с ним.

А затем, что если первый не получит подтверждения, то он не будет 100% уверен, а, значит и не будет атаковать, а значит и второй не может атаковать.

[Чива Ротсен]

Ну вот я и появился. И снова предлагаю вернуться к этой непростой задаче.

Шшок, объясни мне, ЗАЧЕМ одному из генералов посылать в последний, N-ный полет голубя? Зачем? Ведь уверенности в том, что голубь долетит, у него не может быть. Значит, этому генералу по барабану, долетит этот голубь или не долетит. Зачем тогда его посылать? Он может с тем же успехом его не посылать. Значит N-ный полет не нужен.

Давай не будем идти с начала. Давай будем идти с конца. И тогда, на мой взгляд, все становится ясно.

[Никита]

тогда получается что не надо воообще никаких голубей посылать.. а действовать по обстоятельствам независимо...

[Тоня]

Рассуждения с конца напоминают мне задачку об учебной тревоге в армии. Служащим становится известно, что в течение 10-ти дней (ночью) неожиданно будет объявлена учебная тревога. Давайте рассуждать с конца. Допустим, что сегодня - 10-тая ночь, а тревоги до сих пор не было. Что это значит? Значит, что она непременно будет в эту ночь, но тогда она не будет неожиданной. Значит, тревога не может быть объявлена в 10-ую ночь. По этой же причине не может и в 9-ую, и в 8-ую... Вообще никогда! Условие некорректно.
Также и с голубями. Генералы не могут быть уверены. О чём бы они не договорились заранее, они не знают, долетел ли их голубь.

[Semak]

Да, именно об этом я и говорил выше. Получается не задачка, а софизм своего рода. И в чем ее "непростота" тоже не очень понятно.

[AndrNiko]

Условие задачи про двух генералов настолько абстрактно, что его трудно интерпретировать однозначно. На практике в компьютерной индустрии есть чётко проработанные способы, как из ненадёжного протокола обмена информацией сделать надёжный. Нужны понятия тайм-аута и перезапроса. Т.е. если генерал отправил голубя и должен получить ответ, но в течение разумного времени не получил, то он считает сообщение утерянным и посылает нового голубя. Тогда никаких противоречий нет. Генерал, который посылает последнего голубя, не ждёт ответа. Он своё дело сделал. Если этот голубь не долетит, то это уже забота второго генерала - выждать установленное время, зафиксировать ошибку и послать нового голубя. Чтобы система реально действовала, величина тайм-аута должна быть заранее установлена и согласована.

Если же по условию задачи нельзя ввести понятие тайм-аута, то, видимо, она действительно не имеет решения, потому что никакой голубь не может стать последним.

Что касается задачи об учебной тревоге, то она не имеет никакого отношения к задаче о двух генералах. Задача об учебной тревоге подробно разжёвана в литературе:

М.Гарднер, Математические досуги, М., "Мир", 1972.
Глава 8. Казнь врасплох и связанный с ней логический парадокс.
Есть в Интернете, легко ищется по названию главы. Поэтому здесь пережёвывать неохота.

[Владимиррр]

Эта задача увлекала меня с детства, точнее ее интерпретация - когда можно оборвать цепочку "Я знаю, что ты знаешь, что я знаю...". Я так понимаю, что задачи идентичны в плане смысла, то есть если ответить на решение одной задачи - это же станет решением другой (Хотя я никак не могу этого доказать и до конца не уверен...).
Вроде бы математическое доказательство, предложенное в теме безупречно, я почти успокоился, что цепочка имеет смысл при любом количестве нанизанных Я знаю, что ты знаешь...но тут вдруг... Представьте себе, что генералы общаются например так:
- 1-ый Выступаем завтра в 9 утра!
- 2-ой Хорошо, тебя понял как себя чувствуешь?
- 1-ый Да все ок, а ты?
- 2-ой Да тоже все ок!
- 1-ый А как там мой брат поживает?
- 2-ой Да ты задолбал своими вопросами, старый дуралей!!
- 1-ый Ну и больше не буду писать, идиот!
И что же получается? Неужели если переписка прервется в этом месте или на 1-2 сообщение раньше (если последнее сообщение "ну и больше не буду писать, идиот!" не дойдет второй генерал не будет уверен, что дошло его последнее сообщение "да ты задолбал своими вопросами, старый дуралей", а первый генерал не будет уверен, дошло ли его последнее сообщение "ну и больше не буду писать, идиот!" и, главное, оба будут знать о сомнениях другого) что-либо от этого изменится? . Оба знают, что атака в 9 и оба знают, что об этом информирован его товарищ. Разве не так?
И вроде бы все так (я очень удивлюсь, если кто нибудь найдет логическую неувязку), теперь меня заботит вопрос лишь о правомерности такого ответа, как его связать с "бесспорным" вроде бы мат. доказательством (по крайней мере, я в нем ошибки не вижу)... и еще то, значит ли это, что во фразе: Я знаю, что ты знаешь, что я знаю.... цепочку можно обрывать после 7 звена. За сим все... надеюсь, те кто обсуждал эту тему больше года назад еще здесь или появились новые собеседники, кому эта тема будет интересна и мне будет с кем ее обсудить! Заранее спасибо!

[Лазков Йончер]

Если есть хоть небольшая вероятность, что хоть один голубь не долетит - в случае максимального невезения (как в задачке про пещеру Алладина) генералы не договорятся никогда. В чем прикол задачи не понял.

А что такое "задачка про пещеру Аладдина"?

[Dendr]

А что такое "задачка про пещеру Аладдина"?

viewtopic.php?t=1148