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

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

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

Чива Ротсен
Ультраантипатриот
Ультраантипатриот
Сообщения: 8892
Зарегистрирован: 29 сен 2003, 14:48
Пол: Мужской
Откуда: СПб
Контактная информация:

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

Сообщение Чива Ротсен »

Ах, если бы всегда сообщения в мессенджерах доходили так, как мы этого хотим.

Юляша
Популярный автор
Популярный автор
Сообщения: 3352
Зарегистрирован: 15 янв 2009, 12:32
Пол: Женский

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

Сообщение Юляша »

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

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

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

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


Пример Шшока опровергается примерно также:
Шшок писал(а):- Наступаем в девять! Прием!
- Вас понял. Наступаем в девять! Прием!
- Вас понял. Прием! Хрррррр... бля... хррррр... шшшшшшш.... пи-пи-пи-пи......
- Радист! Он меня слышал?
- Не знаю, батарея села...
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.

Antananarivu2
Графоман со стажем
Графоман со стажем
Сообщения: 615
Зарегистрирован: 09 мар 2016, 12:00
Пол: Мужской

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

Сообщение Antananarivu2 »

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

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

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

Сообщение ЛевК »

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

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

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

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

Сообщение ЛевК »

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

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

Antananarivu2
Графоман со стажем
Графоман со стажем
Сообщения: 615
Зарегистрирован: 09 мар 2016, 12:00
Пол: Мужской

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

Сообщение Antananarivu2 »

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

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) а вот и ответишь!
Тут у кого-то из них садится батарейка.

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

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

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

Сообщение ЛевК »

Antananarivu2 писал(а):И здесь у кого-то садится батарейка
Так в этом то и загвоздка!
Мы не знаем когда села батарейка!

Или так:

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

Или так:

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

Antananarivu2
Графоман со стажем
Графоман со стажем
Сообщения: 615
Зарегистрирован: 09 мар 2016, 12:00
Пол: Мужской

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

Сообщение Antananarivu2 »

Вы подменяете условие задачи.
Важно только первое сообщение. Никто затем встречу отменять или переносить не собирается.

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

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

Сообщение ЛевК »

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

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

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

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

Antananarivu2
Графоман со стажем
Графоман со стажем
Сообщения: 615
Зарегистрирован: 09 мар 2016, 12:00
Пол: Мужской

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

Сообщение Antananarivu2 »

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

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

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

Но жизнь продолжается.
Например, выходя из подъезда многоэтажного дома я тоже не могу сказать что вероятность того что мне на голову упадёт кирпич равна нулю. Она отлична от нуля (хотя и очень мала) - но тем не менее я смело выхожу из подъезда.
С этим я не спорю)
В реальном мире чаще всего будет достаточно вообще 3 сообщений:
- Встречаемся завтра в 9:00, как понял меня?
- Понял, до завтра!
- Пока

Antananarivu2
Графоман со стажем
Графоман со стажем
Сообщения: 615
Зарегистрирован: 09 мар 2016, 12:00
Пол: Мужской

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

Сообщение Antananarivu2 »

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

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

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

Сообщение ЛевК »

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

Аватара пользователя
Шшок
Акула пера
Акула пера
Сообщения: 9061
Зарегистрирован: 28 ноя 2003, 14:05
Пол: Мужской
Откуда: С большой дороги.

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

Сообщение Шшок »

Я думаю, что если в исходной задаче заменить генералов на прапорщиков, то задача станет более жизненной :lol:
В борьбе бобра с козлом побеждает бобро. Или козло.

Юляша
Популярный автор
Популярный автор
Сообщения: 3352
Зарегистрирован: 15 янв 2009, 12:32
Пол: Женский

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

Сообщение Юляша »

Antananarivu2 писал(а):
16 фев 2020, 15:12
Но по условиям задачи «Генералы и голуби» любое сколь угодно большое количество сообщений недостаточно.
Не так. Давайте рассмотрим условие задачи как игру: "Генералы против шпиона из будущего".

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

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

Генералы выигрывают, если ни один из них не сделал записи в дневнике или оба они сделали такую запись. Если же запись сделал только один генерал, то выигрывает шпион.

Суть ответа в том, что выигрышной стратегии для генералов не существует, шпион всегда может найти подходящий момент для вмешательства.
Традиционная методика: "запросим дополнительное подтверждение", - тоже не помогает.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.

Ответить

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