ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Задачи

Страница: << 1 2 3 >> [Всего задач: 13]      



Задача 97936

 [Обмены квартир]
Темы:   [ Разложение в произведение транспозиций и циклов ]
[ Композиции симметрий ]
[ Группа перестановок ]
Сложность: 3+
Классы: 8,9,10

В некотором городе разрешаются только парные обмены квартир (если две семьи обмениваются квартирами, то в тот же день они не имеют права участвовать в другом обмене). Докажите, что любой сложный обмен квартирами можно осуществить за два дня.
(Предполагается, что при любых обменах каждая семья как до, так и после обмена занимает одну квартиру, и что семьи при этом сохраняются).

Решение

Сложный обмен квартир представляет собой цикл. Представим его в виде поворота правильного многоугольника, вершины которого соответствуют участвующим в обмене квартирам. Этот поворот есть композиция двух осевых симметрий (относительно серединных перпендикуляров к двум соседним сторонам). Каждая осевая симметрия задаёт несколько парных обменов; все их можно осуществить за один день.

Прислать комментарий

Задача 111804

Темы:   [ Разложение в произведение транспозиций и циклов ]
[ Индукция (прочее) ]
[ Принцип крайнего (прочее) ]
[ Процессы и операции ]
Сложность: 4-
Классы: 8,9,10

В очереди к стоматологу стоят 30 ребят: мальчиков и девочек. Часы на стене показывают 8:00. Как только начинается новая минута, каждый мальчик, за которым стоит девочка, пропускает её вперед. Докажите, что перестановки в очереди закончатся до 8:30, когда откроется дверь кабинета.

Решение

  Докажем индукцией по n, что для очереди из n ребят через  n – 1  минуту получится расстановка, которую назовём правильной: в начале очереди все девочки, а потом все мальчики. База для одного пациента очевидна – перестановок в очереди не будет вообще.
  Шаг индукции. Если в очереди нет девочек, то утверждение очевидно. Пусть девочки есть. Рассмотрим самую первую девочку D в очереди. Если перед ней нет мальчиков, то она не участвует в перестановках, и по предположению индукции (D можно мысленно убрать) через  n – 2  минуты получится правильная расстановка. Если же перед D есть мальчики, то рассмотрим ситуацию через минуту: за D будет стоять мальчик; далее D каждую минуту перемещается на одну позицию вперед, пока не окажется в начале очереди, а остальные девочки меняются так, как будто девочки D нет в очереди. (Действительно, D может помешать девочке D' поменяться с мальчиком только в случае, если D' стоит точно за D; но если за D стоит девочка, значит, в предыдущую минуту D не менялась местами, и они стоят в начале очереди.) Таким образом, по предположению индукции ещё через  n – 2  минуты все остальные девочки выстроятся впереди мальчиков вслед за D, то есть получится правильная расстановка.

Прислать комментарий

Задача 78627

Темы:   [ Разложение в произведение транспозиций и циклов ]
[ Процессы и операции ]
Сложность: 4-
Классы: 8,9,10

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

Решение

  Занумеруем портреты королей по порядку их царствования: 1, 2,..., n. Покажем, как королю из любого исходного расположения портретов получить порядок 1, 2,..., n по часовой стрелке (назовём такой порядок стандартным). Подгоним сначала первый портрет ко второму (двигая первый по часовой стрелке). Мы сможем это сделать, так как первый портрет можно менять с любым, кроме второго. После этого будем двигать портреты 1 и 2 вместе, пока не подгоним их к третьему, и т. д. В результате получим стандартный порядок.
  Заметим, что мы заодно научились получать из стандартного порядка любой другой порядок. Действительно, для этого достаточно проделать перевешивания, приводящие конечный порядок к стандартному, но в обратном порядке. Теперь уже несложно получить из любого порядка любой другой: надо сначала из исходного порядка получить стандартный, а потом из него получить конечный порядок.

Прислать комментарий

Задача 97762

Темы:   [ Разложение в произведение транспозиций и циклов ]
[ Перебор случаев ]
[ Делимость чисел. Общие свойства ]
Сложность: 4
Классы: 9,10,11

Автор: Фольклор

a1, a2, ..., a101  – такая перестановка чисел  2, 3, ..., 102,  что ak делится на k при каждом k. Найти все такие перестановки.

Решение

  Добавим  а102 = 1.  Мы получили подстановку на множестве  {1, 2, ..., 102}.  Она распадается на циклы. Но наименьшее число нетривиального (содержащего более одного числа) цикла стоит на месте с номером, большим самого числа. По условию таким числом может быть только 1, следовательно, нетривиальный цикл только один (и состоит из некоторых делителей числа 102, каждый из которых является делителем следующего), а остальные циклы тривиальны. Вот все варианты нетривиальных циклов (их 13):
  (1, 102),  (1, 2, 102),  (1, 3, 102),  (1, 6, 102),  (1, 17, 102),  (1, 34, 102),  (1, 51, 102),  (1, 2, 6, 102),  (1, 2, 34, 102),  (1, 3, 6, 102),  (1, 3, 51, 102),
(1, 17, 34, 102),  (1, 17, 51, 102).

Прислать комментарий

Задача 97983

Темы:   [ Разложение в произведение транспозиций и циклов ]
[ Полуинварианты ]
[ Суммы числовых последовательностей и ряды разностей ]
Сложность: 4
Классы: 9,10,11

Автор: Фольклор

Числа  1, 2, 3, ..., n  записываются в некотором порядке:  a1, a2, a3, ..., an.  Берётся сумма  S = a1/1 + a2/2 + ... + an/n.  Найдите такое n, чтобы среди таких сумм (при всевозможных перестановках  a1, a2, a3, ..., an)  встретились все целые числа от n до  n + 100.

 

Решение

Записав числа по порядку, получим  S = n.  Перестановка k и 2k увеличивает S на  2k/k + k/2k – 2 = ½.  При  n = 798  мы имеем 200 непересекающихся пар вида  {k, 2k}:  {1, 2},  {3, 6},  ...,  {399, 798}.

Ответ

Например,  n = 798.

Прислать комментарий

Страница: << 1 2 3 >> [Всего задач: 13]      



© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .