Задача про разделение секрета.

deniskostin · Сообщение **deniskostin** » 30 апр 2014, 14:45

Группа состоит из 12 чел. Секрет группы хранится в сейфе. Необходимо, чтобы доступ к сейфу был возможен тогда и только тогда, когда соберутся не менее 10 членов группы.
Нужно ответить на вопросы:
1) сколько замков должен иметь сейф?
2) сколько ключей нужно для них изготовить?
3) Как разделить ключи между членами группы (сколько в итоге ключей будет иметь каждый член группы) ?

arojda1 · Сообщение **arojda1** » 01 май 2014, 05:21

deniskostin писал(а):Source of the post
Группа состоит из 12 чел. Секрет группы хранится в сейфе. Необходимо, чтобы доступ к сейфу был возможен тогда и только тогда, когда соберутся не менее 10 членов группы.
Нужно ответить на вопросы:
1) сколько замков должен иметь сейф?
2) сколько ключей нужно для них изготовить?
3) Как разделить ключи между членами группы (сколько в итоге ключей будет иметь каждый член группы) ?

С из 12 по 3 замков повесь и каждой из троек ключи раздай (т.е. по 3 ключа на замок). Тогда любая тройка из 12 может своим отсутствием наложить вето на открытие дверей. Сколько ключей у каждого будет, уж сам посчитай.

ARRY · Сообщение **ARRY** » 01 май 2014, 18:52

arojda1 писал(а):Source of the post
Тогда любая тройка из 12 может своим отсутствием наложить вето на открытие дверей.

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

ARRY · Сообщение **ARRY** » 06 май 2014, 17:59

ARRY писал(а):Source of the post
Ведь постановка задачи подразумевает минимизацию числа замков и ключей.
А значит нужно доказать, что у любой тройки должен быть общий и единственный ключ, и что ни у какой четвёрки такого ключа быть не может.

Прошу извинения, панове!
Чевой-то я загнул несуразное, не подумавши как следует.
Никакая минимизация здесь не при чём.
А логика, значится, вот какая:
Любые $$9$$

человек сейф открыть не могут, поскольку у них нет ключа от какого-то замка. Но любой из оставшихся $$3$$

человек этот ключ должен иметь. Значит, нужно установить $C_{12}^9$ замков.
Затем $$3$$

ключа от каждого замка надо отдать некоторым трём людям, но при этом разные ключи надо раздать разным тройкам. Стало быть, если соберутся $$10$$

человек (или более), то среди них заведомо будет представитель от каждой тройки, и они откроют все $$220$$

замков.
А в общем случае, если есть группа из $$n$$

человек, а сейф можно открыть при наличии не менее $$k$$

человек $(k\leqslant n)$ , то потребуется $C_n^{k-1}$ замков, и к каждому замку потребуется $$n-k+1$$

ключей.
Ну, как-то так.

Anik · Сообщение **Anik** » 05 июн 2014, 16:36

А почему 220 замков, мне больше нравится число 380. Замки, что амбарные (висячие)?
Интересный сейф получается, по-русски.
Можно было бы по этим данным спроектировать всего один электронный замок с 12 оригинальными ключами. У каждого пользователя всего один ключ.
А можно применить слесарный подход, без всякой электроники. Тоже один замок и 12 разных ключей, соответственно 12 замочных скважин.

ARRY · Сообщение **ARRY** » 06 июн 2014, 05:44

Anik писал(а):Source of the post
Можно было бы по этим данным спроектировать всего один электронный замок с 12 оригинальными ключами. У каждого пользователя всего один ключ.
А можно применить слесарный подход, без всякой электроники. Тоже один замок и 12 разных ключей, соответственно 12 замочных скважин.

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

Anik · Сообщение **Anik** » 06 июн 2014, 06:57

ARRY писал(а):Source of the post
Anik писал(а):Source of the post
Можно было бы по этим данным спроектировать всего один электронный замок с 12 оригинальными ключами. У каждого пользователя всего один ключ.
А можно применить слесарный подход, без всякой электроники. Тоже один замок и 12 разных ключей, соответственно 12 замочных скважин.

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

В условии не сказано, что замок должен быть висячий.
Один врезной замок с 12 механизмами открывания, типа английского замка с ключом.
1) Ключ вставляется в соответствующую скважину и поворачивается *только на пол-оборота "открыть".
2) Ключ можно вытащить из замочной скважины если он в положении "закрыть".
3) Поворот любого ключа в положение "открыть" перемещает зубчатую рейку (и вместе с ней засов) на одну десятую часть длины засова.
4) Сейф открывается если в положении "открыть" находятся десять любых ключей, при этом засов выдвинут полностью.
5) Все ключи можно вынуть при условии, что засов находится в исходном запертом положении (полностью задвинут).

yourdomain.com