2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Заним. задачка
Сообщение29.08.2006, 11:56 
Аватара пользователя


24/08/06
57
Моск. обл.
Заранее сорри если задача уже решалась или она настолько известна что ее просто глупо выкладывать, но мне просто интересно есть решение отличное от моего. Итак сама задача.
Чупа from forum MPGU писал(а):
"Три человека сидят за столом. Им приходит в голову посчитать свою среднюю ЗП (на 3х), но никто не хочет говорить, сколько получает. Какой способ общения им нужно выбрать?

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


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

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

 Профиль  
                  
 
 
Сообщение29.08.2006, 12:04 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение29.08.2006, 12:14 
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение29.08.2006, 12:42 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение30.08.2006, 10:28 
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение30.08.2006, 11:00 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение30.08.2006, 19:29 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение31.08.2006, 10:11 
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group