Задача о трех программистах

[geevee]

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

Вопрос: как им узнать среднюю зарплату, не нарушая соглашение о неразглашении, и не прибегая к помощи постороннего доверенного

Comments

[vancir]

Каждый программист загадывает одно из чисел 1, 2, -3. Пишут на доске число, равное своей зарплате+загаданное. Считают среднее. Потом то же самое повторяют для чисел 10, 20, -30. И так далее. Если на доске появится одно и то же число два раза, оно и будет средним арифметическим...Ну это конечно не будет работать если все будут загадывать одно и то же число каждый раз) правда вероятность этого равна нулю.
вообще, решение какое-то простое?)

[geevee]

Пусть первый имеет зарплату X. Он пишет на доске число X1, отстоящее от X не более чем на 3.

На второй итерации он пишет на доске число X2. Второй программист смотрит на число X2. Зная его, он знает, что X равно либо X2 − 10, либо X2 − 20, либо X2 + 30. Ровно одно из этих чисел отстоит от X1 на 3 или меньше - это и есть значение зарплаты первого программиста.

[geevee]

:)

[geevee]

Да, могут пользоваться бумажкой. И шептать на ухо тоже могут.

арифметика в конечных полях по модулю простых чисел ру

[oxij]

а тебя интересует решение с использованием NP-полноты или из класса IP (интерактивный прувер)? :3

Re: арифметика в конечных полях по модулю простых чисел

[geevee]

Я стыдливо промолчу.

[sasha_utkin]

пропить три зарплаты в одном баре, сумму по чекам сложить и разделить на три

[geevee]

Кто будет считать сумму по чекам? Бармен? Тогда он по сути доверенное лицо.

Но попытка хорошая, да :)