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

Проект МЦНМО
при участии
школы 57
Задача 97993
Темы:    [ Перестановки и подстановки ]
[ Отношение порядка ]
[ Правило произведения ]
Сложность: 4-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Автор: Анджанс А.

Числа 1, 2, 3, ..., N записываются в строчку в таком порядке, что если где-то (не на первом месте) записано число i, то где-то слева от него встретится хотя бы одно из чисел  i + 1  и  i – 1.  Сколькими способами это можно сделать?


Решение

Пусть на первом месте стоит число k. Заметим, что если  k > 1,  то числа  k – 1,  k – 2, ..., 1  стоят в нашей перестановке в порядке убывания (если двигаться слева направо). Действительно, по условию левее числа 1 должно стоять 2, левее 2 – 1 или 3, то есть 3,  левее 3 – 2 или 4, то есть 4 и т. д. Аналогично, при  k < N  числа  k + 1,  k + 2,  ...,  N  стоят в порядке возрастания, так как левее N должно быть  N – 1,  левее  N – 1  – число  N – 2  и т. д. Следовательно, любая из рассматриваемых перестановок однозначно задаётся набором мест, занимаемых числами  1, 2, ...,  k – 1  (таких мест может вообще не быть, если  k = 1,  то есть для перестановки  1, 2, ..., N).  Количество этих наборов равно количеству подмножеств множества из  N – 1  элемента – всех мест, кроме первого, то есть 2N–1. По числу элементов подмножества однозначно определяется число k, стоящее на первом месте.


Ответ

2N–1 способами.

Замечания

4 балла

Источники и прецеденты использования

журнал
Название "Квант"
год
Год 1989
выпуск
Номер 6
Задача
Номер М1167
олимпиада
Название Турнир городов
Турнир
Дата 1988/1989
Номер 10
вариант
Вариант осенний тур, основной вариант, 9-10 класс
Задача
Номер 3

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

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