Генералы и голуби.
Модераторы: Азарапетыч, Администрация
-
- Ультраантипатриот
- Сообщения: 8892
- Зарегистрирован: 29 сен 2003, 14:48
- Пол: Мужской
- Откуда: СПб
- Контактная информация:
Генералы и голуби.
А эту задачу знаете?
Два генерала должны пойти в наступление на двух фронтах. Одновременно. Следовательно, они должны договориться о времени выступления, которое заранее ими не определено. Связь между ними осуществляется только посредством голубиной почты. Для простоты пусть будет один только голубь. Итак, генералы обязательно должны договориться об общем времени наступления, иными словами каждый генерал должен быть уверен, что они оба обладают необходимой информацией о часе Х.
По силам ли им это? А если да, то за сколько полетов голубя туда-сюда?
П.С. Следует учитывать, что голубиная почта - она, мягко говоря, ненадежная. Мало ли что голубю по дороге встретится - охотник, голубка с гнездом, и так далее.
Два генерала должны пойти в наступление на двух фронтах. Одновременно. Следовательно, они должны договориться о времени выступления, которое заранее ими не определено. Связь между ними осуществляется только посредством голубиной почты. Для простоты пусть будет один только голубь. Итак, генералы обязательно должны договориться об общем времени наступления, иными словами каждый генерал должен быть уверен, что они оба обладают необходимой информацией о часе Х.
По силам ли им это? А если да, то за сколько полетов голубя туда-сюда?
П.С. Следует учитывать, что голубиная почта - она, мягко говоря, ненадежная. Мало ли что голубю по дороге встретится - охотник, голубка с гнездом, и так далее.
-
- Ультраантипатриот
- Сообщения: 8892
- Зарегистрирован: 29 сен 2003, 14:48
- Пол: Мужской
- Откуда: СПб
- Контактная информация:
- Шшок
- Акула пера
- Сообщения: 9061
- Зарегистрирован: 28 ноя 2003, 14:05
- Пол: Мужской
- Откуда: С большой дороги.
Ну тогда это действительно рассуждение на тему о том, где можно с уверенностью оборвать цепочку "Я знаю, что ты знаешь, что я знаю, что...."Чива Ротсен писал(а):Согласен. Сплоховал с формулировкой. Можно, в принципе, сказать что пусть голубей у них неограниченное количество и долетают они до цели с какой-то постоянной вероятностью. Но лучше сказать так: голуби долетают всегда. Но об этом знаем только мы с вами, а генералы уверены быть не могут.
Что-то не поняла...
1.Первый генерал пишет: атакуем завтра в 9 утра.
2.Второй, получив ответ, отправляет голубя взад с подтверждением. Теперь первый точно знает, что второй его информацию получил. И может смело атаковать в 9 утра.
3.Первый тоже отправляет подтверждение. Теперь второй точно знает, что первый знает, что он знает про 9 часов.
ВСЕ. В чем подвох?
1.Первый генерал пишет: атакуем завтра в 9 утра.
2.Второй, получив ответ, отправляет голубя взад с подтверждением. Теперь первый точно знает, что второй его информацию получил. И может смело атаковать в 9 утра.
3.Первый тоже отправляет подтверждение. Теперь второй точно знает, что первый знает, что он знает про 9 часов.
ВСЕ. В чем подвох?
Гном
- Dendr
- Акула пера
- Сообщения: 5717
- Зарегистрирован: 06 май 2005, 15:11
- Пол: Мужской
- Откуда: Раменское, Мос.обл.
- Контактная информация:
Интересная задачка
Хотел было задать вопрос по условию, потом стал писать примерное решение, дабы задать вопрос-уточнение по задаче, а в итоге разобрался с условием, и ответ (вроде верный) решил послать в личку
В общем, получилось также, как и с генералами. Именно, что: "Я знаю, что ты знаешь...<skipped>... что мы оба знаем"
Ну вот пока ответ писал, да в личку перекидывал - Гном уже в теме отметилась
Хотел было задать вопрос по условию, потом стал писать примерное решение, дабы задать вопрос-уточнение по задаче, а в итоге разобрался с условием, и ответ (вроде верный) решил послать в личку
В общем, получилось также, как и с генералами. Именно, что: "Я знаю, что ты знаешь...<skipped>... что мы оба знаем"
Ну вот пока ответ писал, да в личку перекидывал - Гном уже в теме отметилась
-
- Ультраантипатриот
- Сообщения: 8892
- Зарегистрирован: 29 сен 2003, 14:48
- Пол: Мужской
- Откуда: СПб
- Контактная информация:
-
- Ультраантипатриот
- Сообщения: 8892
- Зарегистрирован: 29 сен 2003, 14:48
- Пол: Мужской
- Откуда: СПб
- Контактная информация:
- freddy
- Администратор
- Сообщения: 13569
- Зарегистрирован: 27 авг 2003, 13:56
- Пол: Мужской
- Откуда: Санкт-Петербург
- Контактная информация:
Последний отправивший не знает, дошёл ли его голубь и, соответственно, не знает, знает ли второй генерал, что тот знает, что голубь к нему дошёл.Гном писал(а):Что-то не поняла...
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 - это минимальное необходимое количество пролетов. Мы пришли к противоречию. Следовательно, исходное предположение (о возможности договоренности у этих параноиков) - неверно. Финиш.
Допустим, решение существует. И именно N - минимальное количество пролетов голубя, которых будет достаточно, чтобы генералы были абсолютно уверены, что они поняли друг друга и договорились.
Но тогда получается, что генералу, отправившего голубя в последний, N-ный полет, совершенно безразлично, долетит он до адресата или нет. Ведь он не ждет подтверждения. Значит, этот последний, N-ный полет голубя вообще не нужен во всей ситуации, если не важно, получит его другой генерал или нет. Значит, этого последнего голубя можно было и не посылать вообще. А соответственно, для успешного завершения компании хватило бы и N-1 - го пролета голубя. Но мы же объявили, что N - это минимальное необходимое количество пролетов. Мы пришли к противоречию. Следовательно, исходное предположение (о возможности договоренности у этих параноиков) - неверно. Финиш.
- Dendr
- Акула пера
- Сообщения: 5717
- Зарегистрирован: 06 май 2005, 15:11
- Пол: Мужской
- Откуда: Раменское, Мос.обл.
- Контактная информация:
Прочитал-таки ответ... ("цитата" - рулит )
Такой ответ подозревал, но мысль не развивал... (хм, стихами заговорил - и это посреди ночи:))
Было предолжение сделать так:
пусть p - вероятность того, что голубь долетит
q=1-p - не долетит
Тогда вероятность того, что голубь пролетит ровно N раз и сдохнет (скорее всего, от изнеможения - за время его полета эти придурки могли по-другому связаться) - P(N)=q*p^(N-1).
А какова вероятность того, что оба генерала свяжутся? очевидно,
P=sum(P(N),N=1,inf)==p (!). Иными словами, получается, что первому генералу достаточно пустить голубя и забыть о нем, готовиться к атаке. По теории вероятностей, то, что второй ответит, ничего не поменяет (!!).
Отсюда ответ - достаточно одного раза (чтобы скотинку не мучать). В любом случае, атака будет удачной с вероятностью p (повторюсь, сколько птицу не гоняй - результат один и тот же)
Такой ответ подозревал, но мысль не развивал... (хм, стихами заговорил - и это посреди ночи:))
Было предолжение сделать так:
пусть p - вероятность того, что голубь долетит
q=1-p - не долетит
Тогда вероятность того, что голубь пролетит ровно N раз и сдохнет (скорее всего, от изнеможения - за время его полета эти придурки могли по-другому связаться) - P(N)=q*p^(N-1).
А какова вероятность того, что оба генерала свяжутся? очевидно,
P=sum(P(N),N=1,inf)==p (!). Иными словами, получается, что первому генералу достаточно пустить голубя и забыть о нем, готовиться к атаке. По теории вероятностей, то, что второй ответит, ничего не поменяет (!!).
Отсюда ответ - достаточно одного раза (чтобы скотинку не мучать). В любом случае, атака будет удачной с вероятностью p (повторюсь, сколько птицу не гоняй - результат один и тот же)
Первый шлет записку - "Атакуем в 9 утра. Подтверждением того что я получил ваше согласие будет прекращение посылок голубей с этим сообщением"
и шлет голубя за голубем пока не получит ответного сообщения. после чего умолкает.
Второй тоже шлет ответных голубей пока поток голубей с той стороны не утихнет.
и вот когда оба пересткнут слать голубей, оба будут знать что оба знают о времени выступления.
и шлет голубя за голубем пока не получит ответного сообщения. после чего умолкает.
Второй тоже шлет ответных голубей пока поток голубей с той стороны не утихнет.
и вот когда оба пересткнут слать голубей, оба будут знать что оба знают о времени выступления.
- Semak
- Акула пера
- Сообщения: 7894
- Зарегистрирован: 13 май 2004, 18:30
- Пол: Мужской
- Откуда: Москва
- Контактная информация:
Если есть хоть небольшая вероятность, что хоть один голубь не долетит - в случае максимального невезения (как в задачке про пещеру Алладина) генералы не договорятся никогда. В чем прикол задачи не понял.
Каждой хорошенькой девушке - по плохому танцору!
Хотите научиться играть в бридж? Тогда вам СЮДА
Хотите научиться играть в бридж? Тогда вам СЮДА