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

Логические задачи

Модераторы: Азарапетыч, Администрация

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

Сообщение Чива Ротсен » 08 июл 2005, 12:23

А эту задачу знаете?

Два генерала должны пойти в наступление на двух фронтах. Одновременно. Следовательно, они должны договориться о времени выступления, которое заранее ими не определено. Связь между ними осуществляется только посредством голубиной почты. Для простоты пусть будет один только голубь. Итак, генералы обязательно должны договориться об общем времени наступления, иными словами каждый генерал должен быть уверен, что они оба обладают необходимой информацией о часе Х.

По силам ли им это? А если да, то за сколько полетов голубя туда-сюда?

П.С. Следует учитывать, что голубиная почта - она, мягко говоря, ненадежная. Мало ли что голубю по дороге встретится - охотник, голубка с гнездом, и так далее.
Чива Ротсен
Ультраантипатриот
Ультраантипатриот
 
Сообщения: 8883
Зарегистрирован: 29 сен 2003, 14:48
Откуда: СПб

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

Сообщение Чива Ротсен » 07 фев 2020, 22:30

Ах, если бы всегда сообщения в мессенджерах доходили так, как мы этого хотим.
Чива Ротсен
Ультраантипатриот
Ультраантипатриот
 
Сообщения: 8883
Зарегистрирован: 29 сен 2003, 14:48
Откуда: СПб

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

Сообщение Юляша » 08 фев 2020, 16:55

К сожалению, договориться действительно невозможно. И опровержение справедливо.
Пусть некая согласованная генералами процедура требует обмена К сообщениями. Тогда рассмотрим вариант, когда голубь успешно слетал К-1 раз, а именно на К-ом разе помер. Все - процедура не соблюдена, атаки не будет или она окончится катастрофой.
Предельный вариант - когда первый генерал вообще не ждет подтверждения. Голубь не долетает, второй генерал в блаженном неведении, первый атакует и получает по рогам.

Все приведенные здесь "контрпримеры" опираются на то, что подразумеваемая процедура короче, чем набор полученных сообщений.

Вот, например, что написал Владимиррр.
Владимиррр писал(а):- 1-ый Выступаем завтра в 9 утра!
- 2-ой Хорошо, тебя понял как себя чувствуешь?
- 1-ый Да все ок, а ты?
- 2-ой Да тоже все ок!
- 1-ый А как там мой брат поживает?
- 2-ой Да ты задолбал своими вопросами, старый дуралей!!
- 1-ый Ну и больше не буду писать, идиот!


Вроде все классно... Но предположим, что после

Владимиррр писал(а):- 1-ый Выступаем завтра в 9 утра!
- 2-ой Хорошо, тебя понял как себя чувствуешь?


переписка оборвалась. Откуда второму знать, получил первый подтверждение или нет?
(Между строк Владимиррр подразумевал, что двух писем достаточно.)

Или так: если первому генералу достаточно Х подтверждений, а второму - Y подтверждений, то мы всегда можем "перехватить" голубя в такой момент, когда для одного генерала условие выполнено, а для другого - нет.


Пример Шшока опровергается примерно также:

Шшок писал(а):- Наступаем в девять! Прием!
- Вас понял. Наступаем в девять! Прием!
- Вас понял. Прием! Хрррррр... бля... хррррр... шшшшшшш.... пи-пи-пи-пи......
- Радист! Он меня слышал?
- Не знаю, батарея села...
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3203
Зарегистрирован: 15 янв 2009, 12:32

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

Сообщение Antananarivu2 » 08 фев 2020, 18:58

Спасибо, Юляша.
У меня больше вопросов было про то, почему в реальной жизни нам не требуется бесконечного количества сообщений, чтобы друг друга понять: договориться в мессенджере о завтрашней встрече, например.
Но вроде своим последним постом я сам для себя все объяснил. :)
Antananarivu2
Литератор-любитель
Литератор-любитель
 
Сообщения: 475
Зарегистрирован: 09 мар 2016, 12:00

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

Сообщение ЛевК » 16 фев 2020, 13:24

Antananarivu2 писал(а):Спасибо, Юляша.
У меня больше вопросов было про то, почему в реальной жизни нам не требуется бесконечного количества сообщений, чтобы друг друга понять: договориться в мессенджере о завтрашней встрече, например.
Но вроде своим последним постом я сам для себя все объяснил. :)

В реальной жизни тоже может возникнуть такая ситуация.
Например.
Квартира. Жена вертится на кухне. Муж - в комнате с компом.
Жена: Слушай, у нас оказывается гречка закончилась. Сбегай срочно в магазин.
Муж (смотрит на часы): Хорошо, бегу. У меня, правда, через двадцать минут важный конференс, но успею. (Вскакивает, бежит к двери)
Жена: Да, тут еще, я смотрю, огурцы закончились, заскочи еще в овощной...
Муж (уже с лестничной клетки): За огурцами уже, боюсь, не успею.

В этой ситауции нельзя сказать, что муж уверен, что жена его слышала, ибо он уже был вне квартиры. Вот если бы она подтвердила это "Ну хорошо не надо, сама сбегаю", то - другое дело. Но даже если бы жена и произнесла эту фразу, он не может быть уверена, что муж ее услышал.
И т.д.

Вот нам - реальная жизнь, в которой каждое сообщение несет в себе важную информацию, от которой зависит поведение принимающего ее.
Вполне возможно, что в результате огурцы купят оба, или вообще никто.
Ровно как и с генералами.
Аватара пользователя
ЛевК
Популярный автор
Популярный автор
 
Сообщения: 1288
Зарегистрирован: 29 ноя 2004, 20:33
Откуда: Израиль

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

Сообщение ЛевК » 16 фев 2020, 14:09

Ещё пример - более похожий на оригинал

14:00 Ваня шлет сообщение Коле: Встреча в 16:00
15:00 У Вани садится батарейка
15:05 Коля наконец отвечает: В 16:00 не успеваю. Давай перенесем на 17:00
15:15 У Коли садится батарейка
15:20 Ваня находит розетку, подключает телефон, читает сообщение и отвечает: "В 17:00 не могу. Перенесем на завтра"
15:30 У обоих меняются обстоятельства - оба времени подходят каждому
Занавес.
Что мы имеем? Ни Ваня, ни Коля не уверены что их последнее сообщение прочитано.
И потому, в зависимости от степени их уверенности, возможен полный веер из 9 различных поведений (каждый может прийти в 16, в 17 или не прийти вообще).
Аватара пользователя
ЛевК
Популярный автор
Популярный автор
 
Сообщения: 1288
Зарегистрирован: 29 ноя 2004, 20:33
Откуда: Израиль

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

Сообщение Antananarivu2 » 16 фев 2020, 15:12

Но по условиям задачи «Генералы и голуби» любое сколь угодно большое количество сообщений недостаточно. И как быть например с таким диалогом?

1)- Встречаемся завтра в 9, как понял?
2)- Понял тебя отлично!
1)- Вот и хорошо! Кстати, смотрел вчера игру Спартака?
2)- Нет, не смотрел, а что там было?
1)- Ой, чего там только не было!
2)- Ладно, потом расскажешь! Как здоровье мамы?
1)- Спасибо, отлично, а твоей?
2)- Спасибо, тоже.
(Пропущено 2344 сообщений про футбол, политику и женщин)
1)- Тебе не кажется, что мы с тобой заболтались?
2)- Есть такое. Ладно, пока
1)- Пока
2)- Пока, пока.
1)- Пока, пока, пока)
И здесь у кого-то садится батарейка.

Ну или если вернуться к исходной задаче и к генералам, с таким?

1)- Выступаем завтра в 9:00, как понял?
2)- Принято, выступаем, завтра в 9:00, как понял, что я понял?
1)- Принято, выступаем, завтра в 9:00, как понял, что я понял?
2)- Принято, выступаем, завтра в 9:00, как понял, что я понял?
1)- Принято, выступаем, завтра в 9:00, как понял, что я понял?
2)- Принято, выступаем, завтра в 9:00, как понял, что я понял?
1)- Принято, выступаем, завтра в 9:00, как понял, что я понял?
2)- Принято, выступаем, завтра в 9:00, как понял, что я понял?
1)- Принято, выступаем, завтра в 9:00, как понял, что я понял?
2)- Принято, выступаем, завтра в 9:00, как понял, что я понял?
1)- Принято, выступаем, завтра в 9:00, как понял, что я понял?
2)- Принято, выступаем, завтра в 9:00, как понял, что я понял?
(Пропущено 7344 сообщения)
1)- Принято, выступаем, завтра в 9:00, как понял, что я понял?
И тут у одного из генералов убивают голубя.

Ну или давайте царство абсурда:

1) Встречаемся завтра в 9:00
2) ок, понял тебя
1) как дела?
2) хорош болтать
1) а мне хочется
2) надоел
1) хаха
2) надоел, сказал!
1) хихи
2) черт!
1) хохо
2) если ты еще раз мне напишешь, я тебя убью
1) не убьешь
2) в любом случае, я больше тебе не отвечу
1) а вот и ответишь!
Тут у кого-то из них садится батарейка.

Кто-нибудь в здравом уме может представить, что этих диалогов недостаточно, чтобы завтра в девять встреча состоялась?
Antananarivu2
Литератор-любитель
Литератор-любитель
 
Сообщения: 475
Зарегистрирован: 09 мар 2016, 12:00

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

Сообщение ЛевК » 16 фев 2020, 16:01

Antananarivu2 писал(а):И здесь у кого-то садится батарейка

Так в этом то и загвоздка!
Мы не знаем когда села батарейка!

Или так:

1-й генерал: Пока...
У 2-го садится батарейка
1-й генерал: пока... ой блин, всё отменяется, в 9:00 теща прилетает, должен встретить. Перенесем на 10:00.

Или так:

1-й генерал: Пока...
1-й генерал: пока... ой блин, всё отменяется, в 9:00 теща прилетает, должен встретить. Перенесем на 10:00.
У 2-го садится батарейка
Аватара пользователя
ЛевК
Популярный автор
Популярный автор
 
Сообщения: 1288
Зарегистрирован: 29 ноя 2004, 20:33
Откуда: Израиль

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

Сообщение Antananarivu2 » 16 фев 2020, 16:11

Вы подменяете условие задачи.
Важно только первое сообщение. Никто затем встречу отменять или переносить не собирается.
Antananarivu2
Литератор-любитель
Литератор-любитель
 
Сообщения: 475
Зарегистрирован: 09 мар 2016, 12:00

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

Сообщение ЛевК » 16 фев 2020, 16:11

Antananarivu2 писал(а):Кто-нибудь в здравом уме может представить, что этих диалогов недостаточно, чтобы завтра в девять встреча состоялась?

Мы же говорим не о житейских делах, а о строгой математике.

Дадим определение: Генерал считается уверенным в том что его сообщение достигло адресата, в том и только том случае если он получил от него подтверждение. В противном случае генерал считается неуверенным.
В рамках данного определения нет понятия "почти уверен" или "уверен на 99.99%".

Видимо это тебе и мешает.

Но жизнь продолжается.
Например, выходя из подъезда многоэтажного дома я тоже не могу сказать что вероятность того что мне на голову упадёт кирпич равна нулю. Она отлична от нуля (хотя и очень мала) - но тем не менее я смело выхожу из подъезда.
Аватара пользователя
ЛевК
Популярный автор
Популярный автор
 
Сообщения: 1288
Зарегистрирован: 29 ноя 2004, 20:33
Откуда: Израиль

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

Сообщение Antananarivu2 » 16 фев 2020, 16:17

ЛевК писал(а):
Antananarivu2 писал(а):Кто-нибудь в здравом уме может представить, что этих диалогов недостаточно, чтобы завтра в девять встреча состоялась?

Мы же говорим не о житейских делах, а о строгой математике.

Дадим определение: Генерал считается уверенным в том что его сообщение достигло адресата, в том и только том случае если он получил от него подтверждение. В противном случае генерал считается неуверенным.
В рамках данного определения нет понятия "почти уверен" или "уверен на 99.99%".

Видимо это тебе и мешает.

Но жизнь продолжается.
Например, выходя из подъезда многоэтажного дома я тоже не могу сказать что вероятность того что мне на голову упадёт кирпич равна нулю. Она отлична от нуля (хотя и очень мала) - но тем не менее я смело выхожу из подъезда.

С этим я не спорю)
В реальном мире чаще всего будет достаточно вообще 3 сообщений:
- Встречаемся завтра в 9:00, как понял меня?
- Понял, до завтра!
- Пока
Antananarivu2
Литератор-любитель
Литератор-любитель
 
Сообщения: 475
Зарегистрирован: 09 мар 2016, 12:00

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

Сообщение Antananarivu2 » 16 фев 2020, 16:19

Главное, чтобы эти двое не знали про задачу двух генералов и о бесконечной цепочке «я знаю, что ты знаешь, что я знаю...» :D
Antananarivu2
Литератор-любитель
Литератор-любитель
 
Сообщения: 475
Зарегистрирован: 09 мар 2016, 12:00

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

Сообщение ЛевК » 16 фев 2020, 16:22

Antananarivu2 писал(а):Главное, чтобы эти двое не знали про задачу двух генералов и о бесконечной цепочке «я знаю, что ты знаешь, что я знаю...» :D

Ну, слава Б-гу, разобрались :)
Аватара пользователя
ЛевК
Популярный автор
Популярный автор
 
Сообщения: 1288
Зарегистрирован: 29 ноя 2004, 20:33
Откуда: Израиль

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

Сообщение Шшок » 17 фев 2020, 11:40

Я думаю, что если в исходной задаче заменить генералов на прапорщиков, то задача станет более жизненной :lol:
В борьбе бобра с козлом побеждает бобро. Или козло.
Аватара пользователя
Шшок
Акула пера
Акула пера
 
Сообщения: 8669
Зарегистрирован: 28 ноя 2003, 14:05
Откуда: С большой дороги.

Пред.

Вернуться в Задачки

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1