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


Содержание

ММ8

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

Последовательность задана по правилу:
f(n) = -1, если n mod 53 = 0
f(n) = n (mod (n mod 53)), в остальных слyчаях

1. Каков maximum значений f(n) (1 балл)
2. При каком наименьшем n достигается maximum. (1 балл)
3. Какое максимальное количество единиц, идyщих подряд, встречается в этой последовательности. (3 балла)
4. Какие числа встречаются в последовательности чаще чем -1? (3 балла)

Решение

1-2.
Очевидно, n (mod 53) ≤ 52, откуда f(n) ≤ 51.
Для того, чтобы f(n) в точности равнялось 51, необходимо и достаточно выполнение двух сравнений: n ≡ 52 (mod 53) и n ≡ 51 (mod 52).
По китайской теореме об остатках (она не последний раз применяется при разборе данной задачи) среди чисел, не превосходящих 52*53, есть ровно одно удовлетворяющее двум вышеприведенным сравнениям. Ясно, что это 53*52-1 = 2755. Оно то и есть наименьшее n, для которого f(n) = 51.

3.
Ясно, что последовательность не может содержать более 51-й единицы подряд, поскольку каждый 53-й член последовательности равен -1, а следующий за ним - 0.
Покажем, 51 единица подряд обязательно встретится.
Пусть L = НОК[2,..52]. По китайской теореме об остатках найдется n такое, что n == 1 (mod 53), n == 2 (mod L). (Наименьшее подходящее n равно 130159869178331861668802.)
Тогда:
f(n+1) = n+1 (mod 2) = 3 mod 2 = 1.
f(n+2) = n+2 (mod 3) = 4 mod 3 = 1.
. . . . . . . . . . . . .
f(n+51) = n+51 (mod 52) = 53 mod 52 = 1.

4.
Прежде всего заметим, что последовательность f(n) является периодической. Наименьший период равен НОК[2,..53] = 164249358725037825439200 (я специально взял последовательность с достаточно большим периодом, чтобы сделать неэффективной подмену решения с помощью рассуждений компьютерным перебором).
В силу периодичности, понятие 'чаще' имеет вполне прозрачный смысл (вопреки мнению некоторых критиков, давших, кстати, вполне корректное толкование этому понятию и для последовательностей, не имеющих периода).
Ясно, что -1 встречается с частотой 1/53.
Выясним частоту появления числа s из диапазона [0..51].
Пусть x ≡ t (mod 53). Для того, чтобы в класс вычетов по модулю 53, порожденный t, попали такие n, что f(n) = s, необходимо, чтобы t было больше s.
Числа x, x+53,… x+53(t-1) образуют полную систему вычетов по модулю t. Поэтому среди них есть в точности одно y такое, что f(y) = s.
Значит частота, появления s в классе t, равна 1/t, а представители этого класса, естественно, встречаются с частотой 1/53.
Суммируя по всем t из диапазона [s+1..52] получаем, что частота появления s в нашей последовательности равна (1/(s+1)+…+1/52)/53.
Понятно, что чаще, чем -1, встречаются те s, для которых 1/(s+1)+…+1/52 больше 1. Простой подсчет показывает, что этому соотношению удовлетворяют все s из диапазона [0..18] и только они.

Обсуждение

Понятно, что число 53 не является особенным. Если заметить его любым другим простым числом p, то мы получим примерно те же ответы на поставленные вопросы. А именно:
Максимум значений f(n) равен p-2 и впервые достигается при n = p(p-1)-1.
Максимальное число единиц, идущих подряд, равно p-2. Более обще - максимальное число одинаковых значений s, идущих подряд равно p-1-s и такой набор встречается ровно один раз на каждом периоде.
Если в качестве модуля рассмотреть составное число m, то некоторые результаты претерпят изменения. Так, максимальное число единиц, идущих подряд, станет равно q-1, где q - наименьший простой делитель m.
Частота появления в последовательности различных неотрицательных чисел в случае составного модуля перестанет монотонно убывать с ростом этих чисел. Числа, не взаимно простые с модулем, будут встречаться чаще чем взаимно простые (это понятно, поскольку, если НОД(n,m) = d > 1, то f(n) обязательно будет кратно d, но и в случае, когда m и n взаимно просты, f(n) все равно может оказаться кратно d).

Награды

На 8-ю задачу получено рекордное количество ответов - шесть!
За полное правильное решение задачи (кто бы сомневался!) Макс Алексеев получает 8 призовых баллов.
Лидер марафона Борис Бух также получает 8 призовых баллов (по 1 за первые два пункта, 3 - за третий пункт, 1 - за соображения по четвертому пункту и 2 дополнительных за решение обобщенной задачи).
Павел Егоров получает 7 призовых баллов (1 балл изъят за невнятность в изложении и некоторую погрешность в ответе третьего пункта).
Олег Андрушко получает 3 призовых балла (за решение первых двух пунктов и верные соображения по четвертому).
Вячеслав Пономарев получает 2 призовых балла (решены первые два пункта).
Маша Никулина получает 2 призовых балла (она тоже справилась с первыми двумя пунктами).


 

 


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

marathon/problem_8.txt · Последние изменения: 2015/10/04 17:12 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006