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

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

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

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

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

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

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

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

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

П.С. Следует учитывать, что голубиная почта - она, мягко говоря, ненадежная. Мало ли что голубю по дороге встретится - охотник, голубка с гнездом, и так далее.

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

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

Что-то уж больно много недоговоренностей в этой задачке. Например, наличие охотника.
Генерал 1 пишет генералу 2 записку: Атаку начинаем завтра в 9 утра. Голубь вылетает с этой запиской, его по дороге убивает охотник - и все. Конец задаче.
Или я чего-то недопонял?

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

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

Или, может быть, это задачка в стиле "Я знаю, что ты знаешь, что я знаю, что ты знаешь...." - и так до бесконечности?

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

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

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

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

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

Чива Ротсен писал(а):Согласен. Сплоховал с формулировкой. Можно, в принципе, сказать что пусть голубей у них неограниченное количество и долетают они до цели с какой-то постоянной вероятностью. Но лучше сказать так: голуби долетают всегда. Но об этом знаем только мы с вами, а генералы уверены быть не могут.
Ну тогда это действительно рассуждение на тему о том, где можно с уверенностью оборвать цепочку "Я знаю, что ты знаешь, что я знаю, что...."

Аватара пользователя
Гном
Акула пера
Акула пера
Сообщения: 5768
Зарегистрирован: 17 сен 2003, 00:07
Откуда: СПб

Сообщение Гном »

Что-то не поняла...
1.Первый генерал пишет: атакуем завтра в 9 утра.
2.Второй, получив ответ, отправляет голубя взад с подтверждением. Теперь первый точно знает, что второй его информацию получил. И может смело атаковать в 9 утра.
3.Первый тоже отправляет подтверждение. Теперь второй точно знает, что первый знает, что он знает про 9 часов.
ВСЕ. В чем подвох?
Гном

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Сообщение Dendr »

Интересная задачка :)
Хотел было задать вопрос по условию, потом стал писать примерное решение, дабы задать вопрос-уточнение по задаче, а в итоге разобрался с условием, и ответ (вроде верный) решил послать в личку :)

В общем, получилось также, как и с генералами. Именно, что: "Я знаю, что ты знаешь...<skipped>... что мы оба знаем" :)

Ну вот :) пока ответ писал, да в личку перекидывал - Гном уже в теме отметилась :)

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

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

Ребята, давайте-ка все-таки через личку.

Верных решений пока нет. К сожалению не могу объяснить, почему. Ибо объяснение фактически является ответом.

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

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

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

Аватара пользователя
freddy
Администратор
Администратор
Сообщения: 13569
Зарегистрирован: 27 авг 2003, 13:56
Пол: Мужской
Откуда: Санкт-Петербург
Контактная информация:

Сообщение freddy »

Гном писал(а):Что-то не поняла...
1.Первый генерал пишет: атакуем завтра в 9 утра.
2.Второй, получив ответ, отправляет голубя взад с подтверждением. Теперь первый точно знает, что второй его информацию получил. И может смело атаковать в 9 утра.
3.Первый тоже отправляет подтверждение. Теперь второй точно знает, что первый знает, что он знает про 9 часов.
ВСЕ. В чем подвох?
Последний отправивший не знает, дошёл ли его голубь и, соответственно, не знает, знает ли второй генерал, что тот знает, что голубь к нему дошёл.

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

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

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

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

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

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

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

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Сообщение Dendr »

Прочитал-таки ответ... ("цитата" - рулит :))
Такой ответ подозревал, но мысль не развивал... (хм, стихами заговорил - и это посреди ночи:))

Было предолжение сделать так:
пусть p - вероятность того, что голубь долетит
q=1-p - не долетит
Тогда вероятность того, что голубь пролетит ровно N раз и сдохнет (скорее всего, от изнеможения - за время его полета эти придурки могли по-другому связаться) - P(N)=q*p^(N-1).
А какова вероятность того, что оба генерала свяжутся? очевидно,
P=sum(P(N),N=1,inf)==p (!). Иными словами, получается, что первому генералу достаточно пустить голубя и забыть о нем, готовиться к атаке. По теории вероятностей, то, что второй ответит, ничего не поменяет (!!).

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

Аватара пользователя
Никита
Популярный автор
Популярный автор
Сообщения: 1153
Зарегистрирован: 11 окт 2004, 13:22
Пол: Мужской

Сообщение Никита »

Первый шлет записку - "Атакуем в 9 утра. Подтверждением того что я получил ваше согласие будет прекращение посылок голубей с этим сообщением"

и шлет голубя за голубем пока не получит ответного сообщения. после чего умолкает.
Второй тоже шлет ответных голубей пока поток голубей с той стороны не утихнет.

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

Аватара пользователя
Semak
Акула пера
Акула пера
Сообщения: 7894
Зарегистрирован: 13 май 2004, 18:30
Пол: Мужской
Откуда: Москва
Контактная информация:

Сообщение Semak »

Если есть хоть небольшая вероятность, что хоть один голубь не долетит - в случае максимального невезения (как в задачке про пещеру Алладина) генералы не договорятся никогда. В чем прикол задачи не понял.
Каждой хорошенькой девушке - по плохому танцору!
Хотите научиться играть в бридж? Тогда вам СЮДА

Ответить

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