Заним. задачка

[XpeH]

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

Чупа from forum MPGU писал(а):

"Три человека сидят за столом. Им приходит в голову посчитать свою среднюю ЗП (на 3х), но никто не хочет говорить, сколько получает. Какой способ общения им нужно выбрать?

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

Эту задачу я увидел на форуме своего универа(http://www.ort-usa.org/~cyberbat/forum/ ... php?p=4878), решил с одной оговоркой и теперь мне интересно есть ли другие решения(без этой оговорки). Автор что-то давно не показывается, поэтому я нагло решил поэксплуатировать лучшие умы России:). Решение я приведу ниже, на всякий случай(если кто-то заинтерисуется и захочет сам порешать) фоновым цветом. Просто выделите область внизу.

Для решения я воспользовался своими куцыми знаниями из теории кодирования. Решается она след. образом, причем не только для 3-х, а для любого числа человек, с оговоркой, что участники этого круглого стола могут закрывать уши и соответсвенно не слышать друг-друга. Думаю уже достаточно, но на всякий случай - решение: 1-й загадывает произвольное число х, 3-й закрывает уши и 1-й сообщает это число 2-му. Далее, уши закрывает первый, а второй добавляет свою зарплату к х и сообщает эту сумму 3-му, потом уши закрывает второй и третий делится полученным результатом с первым. Тот добавляет свою зарплату, отнимает х и делит на 3. Все. Противоречий вроде нет, каждый знает только сумму зарплат двух других собеседников.

[Руст]

Я не совсем понял смысль задачи. Это вроде игры в покер через компьютер, описанный Гарднером? Т.е. связано с шифровкой информацией?

[XpeH]

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

[Руст]

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

[XpeH]

2 Руст Вчера безуспешно искал упомянутую Вами книгу. Насколько я понял автор - Эрл Стенли Гарднер, а книга называется "Партия в покер". Если знаете где эта книга лежит в электронном виде, дайте пожалуйста ссылку. Ни на одной известной мне "свободной" библиотеке я ее не нашел. Или, если Вас это не затруднит, выложите сюда текст с описанием способа Гарднера.

[juna]

Вряд ли книга называется "Партия в покер", у меня есть много книжек Гарднера. Точно не помню посмотрите здесь http://slil.ru/23071900

[Руст]

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

[XpeH]

Почитал Ященко, да как оказалось я действитеьно использовал один из приведенных там алгоритмов, правда с некоторой модификацией, роль посредника переходит от одного участника к другому. Ну и мой способ шифрования конечно очень детский. Теперь, я думаю, можно поместить решение в открытом виде.
Решение: Решается она след. образом, причем не только для 3-х, а для любого числа человек, с оговоркой, что участники этого круглого стола могут закрывать уши и соответсвенно не слышать друг-друга. 1-й загадывает произвольное число х, 3-й закрывает уши и 1-й сообщает это число 2-му. Далее, уши закрывает первый, а второй добавляет свою зарплату к х и сообщает эту сумму 3-му, потом уши закрывает второй и третий делится полученным результатом с первым. Тот добавляет свою зарплату, отнимает х и делит на 3. Все. Противоречий вроде нет, каждый знает только сумму зарплат двух других собеседников.