Задачка про министров-взяточников

[Disprein]

За круглым столом сидят министры (коих не меньше трех) некоторого государства. Известно, что министры берут взятки, но сумму взяток для каждого министра не знает никто, кроме самого министра. И ни один министр ни за что не поделится этой информацией ни с одной живой душой, потому что это дело подсудное.
Однако глава государства потребовал от кабинета министров предоставить ему среднюю сумму взяток на одну министерскую душу.
Как действовать министрам, если все они заинтересованы в том, чтобы глава государства получил нужную ему информацию, но ни один из них не хочет раскрывать сумму своих взяток?

@темы: Головоломки и занимательные задачи

Comments

[Фабий]

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

[Garryncha]

Министры могут действовать так: первый берёт произвольное число, прибавляет к нему размер своей взятки, сумму сообщает второму, второй прибавляет размер своей взятки и сообщает сумму третьему и т.д. Когда прошли всех министров первый вычитает из общей суммы первоначально взятое им число. Т.к. министров по крайней мере трое, то слагаемых в общей сумме будет по крайней мере 4 (по одному на брата + произвольное число), так что первый, зная только произвольное число и свой размер взятки (2 слагаемых), не вычислит остальные слагаемые, а остальные — тем более. Зная общую сумму взяток, делим её на количество министров и получаем размер средней взятки. Хорошая задачка, расскажу её людям.:-)

[Trotil]

Это очень похоже про обедающих криптографов: avva.livejournal.com/1035705.html

Я взял этот ник на волне дурацкого флешмоба

Здорово придумал! Кстати, есть "затеняющая подпись" (подпись вслепую), там примерно подобный принцип.

[Disprein]

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

Я взял этот ник на волне дурацкого флешмоба, да, все верно)

[inquisitor]

Министры могут действовать так: первый берёт произвольное число, прибавляет к нему размер своей взятки, сумму сообщает второму, второй прибавляет размер своей взятки и сообщает сумму третьему и т.д. Когда прошли всех министров первый вычитает из общей суммы первоначально взятое им число.

Можно использовать операцию умножения вместо сложения и операцию извлечения корня n-ой степени вместо деления. Тогда получим среднее геометрическое.