Один с сошкой, а семеро с ложкой

[wpoms.]

В компании, управляемой несколькими директорами, есть сейф, закрываемый на шесть замков. У каждого директора есть три ключа, которыми он может открыть три разные замка. Каждый ключ может открыть ровно один замок. Нет двух директоров, ключи которых могут открыть одни и те же три замка, и никакие два директора не могут вместе открыть сейф. Сколько директоров работают в компании?

@темы: Дискретная математика

Comments

[Unfreetoker]

Найдём максимальное количество директоров. Каждая комбинация ключей уникальна, т.к. нет директоров, у которых наборы ключей совпадают. Также каждая комбинация ключей "блокирует" ровно одну комплементарную ей комбинацию (например, если есть комбинация 1, 2, 3, то комбинации 4, 5, 6 нет, иначе они могли бы вдвоём открыть сейф). Получается, что всего директоров не больше 6*5*4/(3*2*1)/2 = 10 человек.

[sexstant]

19

[sexstant]

Пусть номера ключей от 1 до 6.
У первого директора набор (1,2,3)
У следующих 9 два ключа как у первого:
(1,2,4), (1,2,5),(1,2,6)
(1,3,4), (1,3,5),(1,3,6)
(2,3,4), (2,3,5),(2,3,6)
У следующих 9 один ключ как у первого:
(1,4,5), (1,4,6),(1,5,6)
(2,4,5), (2,4,6),(2,5,6)
(3,4,5), (3,4,6),(3,5,6)

[All_ex]

sexstant, У следующих 9 два ключа как у первого: (1,2,4) .... У следующих 9 один ключ как у первого:,(3,5,6)
Вроде эти вдвоём откроют сейф...

[вейко]

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

1-2-3, 2-3-4, 1-5-6 ну например 3 директора

[All_ex]

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

С другой стороны в условии не сказано, что какой-нибудь набор директоров может открыть этот сейф...