Задача 97983

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

Сложность: 4 Классы: 9,10,11

Условие

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

Числа  1, 2, 3, ..., n  записываются в некотором порядке:  a₁, a₂, a₃, ..., a_n.  Берётся сумма  S = ^a₁/₁ + ^a₂/₂ + ... + ^a_n/_n.  Найдите такое n, чтобы среди таких сумм (при всевозможных перестановках  a₁, a₂, a₃, ..., a_n)  встретились все целые числа от 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.

Замечания

3 балла

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

олимпиада
Название	Турнир городов
Турнир
Дата	1988/1989
Номер	10
вариант
Вариант	осенний тур, основной вариант, 7-8 класс
Задача
Номер	3