ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
Страница: << 1 2 3 >> [Всего задач: 13]
В некотором городе разрешаются только парные обмены квартир (если две семьи
обмениваются квартирами, то в тот же день они не имеют права участвовать в
другом обмене). Докажите, что любой сложный обмен квартирами можно осуществить за два дня. РешениеСложный обмен квартир представляет собой цикл. Представим его в виде поворота правильного многоугольника, вершины которого соответствуют участвующим в обмене квартирам. Этот поворот есть композиция двух осевых симметрий (относительно серединных перпендикуляров к двум соседним сторонам). Каждая осевая симметрия задаёт несколько парных обменов; все их можно осуществить за один день.
В очереди к стоматологу стоят 30 ребят: мальчиков и девочек. Часы на стене показывают 8:00. Как только начинается новая минута, каждый мальчик, за которым стоит девочка, пропускает её вперед. Докажите, что перестановки в очереди закончатся до 8:30, когда откроется дверь кабинета. Решение Докажем индукцией по n, что для очереди из n ребят через n – 1 минуту получится расстановка, которую назовём правильной: в начале очереди все девочки, а потом все мальчики. База для одного пациента очевидна – перестановок в очереди не будет вообще.
Испанский король решил перевесить по-своему портреты своих предшественников в круглой башне замка. Однако он хочет, чтобы за один раз меняли местами только два портрета, висящие рядом, причём это не должны быть портреты двух королей, один из которых царствовал сразу после другого. Кроме того, ему важно лишь взаимное расположение портретов, и два расположения, отличающиеся поворотом круга, он считает одинаковыми. Доказать, что как бы сначала ни висели портреты, король может по этим правилам добиться любого нового их расположения. Решение Занумеруем портреты королей по порядку их царствования: 1, 2,..., n. Покажем, как королю из любого исходного расположения портретов получить порядок 1, 2,..., n по часовой стрелке (назовём такой порядок стандартным). Подгоним сначала первый портрет ко второму (двигая первый по часовой стрелке). Мы сможем это сделать, так как первый портрет можно менять с любым, кроме второго. После этого будем двигать портреты 1 и 2 вместе, пока не подгоним их к третьему, и т. д. В результате получим стандартный порядок.
a1, a2, ..., a101 – такая перестановка чисел 2, 3, ..., 102, что ak делится на k при каждом k. Найти все такие перестановки. Решение Добавим а102 = 1. Мы получили подстановку на множестве {1, 2, ..., 102}. Она распадается на циклы. Но наименьшее число нетривиального (содержащего более одного числа) цикла стоит на месте с номером, большим самого числа. По условию таким числом может быть только 1, следовательно, нетривиальный цикл только один (и состоит из некоторых делителей числа 102, каждый из которых является делителем следующего), а остальные циклы тривиальны. Вот все варианты нетривиальных циклов (их 13):
Числа 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-...
МЦНМО
(о копирайте)
|
Пишите нам
|