Ключи, комнаты.

[Begemot82]

karandash_oleg в сообщении #1038974 писал(а):

Begemot82 в сообщении #1038971 писал(а):

Считаем, что у сторожа ключ типа 1.
Пусть есть 3 комнаты, одна открываемая ключом типа 1, две ключом типа 2. Остальные открываются ключами типа 3, 4, 5.
Открываем комнату, там ключ типа 2, открываем еще две комнаты, там ключи типа 1.
Тупик, остальные комнаты не открываются.

А как может быть несколько ключей типа 1, если комната всего одна?

В условии

Цитата:

количество ключей разных видов различно

но не говориться что не равно 1, значит может быть одна комната.
Если надо больше, пусть будет два ключа типа 1 и три ключа типа 2

[slavav]

В вашем примере одна комната первого типа и два ключа первого типа. А из условия комнат первого типа столько же сколько ключей первого типа.

[karandash_oleg]

Что-то Бегемот меня запутал))

[Begemot82]

slavav в сообщении #1038979 писал(а):

В вашем примере одна комната первого типа и два ключа первого типа. А из условия комнат первого типа столько же сколько ключей первого типа.

Понял.
Тянем цепочку дальше. Ключом типа 1 открыли комнату с ключом типа 2. Ключами типа 1 и 2 открыли все комнаты типа 1 и 2.
Осталось доказать, что в комнатах двух типов обязательно есть ключ третьего типа.
Затем, что среди комнат трех типов будет ключ от комнат 4 или 5 типа ( в комнатах 4 и 5 не могут находиться все ключи 4 и 5 типа )

[karandash_oleg]

Пока что я не понял целостно вашу подсказку, Begemot82!
Комната-таки первого типа в вашем примере -- одна или нет?

[Begemot82]

karandash_oleg в сообщении #1038984 писал(а):

Что-то Бегемот меня запутал))

Извините. Тогда мои сообщения пропускайте.

[levtsn]

Если осталось только два типа запертых комнат то ключи должны лежать в комнате другого типа а по условию их разное количество. Если осталось три типа запертых то первые два типа хранят друг друга что запрещено. Таким образом невозможно чтобы осталось какое то количество не открытых комнат.

[slavav]

Согласен.
Для полноты картины можно привести пример неполного открытия комнат если типов комнат - шесть.

[levtsn]

Если шесть то остаётся три типа например 1 2 и 3 открываемые и не открываемые три типа 10 7 и 17 штук в 6 типе лежат ключи 5 и 6
4 типа а в 5 и 4 ключи 6типа.

[karandash_oleg]

levtsn в сообщении #1038999 писал(а):

Если осталось три типа запертых то первые два типа хранят друг друга что запрещено.

А почему запрещено? Пока что не могу понять.

[slavav]

Два типа, которые ссылаются только на друг друга. На себя тип ссылаться не может. Значит дверь одного типа содержит ключ второго типа. И наоборот. Ключей первого типа столько же сколько дверей первого типа. Все ключи первого типа лежат за дверьми второго типа.
$K_1 = D_1$ Ключей первого типа столько же сколько дверей первого типа.
$K_1 = D_2$ Все ключи первого типа лежат за дверьми второго типа. И двери второго типа содержат только ключи первого типа.

[karandash_oleg]

slavav , спасибо. Теперь понятно -- почему запрещено. А именно потому как из условия $K_1\ne K_2$, а значит$D_1=K_1\ne K_2=D_2$.

levtsn так лаконично изложил (это хорошо, у меня так не получается лаконично и грамотно излагать мысли), но пока на меня действует побочный эффект лаконичности (в эти две строчки уже очень долго не получается вникнуть( )

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

Цитата:

Если осталось только два типа запертых комнат то ключи должны лежать в комнате другого типа а по условию их разное количество. Если осталось три типа запертых то первые два типа хранят друг друга что запрещено. Таким образом невозможно чтобы осталось какое то количество не открытых комнат.

А как из первых двух предложений следует третье? Пока что совсем не очевидно это

[slavav]

Вариант 0-5 исключён ( у нас есть дубликат). Варианты 1-4, 2-3, 3-2, 4-1 мы исключили. Следовательно, возможен только 5-0 (все типы дверей открыты).

[karandash_oleg]

slavav в сообщении #1039222 писал(а):

Вариант 0-5 исключён ( у нас есть дубликат). Варианты 1-4, 2-3, 3-2, 4-1 мы исключили. Следовательно, возможен только 5-0 (все типы дверей открыты).

Спасибо. Почти все понятно, кроме двух вещей.
1) Почему исключается вариант 1-4. Да, мы можем открыть двери одного типа, потом набрать ключей другого типа, чтобы открывать другие двери, но разве не может быть такой расклад?
2) Почему нет промежуточных вариантов? Когда открыты не все двери трех типов. То есть 2 из 4 типа $D_1$, 3 из 5 $D_2$...

[slavav]

1-4 исключён так как за дверьми первого типа хранятся ключи других типов.
Если у вас ключ определённого типа, то вы сразу открываете все двери этого типа.