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


Содержание

ММ58

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

Обозначим через T(n) количество треугольников периметра n с целочисленными длинами сторон.

1) Конечно ли множество таких n, которые делят T(n)?
2) Конечно ли, множество таких n, при которых T(n) является полным квадратом?
3) Какие n встречаются чаще: те, при которых T(n) кратно 173, или те, при которых T(n) кратно 211?

Решение

Выведем формулу для подсчета T(n).

Начнем с частного случая. Пусть, например, n = 200.
Будем осуществлять перебор треугольников по возрастанию наибольшей стороны:

66, 67, 67;

64, 68, 68;
65, 67, 68;
66, 66, 68;

62, 69, 69;
63, 68, 69;
64, 67, 69;
65, 66, 69;

60, 70, 70;
61, 69, 70;
62, 68, 70;
63, 67, 70;
64, 66, 70;
65, 65, 70;

……….
2, 99, 99;
3, 98, 99;
……….
50, 51, 99.

Легко видеть, что с возрастанием самой большой стороны на 1 число треугольников поочередно возрастает то на 2, то на 1.
В самом деле, нижняя граница диапазона значений короткой стороны с увеличением длинной стороны на 1, всякий раз уменьшмется на 2 (ведь средняя сторона тоже получает дополнительное значение). В то же время, верхняя граница диапазона меньшей стороны уменьшается на 1 при переходе значения большей стороны с четного числа на нечетное и не изменяется при переходе с нечетного на четное.
Таким образом, T(200) = 1 + 3 + 4 + 6 + 7 + … + 46 + 48 + 49 =
1 + 2 + 3 + … + 49 - (2 + 5 + 8 + … + 47) = 49*25 - 49*8 = 833.

В общем случае, очевидно, картина будет аналогичной:
T(n) будет разностью двух арифметических прогрессий, в первой из которых суммируются натуральные числа от 1 до некогорого s(n), а во второй представлены члены из первой, сравнимые с n по модулю 3.
Не сложно найти и s(n).
При n = 4t максимальное значение большей стороны - 2t-1, а меньшая при этом может меняться от 2 до t. Поэтому s(4t) = t-1.
При n = 4t+1 максимальное значение большей стороны - 2t, а меньшая при этом может меняться от 1 до t. Поэтому s(4t+1) = t.
При n = 4t+2 максимальное значение большей стороны - 2t, а меньшая при этом может меняться от 2 до t+1. Поэтому s(4t) = t.
При n = 4t+3 максимальное значение большей стороны - 2t+1, а меньшая при этом может меняться от 1 до t+1. Поэтому s(4t) = t+1.

Итак, T(n) зависит от остатка от деления n на 12.
Остается рассмотреть каждый случай.

Например, при n = 12k. Тогда T(n) = 1 + 2 + … + 3k-1 - (1 + 4 + … + 3k-3) = 3k2 = n2/48.

Аналогично рассматриваются и остальные случаи.

Окончательно получаем, что T(n) = f(n)/48, где:
f(n) = n2 при n = 12k;
f(n) = n2 + 6n - 7 при n = 12k+1 или n = 12k+5;
f(n) = n2 - 4 при n = 12k+2 или n = 12k+10;
f(n) = n2 + 6n + 21 при n = 12k+3;
f(n) = n2 - 16 при n = 12k+4 или n = 12k+8;
f(n) = n2 + 12 при n = 12k+6;
f(n) = n2 + 6n + 5 при n = 12k+7 или n = 12k+11;
f(n) = n2 + 6n + 9 при n = 12k+9;

1. Из выведенной формулы для T(n) ясно, что при n, кратном 48, T(n) всегда будет делиться на n. Поэтому множество n, при которых T(n) кратно n, бесконечно.

2. Покажем, что бесконечно много квадратов являются значениями T(n), например, при n = 12K+2. T(12k+2) = ((12k+2)2 - 4)/48 = (3k+1)k. Достаточно, чтобы 3k+1 и k были квадратами. Пусть 3k+1 = x2 и k = y2. Тогда x2 - 3y2 = 1. Но это уравнение Пелля, имеющее, как известно, бесконечно много решений (x0 = 1, y0 = 0, xn+1 = 2xn + 3yn, yn+1 = xn + 2yn).

3. Ясно, что T(n) периодично по модулю 173 с периодом 173⋅12, а по модулю 211 с периодом 211⋅12.
В классах 12k и 12k+9 на каждом периоде будет по одному числу, кратному каждому из интересующих нас чисел.
В классах 12k+1, 12k+2, 12k+4, 12k+5, 12k+7, 12k+8, 12k+10 и 12k+11 на каждом периоде будет по два числа, кратных каждому из интересующих нас чисел.
Наконец, в классах 12k+3 и 12k+6 на каждом периоде будет по 2 числа, кратных 211, но не будет чисел кратных 173, поскольку значение T(n), равно в этих случаях 3k2+3k+1, а квадратное сравнение 3k2+3k+1 == 0 (mod m) разрешимо при m = 211, но не разрешимо при m = 173.

Итого, на каждом периоде ровно 18 значений T(n) кратно 173 и ровно 22 кратны 211.

Остается уравнять длины периодов.

Из каждых 12⋅173⋅211 значений T(n) ровно 173⋅22 делятся на 211 и ровно 211⋅18 кратны 173. Поскольку первое из этих чисел больше, то значения T(n), кратные 211, встречаются чаще.

Награды

За правильное решение этой задачи Виктор Филимоненков и Влад Франк получают по 8 призовых баллов.

Эстетическая оценка задачи - 2.5 балла


 

 


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

marathon/problem_58.txt · Последние изменения: 2016/10/21 09:19 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006