Константин Кноп (knop) wrote,
Константин Кноп
knop

Category:

Честная раздача карт без современной криптографии

Мне сегодня с двух разных сторон подкинули две похожие околокарточные математические задачи, и я понял, что таки пора...

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

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

Дополнительные условия:
1) компьютеры "честные", т.е. никто из них не нарушет выбранный протокол; в частности, ни один из компьютеров не пытается "сговориться" с другими против кого-либо.
2) компьютеры ничего не забывают;
3) каждый из компьютеров может решить сколь угодно сложную математическую задачу (иначе говоря, понятие "криптографической стойкости" для них абсолютно, а если задача в принципе решается, они ее решат и все что надо вычислят).

Комменты с верными решениями и существенными идеями будут оставаться скрытыми.
Tags: Задачи, Математика
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 25 comments