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

[karandash_oleg]

В доме $40$ комнат, которые открываются ключами $5$ разных видов, причем количество ключей разных видов различно. Все
$40$ ключей оказались заперты в комнатах, так, что в каждой комнате заперт один ключ, которым эту комнату открыть нельзя. Сторож
Сергеев имеет дубликат ключа от одной из комнат. Докажите, что он может открыть все комнаты.

У нас есть $5$ множеств ключей $A,B,C,D,E$. Нам нужно представить число $40$ суммой различных натуральных чисел. Надо подумать как именно.

$40=15+9+6+5+3+2$, $40=15+9+6+5+4+1$, $40=14+10+6+5+3+2$, $40=13+11+6+5+3+2$, $40=15+9+6+5+4+1$....

Куча вариантов получается, как упростить перебор?))

[slavav]

Зачем перебирать? Попробуйте обойтись без перебора.

[karandash_oleg]

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

Зачем перебирать? Попробуйте обойтись без перебора.

От безысходности. А как можно без перебора? Пока что не очевидно -- с чего начать.

[slavav]

У нас есть пять типов комнат. Ясно, что если есть какие-то ключи на руках, то можно открыть все комнаты с типами этих ключей.
От противного: предположим, что не удалось открыть все комнаты. Это значит какие-то типы комнат открыты, какие-то остались закрыты.

Начнём с простого частного случая: может ли быть чтобы мы открыли ровно четыре типа комнат а пятый тип остался заперт?

[karandash_oleg]

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

У нас есть пять типов комнат. Ясно, что если есть какие-то ключи на руках, то можно открыть все комнаты с типами этих ключей.
От противного: предположим, что не удалось открыть все комнаты. Это значит какие-то типы комнат открыты, какие-то остались закрыты.

Начнём с простого частного случая: может ли быть чтобы мы открыли ровно четыре типа комнат а пятый тип остался заперт?

Не может, потому как в комнатах 1-4 типа есть ключи от комнат 5 типа! Причем от всех. Ну а если рассмотреть частный случай, когда мы открыли 3 типа комнат, то тогда еще нет гарантии, что мы откроем комнаты 4-5 типа, так как в комнатах 4 типа могут быть ключи от комнат 5 типа, а в комнатах 5 типа могут быть ключи от комнат 4 типа.

[slavav]

Точно также мы можем исключить случай когда открыт только один тип.
Остались случаи:
2 открыто, 3 - нет (2-3)
3 открыто, 2 - нет (3-2)

Что вы скажете про случай 2-3 ?

[karandash_oleg]

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

Точно также мы можем исключить случай когда открыт только один тип.
Остались случаи:
2 открыто, 3 - нет (2-3)
3 открыто, 2 - нет (3-2)

Что вы скажете про случай 2-3 ?

Спасибо!
А, как раз для этого и дано, что разное число ключей определенного типа, нужно подумать еще!

[slavav]

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

Не может, потому как в комнатах 1-4 типа есть ключи от комнат 5 типа!

Обоснуйте подробнее, пожалуйста.

[DanilovV]

Если пойти с конца, то каким ключом закрывали последнюю комнату?
Дубликатом ключа сторожа Сергеева?
Идем в обратном порядке закрывания комнат. Тогда непонятно причем тут 5 типов ключей и что их количество различно?
Может нужно доказать что при таких исходных данных комнаты можно закрыть?

[slavav]

Порядок закрытия не имеет отношения к задаче.

[Begemot82]

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

Порядок закрытия не имеет отношения к задаче.

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

[slavav]

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

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

Порядок закрытия не имеет отношения к задаче.

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

Их закрывали дубликатами всех ключей, потом все дубликаты спрятали, один оставили.
Двери монтировали запертыми, ключи уже лежали в комнатах.
Двери заперли, ключи бросили в комнаты через оконца, щели в дверях.
И ещё масса вариантов.
Порядок закрытия не имеет отношения к задаче.

[karandash_oleg]

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

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

Не может, потому как в комнатах 1-4 типа есть ключи от комнат 5 типа!

Обоснуйте подробнее, пожалуйста.

Так как в комнате 5 не может быть ключей 5 типа, поэтому эти ключи в 1-4 комнатах!

[Begemot82]

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

[karandash_oleg]

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

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

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