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

[tatx]

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

[dmart]

Белые могут тупо перехватывать все сообщения

Не могут.Некоторое сообщения,так или иначе доходят.

В таком случае, решение - в самом начале ГПиФК.

[Джек Сталин]

tatx, звук залпа, по сути тоже передача информации, к тому же гантированная. По условию же вся информация может передаваться только через сообщения.
dmart, не знаю что такое " ГПиФК", но в данной теме даже приблизительно верного решения предложено не было.

[dmart]

tatx, звук залпа, по сути тоже передача информации, к тому же гантированная. По условию же вся информация может передаваться только через сообщения.
dmart, не знаю что такое " ГПиФК", но в данной теме даже приблизительно верного решения предложено не было.

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

[Джек Сталин]

dmart, ты вообще читал условие? Не годится оно тем, что по нему, мы должны Абсолютно Гарантированно знать, что вторая половина тоже атакует в полдень. И "вариант авось одно дойдет" поэтому нас не устраивает. Веротность 0.99999 хорошо, но нам нужна вероятность 1 и никак не меньше.

[dmart]

dmart, ты вообще читал условие? Не годится оно тем, что по ниму, мы должны Абсолютно Гарантированно, знать что вторая половина тоже атакует в полдень. И "вариант авось одно дойдет" поэтому нас не устраивает. Веротность 0.99999 хорошо, но нам нужна вероятность 1 и никак не меньше.

Путаемся в показаниях. См. выше:

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

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

[Джек Сталин]

Однако...Чтобы задача имела смысл некоторые сообщения должны доходить, иначе любое решение заранее бесмысленно. Но если смотреть на задачу глазами "генерала", то он отписывает сообщение отдает его гонцу и смотрит как тот исчезает в дали. Он не имеет ни малейшего представления с какой веротяностью его письмо будет доставленно, и будет ли вообще, и он не знает, что некотрые письма так или иначе доходят.
Только для тебя краткий курс теории вероятности. Предположим предположим, что шанс доставки письма 0.5, тем не менее если мы отправим 2 письма то шанс доставки информации будет лишь 3/4, а не 1/2*2, как некотороые могли подумать. 10 писем дадут нам шанс доставки где-то 0.999, "стотыщмильонов" еще больший, он конечно будет стремиться к единице, но все же никогда его не достигнет. То есть доставка не будет абсолютно гарантированной. И сколько же мне еще раз написать, что генерал не может полагаться на случай? Ему необходимо четкое подтверждение того, что его письмо дошло, вероятность 1 и не меньше.

[dmart]

BlackJack, никто не говорил, что генералам не нужно подтверждение, подтверждение доставки подтверждения и т.д. По-моему, давно уже пора зеркально отразить ситуацию. Будем считать, что мы сдались. Ждём вариант решения от загадчика и подвергнем его уничтожающей критике.
Или тебе нужно строгое доказательство нерешаемости задачи с вероятностью 1? Думаю, доказать это методом "от противного" не составит труда.

[Джек Сталин]

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

[dmart]

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

Попытки искажения условия - неизбежное следствие попыток сделать нерешаемую задачу решаемой.
Доказательство нерешаемости. Предположим, существуют конечные последовательности сообщений, которые, несмотря на недоставку некоторых их них, приводят к успеху с вероятностью 1. Тогда среди них должна быть минимальная. В этом случае, недоставка заключительного сообщения из этой последовательности сделает эту последовательность короче минимальной, что будет фатально для генерала, отправившего это сообщение - с его точки зрения, атака согласована, а с точки зрения генерала-получателя - нет. Что противоречит исходным предположениям.
Ваш ход. Можете предъявить контрпример?

[Джек Сталин]

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

[dmart]

Это уже заговаривание зубов. Доказательство нерешаемости (несуществования такой конечной последовательности) я предъявил, ты контрпримера не привёл. Существование интернета - тоже для красного словца, а никакое не доказательство. Если это был намёк на протокол TCP, то там подтверждение подтверждения не требуется - пакет тупо перепосылается, пока не придёт подтверждение или истечёт таймаут.
Специально для тебя напомню известное положение из криптографии. Единственная защита канала связи от неприятности "злоумышленник посредине" - это использование в какой-то момент альтернативного канала, в котором если даже и есть злоумышленник посредине - то заведомо другой.

[Джек Сталин]

Это наглядный пример. Твое доказательство неверно, о чем я уже писал, вернее оно возможно и верно, но никак не относится к рассматриваемому случаю. Так же как и "man in the middle" не имеет к нему никакого отношения. К слову последнее решается шифрованием.

подтверждения не требуется - пакет тупо перепосылается, пока не придёт подтверждение

Ты не находишь в этой фразе некого логического противоречия? Если нет, то ты не верно представляешь принцип работы TCP.

[dmart]

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

Предъяви решение.

Так же как и "man in the middle" не имеет к нему никакого отношения. К слову последнее решается шифрованием.

Как раз шифрованием последнее не решается. Необходима сверка fingerprints ключей по телефону или иному каналу.

Добавлено спустя 4 минуты 2 секунды:

Ты не находишь в этой фразе некого логического противоречия? Если нет, то ты не имеешь понятия о принципе работы TCP.

Ну-ка, расскажи, о чём я ещё не имею понятия. Кстати, покури википедию, статью "Задача двух генералов". Там доказательство нерешаемости точь-в-точь моё, разве что чуть построже сформулировано.

[Джек Сталин]

То есть нет логического противорчеия, отлично.

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

[dmart]

BlackJack, как знаешь. Я утратил интерес к задаче, после того как доказал её нерешаемость и получил из независимого источника подтверждение правильности моего доказательства.

[Джек Сталин]

Что же, если задача не представляет ни для кого интереса. То решение которое предложил dmart яыляется правильным. Задачу можно считать решенной.

[Spanish Angel]

решение которое предложил dmart яыляется правильным. Задачу можно считать решенной.

Где ответ?где решение?Что-то я ни фика не понял..

[dmart]

Два туриста подошли к реке. У берега была лодка, способная переправить на другую сторону только одного человека. Вплавь, в том числе, держась за лодку, переправляться нельзя - в реке пираньи и разные прочие гирудас медициналис. И тем не менее оба туриста успешно переправились. Как?
Если уже было - напишите, пожалуйста, в личку, удалю.

[Spanish Angel]

один был суперменом и перелетел?=))

[dmart]

Spanish Angel, нет.

[Spanish Angel]

они построили вторую лодку?=)

[dmart]

Тоже нет.

[Spanish Angel]

блин:(
надо подумать..

[lilith]

Блин, ну и задачки у вас. =/
А они оба были на одном береге?