. Шарики в коробках 1. Имеется несколько коробок, пронумерованных цифрами от 1 до N, и набор шариков, также пронумерованных цифрами от 1 до N. - вопрос №2156525

Шарики разложены по коробкам так, что в каждой коробке находится ровно один шар. Запись (n1, n2, ...., nN) означает, что в коробке с номером 1 лежит шарик с номером n1, в коробке с номером 2 лежит шарик с номером n2 и т.д. Например, (1, 3, 2) означает, что имеется 3 коробки и в коробке с номером 1 лежит шар с номером 1, в коробке с номером 2 лежит шар с номером 3, а в коробке с номером 3 лежит шар с номером 2. Разложение шаров по коробкам вида (1, 2, 3,...., N) называется правильным. За один ход разрешается поменять местами два любых шара. Изучите следующие вопросы: 1.1. Возможно ли за несколько ходов из разложения (4, 3, 5, 1, 2) получить правильное разложение? 1.2. Опишите все возможные разложения, которые можно получить из разложения (4, 3, 5, 1, 2). 1.3. Любое ли разложение шаров по 5 коробкам можно за несколько ходов сделать правильным? 1.4. Верно ли что из любого разложения шаров по 5 коробкам можно получить любое другое разложение? 1.5. Возможно ли за 40 ходов из набора (5, 3, 1, 4, 2) получить набор a) (3, 4, 5, 1, 2); б) (2, 1, 5, 3, 4)? 1.6. Попробуйте оценить количество различных ходов, которое потребуется, чтобы произвольное разложение (a1, a2, a3, a4, a5) шаров по 5 коробкам сделать правильным, если это возможно (ответ должен зависеть от расположения переменных ak). Единственна ли последовательность различных ходов, с помощью которой некоторое фиксированное разложение шаров по 5 коробкам можно сделать правильным? 1.7. Попробуйте оценить количество различных ходов, необходимое для того, чтобы произвольное разложение (a1, a2, a3, a4, a5) шаров по 5 коробкам сделать разложением вида a) (5, 4, 3, 2, 1); б) (5, 1, 4, 2, 3). 1.8. Попробуйте описать множество различных разложений шаров по 5 коробкам, которое можно получить из некоторого фиксированного разложения (a1, a2, a3, a4, a5) за a) три хода; б) четыре хода; в) k ходов. 2. Рассмотрите аналогичные вопросы для произвольного числа коробок N. 3. Пусть теперь в условиях пункта 1 за один ход разрешается сделать следующее: в произвольном порядке выбрать три коробки и переложить содержимое первой выбранной коробки во вторую, второй выбранной коробки в третью, а третьей выбранной коробки в первую. Рассмотрите вопросы пунктов 1 и 2 в этом случае. 4. Пусть в условиях пункта 1 за один ход разрешается сделать следующее: в произвольном порядке выбрать m коробок с номерами i1, i2, ..., im и переложить содержимое коробки с номером i1 в коробку с номером i2, коробки с номером i2 в коробку с номером i3, ..., коробки с номером im в коробку с номером i1. Назовем такую операцию произвольным циклическим сдвигом m коробок. Рассмотрите вопросы пунктов 1 и 2 в этом случае. 5. Рассмотрите случай, когда в условиях пункта 4 номера выбранных коробок i1, i2, ..., im должны быть упорядочены a) по возрастанию (назовем такую операцию прямым циклическим сдвигом m коробок); б) по убыванию (назовем такую операцию обратным циклическим сдвигом m коробок). 6. Пусть дан некоторый набор различных натуральных чисел M = {m1, m2,…, mk}, 1 ≤ mi ≤ N. За один ход разрешается выбрать одно из чисел mi и совершить a) произвольный циклический сдвиг mi коробок; b) прямой циклический сдвиг mi коробок; с) обратный циклический сдвиг mi коробок. Рассмотрите вопросы пунктов 1 и 2 для произвольного набора чисел M или хотя бы для некоторых наборов: 6.1. M = {2, 3}; 6.2. M состоит из всех четных натуральных чисел, не превосходящих N; 6.3. M состоит из всех нечетных натуральных чисел, не превосходящих N; 6.4. M состоит из всех натуральных чисел, делящихся на 3 и не превосходящих N; 6.5. M состоит из всех натуральных чисел, делящихся на t и не превосходящих N; 7. Предложите и рассмотрите различные обобщения этой задачи.

октябрь 9, 2016 г.