Филимоненков Виктор (fiviol) wrote,
Филимоненков Виктор
fiviol

Categories:

Математический марафон. Тур 6. Задачи 56-60.

Прежний пост, посвященный 6 туру математического марафона, проводимого Владимиром Лецко (http://www.fizmat.vspu.ru/konkurs/) уже, пожалуй, переполнен. Поэтому организую здесь вторую часть. Мои решения задач 56-60 будут сбрасываться сюда по мере открытия ответов на них.

31.01.07. Отсюда: http://62.205.161.162/x/_-0?Msg?6JhJJX&66&23778&
Шестой туp математического маpафона завеpшился очеpедной (уже тpетьей) победой Владислава Фpанка, упpочившего свое увеpенное лидеpство в общем зачете.
Победа досталась Владиславу в упоpной боpьбе в дебютантом маpафона, Виктоpом Филимоненковым.
Мои поздpавления лауpеатам!
ИТОГИ ШЕСТОГО ТУРА МАТЕМАТИЧЕСКОГО МАРАФОHА │
1. Владислав Франк - 85
2. Виктор Филимоненков - 74
3. Иван Козначеев - 13
4. Олег Полубасов - 10
5. Дмитрий Милосердов - 4
6. Алексей Ковальский - 3

Поздравляю Владислава! А у меня, стало быть, осталось куда расти.

Конкурсная задача №6(56) (12 баллов)

Назовем трехпарным число, допускающее представление в виде суммы трех взаимно простых натуральных слагаемых, любые два из которых не взаимно просты. Конечно ли множество натуральных чисел, не являющихся трехпарными?

Ответ: да, это множество конечно.
Решение.
1. Введем обозначения. n – некоторое число, p < q < r – три наименьших простых числа, не являющихся делителями n.
2. Докажем, что трехпарным будет любое число n, которое больше p^2*q*r.
Действительно, рассмотрим числа вида n-xqr. Поскольку p и qr взаимно просты, и n не делится на p, найдется такое целое положительное x < p, что n-xqr делится на p. Пусть n-xqr = mp. В силу того, что n > p^2*qr и x < p, имеем: m > (p-1)qr, причем m не делится на q и r.
Поскольку q и r взаимно просты, найдется такое целое положительное y < r, что m-yq делится на r. Поскольку r > p > x, и r – простое, то r и x взаимно просты, а, значит, остатки от деления на x чисел вида y+kr при k=0,1,...x-1 различны. Значит, среди этих остатков есть 1. Значит, для такого k число w=y+kr взаимно просто с x. Но поскольку m-yq делится на r, то и m-wq = m-yq-krq делится на r. При этом m-yq-krq > (p-1)qr-yq-kqr > (p-1)qr-qr-(p-2)qr=0, то есть m = wq+zr, причем w,z > 0.
Окончательно имеем:
n = xqr +wpq +zpr,
причем эти три слагаемых взаимно просты, поскольку xqr и wpq имеют наибольший общий делитель q (все остальные множители в этих слагаемых взаимно просты по построению), а zpr не делится на q (иначе бы и n делилось на q). Таким образом, n трехпарно.
3. Осталось доказать, что неравенство n > p^2*qr выполняется для всех натуральных чисел, начиная с некоторого.
Действительно, пусть, например, n>10000000. Пусть r – большее из трех простых p, q, r.
Если r <= 47, то p^2*qr <= 41^2*43*47 < 10000000 < n.
Если r > 47, то r >= 53, то есть является минимум четырнадцатым простым числом. Так как p, q, r наименьшие простые, на которые не делится n, n должно делиться по крайней мере на 11 различных простых множителей, меньших r. По аксиоме Бертрана (каждое предыдущее простое больше половины следующего) среди этих чисел должны быть четыре, которые больше r/8, r/16, r/32 и r/64. Кроме того, n делится еще на 7 различных простых, то есть
n > 2*3*5*7*11*13*17*(r/8)*(r/16)*(r/32)*(r/64) > r^4 > p^2*qr.

Эстетическая оценка задачи: 4 балла.
8.11.06.
Влад Франк прислал решение задачи, обобщающей задачу №56. Он доказал конечность множества натуральных чисел, не допускающих представления в виде суммы k+1 взаимно простых слагаемых, любые k из которых не взаимно просты.
За правильное решение этой задачи Виктор Филимоненков получает 12 призовых баллов, а Влад Франк - 15 призовых баллов.


Конкурсная задача №7(57) (10 баллов)

Назовем многоугольник регулярным, если он выпуклый и никакие 3 его диагонали не пересекаются в одной точке внутри многоугольника. Пусть n - число сторон регулярного многоугольника.

1) Hа сколько частей разбивают диагонали регулярный многоугольник?
2) Верно ли, что при фиксированном n среди частей, на которые разбивается диагоналями регулярный многоугольник, всегда одно и тоже число треугольников?
3) При каком минимальном n в разбиении регулярного многоугольника может получиться восьмиугольник?
4) Существует ли регулярный многоугольник, в разбиении которого получается больше пятиугольников, чем треугольников?
5) При каких n существуют разбиения регулярного многоугольника, содержащие только треугольники и четырехугольники?

Решение.
1) Ответ: на (k^2+10k)/24 части, где k=(n-1)(n-2).
Действительно, добавив к (n-1)-угольнику еще одну вершину (так, чтобы полученный n-угольник оставался выпуклым и регулярным), проведем диагонали из этой новой вершины. Каждая из этих диагоналей, пересекая любую из частей разбиения (n-1)-угольника, делит ее на два, то есть добавляет одну часть. Легко заметить, что эти n-3 новые диагонали пересекают соответственно, 1*(n-3), 2*(n-4) ... (n-3)*1 старых диагоналей, а, значит, все вместе эти диагонали добавляют 1*(n-3)+2*(n-4)+ ... +(n-3)*1 + (n-3) части разбиения. Еще одна часть добавляется при добавлении новой вершины. Всего это дает (n-3)(n-2)(n-1)/6 + 1 новую часть. Суммируя теперь слагаемые такого вида по n, начиная с n=3, получим указанный выше ответ.
2) Ответ: нет, не верно.
Например, правильный семиугольник является регулярным, и в его разбиении 35 треугольников. В то же время, в разбиении регулярного семиугольника, имеющего в декартовой системе координат координаты вершин (6;0), (3;1), (0;3), (0;7), (3;9) (6;9), (8;5), всего 34 треугольника.
3) Ответ. При n=9.
Заметим сначала, что m-угольник не может появиться в разбиении n-угольника при n < m. Действительно, диагонали, содержащие стороны m-угольника, соединяют 2 вершины n-угольника, но при этом ясно, что из одной вершины не может выходить более двух диагоналей, являющихся сторонами m-угольника. Таким образом, если в разбиении есть m-угольник, то n >= 2m/2 = m.
Теперь покажем, что m-угольник может появиться в разбиении n-угольника при n = m только для нечетного n.
Действительно, пусть n четно и в разбиении есть m(=n)-угольник. Тогда диагонали, содержащие стороны этого m-угольника, должны содержать все вершины (по 2 диагонали на каждую вершину). Занумеруем вершины n-угольника, двигаясь против часовой стрелки, остатками по модулю n. Две диагонали, входящие из каждой из этих вершин, и являющиеся сторонами m(=n)-угольника, должны, очевидно, соединять вершину с соседними вершинами, то есть имеющими номера, отличающиеся на 1 по модулю n.
Построим циклическую последовательность (i_1,i_2...) номеров вершин n-угольника следующим образом. Пусть i_1,i_2 – номера вершин, диагональ (или сторона) между которыми содержит сторону m-угольника. В качестве i_3 возьмем номер второй вершины, с которой соединена вершина i_2, в качестве i_4 - номер второй вершины, с которой соединена вершина i_3, и так далее, пока последовательность не зациклится. Тогда все время i_k=i_(k-2)+1 или все время i_k=i_(k-2)-1 (по модулю n). Поскольку вместе с каждой вершиной с номером i вершина с номером i+1 тоже лежит в этой последовательности, в этой последовательности находятся все n вершин. Но если n четно, то каждый член этой циклической последовательности будет иметь одновременно 2 значения, отличающиеся на n/2 по модулю n, что означает, что в одной вершине сходятся 4 стороны m(=n)-угольника, что невозможно. Противоречие.
В то же время, при нечетном n, регулярный n-угольник, получающийся из правильного n-угольника малым шевелением его вершин, содержит в разбиении m(=n)-угольник (а именно, ту часть, которая содержит центр правильного n-угольника).
Передвигая теперь одну из вершин этого n-угольника (начиная с n=7) вдоль описанной окружности, в какой-то момент получим (n-1)-угольник в разбиении.
Замечание. Понимаю нестрогость последнего предложения. Здесь бы лучше было, как в п.2, просто привести пример правильного 9-угольника, имеющего в разбиении 8-угольник, указав координаты его вершин. Но есть трудность в подборе подходящего 9-угольника с целочисленными координатами. Надеюсь, вы сочтете корректным мое нестрогое рассуждение.
4). Ответ. Нет, не существует.
Рассмотрим многоугольник, разбитый диагоналями, как плоский граф с (k^2+10k)/24 (согласно п.1) внутренними гранями (и одной внешней). Аналогично рассуждениям в п.1 (и параллельно с этим), легко показать, что точек пересечения диагоналей внутри регулярного n-угольника есть (k^2-2k)/24 штук. Поскольку многоугольник регулярный, валентности каждой их этих внутренних вершин графа равны 4. Есть еще n вершин многоугольника, валентности n-1. Итого, сумма валентностей всех вершин графа равна (k^2-2k)/6 + (n-1)n. Но такой же должна быть и сумма валентностей граней, значит, на долю (k^2+10k)/24 внутренних граней приходится (k^2-2k)/6+(n-1)n–n валентностей (валентность внешней грани равна n). В среднем это меньше 4 на одну грань. Поскольку наименьшее число сторон у каждой грани 3, то в среднем меньше 4 может получиться, только если количество треугольников в разбиении больше общего числа всех многоугольников с числом сторон больше 4, в частности, треугольников всегда больше, чем пятиугольников.
5). Ответ. Только при n=3 и n=4.
В этих случаях все части разбиения треугольники.
Далее, при любом n, начиная с 4, n(n-3)=(n-1)(n-2)-2=k-2 части разбиения, примыкающие к вершинам многоугольника, являются треугольниками. На остальные (k^2+10k)/24-(k-2)=(k^2-14k+48)/24 части разбиения приходится (k^2-2k)/6+(n-1)n–n-3(k-2)=(k^2-14k+36)/6+n-2 валентностей, то есть больше, чем в среднем по 4 на 1 грань. Согласно принципу Дирихле :) это означает, что среди частей разбиения есть хотя бы 1 с числом сторон, больше 4.

Моя эстетическая оценка задачи – 3 балла.
18.11.06. (исправление в п.3 - 21.11.06.)

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


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

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

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

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

Решение: Ясно, что T(n) – это количество способов представить число n в виде суммы трех неупорядоченных целых слагаемых таких, что каждое из них было меньше суммы двух других.
1). Ответ: нет, это множество бесконечно.
Рассмотрим n, кратные 12. Покажем, что T(12*k) = 3*k^2.
Рассмотрим количество способов разложения числа 12*k с самым большим слагаемым, равным 6*k-1 (ясно, что это наибольшее возможное значение длины треугольника с периметром 12*k). Тогда две другие стороны могут принимать значения: 6*k-1 и 2, или 6*k-2 и 3 ... или 3*k+1 и 3*k – всего 3*k-1 возможных способов.
Аналогично, количество способов разложить 12*k на три слагаемых с наибольшим слагаемым 6*k-2 равно 3*k-2; количество способов разложения с наибольшим слагаемым 6*k-3 равно 3*k-4 и т.д. Наконец, есть 1 способ разложить 12*k на три слагаемых со старшим слагаемым 4*k.
Таким образом, общее количество способов разбиения 12*k на три слагаемых равно:
T(12*k) = (3*k-1) + (3*k-2) + (3*k-4) + (3*k-5) + ... + 2 + 1 = 3*k^2.
Таким образом, при k делящимся на 4 (то есть при n делящимся на 48) T(12*k) делится на 12*k.
2) Ответ: нет, это множество бесконечно.
По аналогии с п. 1 легко показать, что верны следующие выражения для T(n) в зависимости от остатка от деления n на 12:
T(12*k) = 3*k^2
T(12*k+1) = 3*k^2+2k = k*(3k+2)
T(12*k+2) = 3*k^2+k = (3k+1)*k
T(12*k+3) = 3*k^2+3*k+1
T(12*k+4) = 3*k^2+2*k = (3*k+2)*k
T(12*k+5) = 3*k^2+4*k+1 = (3*k+1)*(k+1)
T(12*k+6) = 3*k^2+3*k+1
T(12*k+7) = 3*k^2+5*k+2 = (3*k+2)*(k+1)
T(12*k+8) = 3*k^2+4*k+1 = (3*k+1)*(k+1)
T(12*k+9) = 3*k^2+6*k+3 = 3*(k+1)^2
T(12*k+10) = 3*k^2+5*k+2 = (3*k+2)*(k+1)
T(12*k+11) = 3*k^2+7*k+4 = (3*k+4)*(k+1)

Покажем, например, что бесконечно количество квадратов вида T(12*k+2) = (3k+1)*k. Пусть k = m^2, тогда достаточно доказать бесконечность количества решений уравнения 3m^2+1 = l^2. Но пара l_1 = 2, m_1 = 1 – одно из решений, и вместе с каждым решением l_i, m_i пара l_(i+1)=3*(m_i)^2+(l_i)^2, m_(i+1) = 2*m_i*l_i тоже является решением (очевидно, новым).

3) Ответ: Чаще встречаются те n, при которых T(n) кратно 211.
В силу приведенных в п.2 формул для T(n) выражение T(n) периодично по любому простому модулю p с периодом 12*p. Поэтому под частотой появления таких n, для которых T(n) делится на p, естественно принять долю таких n среди первых 12*p чисел, которые являются решениями сравнения T(n) = 0 (mod p).
Проследим за формулами из п.2. Для 8 из 12 значений s выражение для T(12*k+s) раскладывается в произведение различных линейных множителей. Для простых p это означает, что T(12*k+s) = 0 (mod p) если один из множителей = 0 (mod p), что дает 8*2=16 решений (то есть подходящих значений k при данном s).
Сравнения T(12*k) = 3*k^2 = 0 (mod p) и T(12*k+9) = 3*(k+1)^2 (mod p) имеют по одному решению k = 0 (mod p) и k = -1 (mod p) соответственно.
Наконец, сравнение T(12*k+3) = T(12*k+6) = 3*k^2+3*k+1 = 0 не будет иметь решений по модулю p = 173, и будет иметь 2 решения по модулю p = 211. Действительно дискриминант уравнения 3*k^2+3*k+1 = 0 равен -3, при этом -3 является квадратом по модулю 211, но не является кадратом по модулю 173 (соответствующие символы Лежандра равны 1 и -1 соответственно).
Таким образом, сравнение T(n) = 0 (mod 173) имеет 18 решений на отрезке длиной 12*173, а сравнение T(n) = 0 (mod 211) имеет 22 решения на отрезке длиной 12*211. То есть те n, при которых T(n) кратно 173, встречаются с частотой около 0,00867, а те n, при которых T(n) кратно 211 - с частотой около 0,00869, то есть чаще.

Моя эстетическая оценка задачи: 4 балла.
19.12.06. (исправление 21.12.06)
За правильное решение этой задачи Виктор Филимоненков и Влад Франк получают по 8 призовых баллов.

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

Сколько существует гомоморфизмов из кольца классов вычетов по модулю m в кольцо классов вычетов по модулю n?

Ответ: Пусть n = p_1^k_1*…*p_s^k_s – каноническое разложение n, и пусть m делится на t выражений вида p_i^k_i. Тогда есть 2^t гомоморфизмов колец.
Решение. На всякий случай уточню: под гомоморфизмом колец X и Y я понимаю отображение f из X в Y, такое что f(x+y) = f(x)+f(y) и f(x*y) = f(x)*f(y) для любых элементов x и y из X.
Я буду опускать выражения (mod m) и (mod n), если это не может вызвать непонимание. Во всех записях вида f(x) = y f будет обозначать гомоморфизм, x – целое число по модулю m, y –целое число по модулю n.

Обозначим f(1) = b. Поскольку f(2) = f(1+1) = f(1) + f(1) = 2b, и вообще f(x) = x*b для любого x, то число b однозначно определяет весь гомоморфизм.

Поскольку f(1) = f(1*1) = f(1)*f(1), то число b является решением уравнения x^2 = x (mod n). Это уравнение равносильно системе уравнений x^2 = x (mod p_i^k_i), i = 1, … , s, каждое из которых имеет ровно по 2 решения x = 1(mod p_i^k_i) и x = 0 (mod p_i^k_i). Таким образом, уравнение x^2 = x (mod n) имеет 2^s решений, каждое из которых можно записать в виде набора нулей и единиц b = (d_1, … ,d_s), где d_i = b (mod p_i^k_i).

Заметим также, что условие b^2 = b является также и достаточным для того, чтобы выполнялось f(x*y) = f(x)*f(y) для любых элементов x и y. Действительно, f(x)*f(y) = (x*b)*(y*b) = x*y*b^2 = x*y*b = f(x*y).

Пусть a – наименьшее целое, такое что f(a) = a*b = 0, то есть a*b делит n. Поскольку b делится на все выражения вида p_i^k_i, для которых d_i = 0, то a равно произведению остальных выражений p_i^k_i. Ясно, что f (x+a) = f(x), и, поскольку f(m) = f(0) = 0, то m делится на a. Таким образом, гомоморфизм с f(1) = b = (d_1, … ,d_s) возможен только в том случае, когда m делится на выражения p_i^k_i для всех i, для которых d_i = 1. Заметим, что этого условия и достаточно для выполнения равенства f(x+y) = f(x)+f(y) для любых элементов x и y.

Таким образом, если m делится на t выражений вида p_i^k_i, то существует ровно 2^t гомоморфизмов, определяемых условием f(1) = b = (d_1, … ,d_s), c d_i = 0 для тех i, для которых m не делится на p_i^k_i и с произвольными d_i для остальных i.

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

Конкурсная задача №10(60) (12 баллов)

Решения принимаются, по крайней мере до 27.01.07

Триша Тройкин, Петя Пятаков и Сёма Семак пытаются сконструировать собственный генератор псевдослучайных чисел.
Для этого они взяли натуральные числа a и m (одни и те же у всех троих) и выстраивают последовательность по правилу:
x_{n+1} = (x_n*a) mod m.
Hачав с некоторого x_1, Триша посчитал x_2, x_3 и x_4. Hо x_4 оказалось равно x_1. Тогда он взял другое (не встречавшееся ранее) число в качестве x_1. Hо последовательность опять зациклилась на третьем шаге. Треья попытка привела Тришу к тому же результату.
Петя совершил пять попыток подобрать x_1. Hо всякий раз получал новые циклы длины 5. Hаиболее упорным оказался Сёма. Он совершил семь попыток. И получил семь циклов длины 7.
При каком наименьшем m могла возникнуть такая ситуация?

Ответ (неверный). При m = 28613 = 13*31*71
Решение: Пусть x, y, z – числа, выбранные соответственно Тришей, Петей, Семой (например, при первых попытках). Тогда верны равенства:
x*(a^3-1) = x*(a-1)(a^2+a+1) = 0 (mod m)
y*(a^5-1) = y*(a-1)(a^4+a^3+a^2+a+1) = 0 (mod m)
z*(a^7-1) = z*(a-1)(a^6+a^5+a^4+a^3+a^2+a+1) = 0 (mod m)
Ясно, что x*(a-1), а также y*(a-1) и z*(a-1) не равны 0, поскольку тогда у кого-то из ребят x_2 = x_1. Поэтому числа a^2+a+1, a^4+a^3+a^2+a+1 и a^6+a^5+a^4+a^3+a^2+a+1 должны иметь среди своих делителей делители числа m. А поскольку эти три числа при любых a попарно взаимно просты (с помощью алгоритма Евклида легко видеть, что их попарные НОД равны 1), то m должно иметь три разных простых делителя.

Лемма. Если для некоторых простых чисел k и p и целом a выполняется равенство
а^k = 1 (mod p),
то либо a = 1 (mod p), либо p имеет вид q*k+1.
Доказательство леммы. По малой теореме Ферма a^(p-1) = 1 (mod p), по условию а^k = 1 (mod p). Поделим p-1 на k с остатком, то есть p-1 = k*q+ r. Тогда a^r = 1, и, если r не равно 0, то a^НОД(k,r) = 1.Но в силу простоты k НОД(k,r) = 1, то есть в этом случае a = 1.

Таким образом, если a не равно 1 (mod p), то сравнение a^2+a+1 = 0 (mod p) возможно только для простого p вида 3q+1, то есть p = 7, 13, 19, 31 … Кроме того, если a = 1 (mod p), то сравнение a^2+a+1 = 3 = 0 (mod p) возможно только при p = 3. Но в этом случае m должно делиться на 3^2, иначе уже x(a-1) делится на 3. Таким образом, m должно иметь среди своих делителей какое-то из чисел 7, 9, 13, 19, 31…
Поскольку, однако, Триша трижды выбирал в качестве x_1 числа, которые не встречались ранее, остатки от деления на p всех 9 чисел, встретившихся у него, должны быть разными, причем не равными 0. Таким образом, p имеет не меньше 10 остатков. Значит, m должно иметь делитель не меньше 13.
Аналогично, m должно иметь среди своих делителей одно из простых чисел вида 5k+1, то есть 11, 31, 41…, либо 5^2 = 25. Опять же по аналогии, этот делитель должен быть не меньше 26, а значит, не меньше 31.
Аналогично, m должно иметь среди своих делителей одно из простых чисел вида 7k+1, то есть 29, 43, 71…, либо 7^2 = 49. Наименьший из этих делителей, при котором Сема мог выбрать 7 раз не встречавшееся ранее число в качестве x_1 равно 71.

Поскольку эти три делителя должны быть разными, то наименьшим возможным значением для m может быть, равное произведению наименьших возможных делителей m в каждом из трех случаев, то есть m = 13*31*71.

Поскольку 3^3-1 = 0 (mod 13), 2^5-1 = 0 (mod 31), 30^7-1 = 0 (mod 71) (последнее, поскольку 30^7 = 1024^7 = (2^10)^7 = 2^70 = 1 (mod 71)), возьмем в качестве a, например, решение системы сравнений a = 3 (mod 13), a = 2 (mod 31), a = 30 (mod 71). Тогда
a^3-1 = 0 (mod 13), a^5-1 = 0 (mod 31), a^7-1 = 0 (mod 71)

Для Триши в качестве первого значения x_1 возьмем 31*71. Тогда x_1*a^3 = x_1 (mod 13*31*71), а при меньших степенях a это равенство, очевидно, не выполняется. При этом числа x_1, x_2, x_3 имеют вид R*31*71. В качестве следующего значения x_1 возьмем r*31*71, где r – не встречавшийся ранее остаток от деления на 13 множителя R для чисел x_1, x_2, x_3. В третий раз снова поступим так же.
Аналогично для Пети возьмем сначала x_1 = 13*71, и в следующие 4 раза в качестве следующего значения x_1 возьмем r*13*71, где r – не встречавшийся ранее остаток от деления на 31.
Аналогично для Семы возьмем в качестве x_1 = 13*31, и в следующие 6 раз в качестве следующего значения x_1 возьмем r*13*31, где r – не встречавшийся ранее остаток от деления на 71.

Таким образом, при указанном значении m возможна указанная в условии задачи ситуация.

Моя эстетическая оценка задачи: 4 балла.
Комментарии: 1. Эстетическую оценку я немного снизил, поскольку громоздким для решения кажется условие о необходимости многократного выбора x_1. Без слов «не встречавшихся ранее», на мой взгляд, задача была бы элегантнее, хотя и «дешевле» (ответ m = 7*11*29, при a = 16).
2. Чуть ли не две недели я потратил, решая неправильно прочитанную задачу, а именно x_{n+1} = (x_n^a) mod m вместо x_{n+1} = (x_n*a) mod m. С неправильной задачей я не справился.
Насколько я понимаю, это была последняя задача 6 тура? Спасибо Вам за задачи, было очень интересно. Хочется пожелать Вам побольше участников, а себе продолжения. Ну, и, наверное, чтобы были задачи из разных математических дисциплин.
24.01.07 г.

Комментарий. Верный ответ: m = 6699 = 3*7*11*29. Дальше все ясно. Да, не уловил я этой простой мысли, умножить m на 3, чтобы получить нужное количество остатков :(
За правильное решение этой задачи Владислав Франк получает 12 призовых баллов.
Виктор Филимоненков (найденное им m - не наименьшее) получает 7 баллов.

Tags: Задачи, Математика
Subscribe

  • Коробка с красным померанцем

    Мне уже случалось фотографировать это слово из трех букв - меня позабавило тогда, что оно похоже на ручки на газовой плите, у которой две конфорки…

  • Бессловесная игра

    Напоминаю, что также в игре Словесные игры: Вопрос 191 (оно), Вопрос 192 (шаги и прыжки), Вопрос 193 (анаграммы), Вопрос 194 (две строчки),…

  • Словесные игры 39. Вопрос 195

    Также в игре: Вопрос 191 (оно), Вопрос 192 (шаги и прыжки), Вопрос 193 (анаграммы), Вопрос 194 (две строчки), Сегодня последняя загадка 39…

  • Post a new comment

    Error

    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 10 comments

  • Коробка с красным померанцем

    Мне уже случалось фотографировать это слово из трех букв - меня позабавило тогда, что оно похоже на ручки на газовой плите, у которой две конфорки…

  • Бессловесная игра

    Напоминаю, что также в игре Словесные игры: Вопрос 191 (оно), Вопрос 192 (шаги и прыжки), Вопрос 193 (анаграммы), Вопрос 194 (две строчки),…

  • Словесные игры 39. Вопрос 195

    Также в игре: Вопрос 191 (оно), Вопрос 192 (шаги и прыжки), Вопрос 193 (анаграммы), Вопрос 194 (две строчки), Сегодня последняя загадка 39…