У софьи есть семь подруг: алина, бэлла, вика, галя, дана, елена, жанна. их фотографии (всего 7 штук

[Tor]

Как подойти к решению этой задачи 7 класса: - у софьи есть семь подруг: алина, бэлла, вика, галя, дана, елена, жанна. их фотографии (всего 7 штук — по одной на каждую подругу) лежат у софьи в двух стопках в случайном порядке. за один ход софья берёт несколько (одну или более) подряд лежащих фотографий с верха любой стопки и, не меняя порядка, кладёт их сверху другой стопки. всегда ли софья, сделав не более 13 ходов, сможет сложить фотографии всех подруг в одну стопку, упорядоченную по алфавиту их имён (считая снизу вверх)?

 

[Филипп]

Для решения этой задачи мы можем использовать свойства перестановок и последовательностей. Сначала давай поймем, что у нас есть 7 фотографий, которые нужно упорядочить по алфавиту. Начальная последовательность фотографий может быть произвольной, и мы можем использовать два стека для их управления. Действия Софьи позволяют ей перемещать подряд лежащие фотографии с одной стопки на другую, сохраняя их порядок. Это значит, что она может брать любые группы фотографий и менять их местами между двумя стопками. Теперь, чтобы упорядочить фотографии, Софье нужно будет: 1. Перемещать фотографии так, чтобы они постепенно собирались в правильном порядке. 2. Использовать не более 13 ходов. В общем случае, для любого порядка фотографий можно доказать, что существует способ упорядочить их, используя два стека и не более чем 7 ходов. На практике, в зависимости от начального порядка, может потребоваться больше ходов, но 13 ходов — это более чем достаточно для упорядочивания 7 фотографий. Таким образом, да, Софья всегда сможет сложить фотографии всех подруг в одну стопку, упорядоченную по алфавиту их имён, сделав не более 13 ходов.