Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

ММ36

Конкурсная задача ММ36 (5 баллов)

Функция f сопоставляет каждому натуральному числу n сумму остатков от деления n на все натуральные числа, меньшие n.
1) описать все такие n, для которых f(n) = n; (2 балла)
2) Доказать, что для любого натурального k f(2k) = f(2k - 1). (3 балла)

Решение

1) Ясно, что если k превышает половину n, то n mod k = n - k.
Поэтому за исключением нескольких начальных значений n
f(n) > 1 + 2 + … + [(n-1)/2] ([x] означает целую часть числа x).
При n больших 10 эта сумма, а значит и f(n), больше n.
Подсчитывая f(n) для n, не превосходящих 10, находим, что единственным числом, для которого f(n) = n, является 8.

2) Обозначим s =2k. Разобьем натуральные числа, не превосходящие 2k - 1 на группы, каждая из которых начинается числом 2t и заканчивается числом 2t+1 -1 (для t = 0,1,…,k-1).
Количество чисел в t-той группе - 2t.
Остаток от деления s-1 на первое число t-той группы равен 2t - 1, а s делится на первое число группы без остатка. Остатки от деления s-1 на каждое из последующих 2t - 1 чисел t-той группы на 1 меньше остатка от деления s на то же число. Таким образом, в каждой группе суммы остатков для s и s-1 равны. Следовательно, f(s) = f(s-1).

Обсуждение

Некоторые дополнительные сведения о последовательности, описанной в данной задаче, (как и о многих других » марафонских» последовательностях) можно почерпнуть в онлайн-энциклопедии целочисленных последовательностей. Наша последовательность представлена там за номером A004125.

Гипотеза, что за исключением случая, описанного во втором пункте ММ36, значения f(n) не повторяются, не подтвердилась. Вот несколько контрпримеров, найденных Юрием Макарычевым:
m = 38183, n = 38185: f(m) = f(n) = 258840858
m = 458009, n = 458011: f(m) = f(n) = 37241677057
m = 776111, n = 776113: f(m) = f(n) = 106936975149
m = 65676407, n= 65676409: f(m) = f(n) = 765769022511763.

Награды

За правильное решение этой задачи Влад Франк, Мигель Митрофанов и Иван Козначеев получают по 5 призовых баллов. Антон Филиппов получает 2 призовых балла за правильное решение первого пункта.


 

 


Страница: [[marathon:problem_36]]

marathon/problem_36.txt · Последние изменения: 2018/10/23 01:03 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006