Под ёлку положили подарки для 12 детей. Каждый подарок был подписан именем: Алиса, Боря, Ваня, Гена, Дима, Женя, Зоя, Коля, Лена, Миша, Наташа, Оля. Ваня тайком зашёл к ёлке, и…
Под ёлку положили подарки для 12 детей. Каждый подарок был подписан именем: Алиса, Боря, Ваня, Гена, Дима, Женя, Зоя, Коля, Лена, Миша, Наташа, Оля. Ваня тайком зашёл к ёлке, и спрятал один из подарков (в той же комнате). Потом каждый из детей поодиночке тайком заходил в эту комнату. Если его подарок лежал под ёлкой, он прятал один чей-нибудь подарок. А если его подарка под ёлкой не было, он находил его, возвращал под ёлку и выходил из комнаты. Какое наименьшее число подарков могло лежать под ёлкой после того, как все дети зашли по одному разy?
Разберемся с ситуацией по порядку. Изначально под ёлкой лежали 12 подарков. Ваня спрятал один из подарков, и теперь под ёлкой осталось 11 подарков.
Когда каждый из остальных 11 детей заходит поочередно, у них есть два варианта развития событий:
- Если подарок ребенка под ёлкой (то есть подарок его имени), он прячет один из оставшихся подарков, которые не его.
- Если подарок ребенка не под ёлкой, он возвращает свой подарок под ёлку и уходит.
В конечном итоге мы хотим узнать, какое наименьшее количество подарков может остаться под ёлкой после того, как все 11 детей зайдут в комнату.
Для минимизации количества подарков под ёлкой, есть следующая ситуация:
- Ваня, усевшись за дела, спрятал какой-либо подарок, оставив под ёлкой 11.
- Каждый из других 11 детей, если их подарок (т.е. подарок с их именем) под ёлкой, имеет возможность продолжать прятать другие подарки. Построим сценарий, при котором все дети, кроме одного, найдут свои подарки и вернут их под ёлку, самостоятельно не оставляя сильно уменьшенное количество подарков.
Только один ребенок, назовем его "Р", возможно situation, при которой Р не находит свой подарок под ёлкой, вернет его и покинет комнату. Таким образом:
- В результате, если 10 детей находят свои подарки и прячут оставшиеся, а только один не находит свой подарок, то в конце мы можем сохранить 2 подарка под ёлкой (подарок Р и один случайный, который кто-то из детей спрятал).
Таким образом, наименьшее количество подарков, которые могут остаться под ёлкой после того, как все 11 детей заходят в комнату, составляет 2.
