...к задачам шестой олимпиады

Next: ...к задачам седьмой олимпиады Up: 7.6. Указания и решения Previous: ...к задачам пятой олимпиады Contents: Содержание

...к задачам шестой олимпиады

6.1. Так как каждый из 1997 абонентов связан ровно с другими, то общее число направлений связи равно . Отсюда общее число связанных пар абонентов равно , так как каждая связанная пара имеет ровно 2 направления связи. Поскольку число должно быть целым, а число 1997 - нечетное, то число должно быть четным.

Докажем, что для каждого существует система связи из 1997 абонентов, в которой каждый связан ровно с другими. В самом деле, расположив всех абонентов на окружности и связав каждого из них с ближайшими к нему по часовой стрелке и с ближайшими к нему против часовой стрелки, получим пример такой сети связи.

6.2. Покажем, что на диагонали присутствуют все числа от 1 до 1997. Пусть число $a\in\{1,\dots,1997\}$ не стоит на диагонали. Тогда, в силу симметрии таблицы, число встречается четное количество раз. С другой стороны, так как число по одному разу встречается в каждой строке, всего в таблице чисел нечетное количество (1997). Получили противоречие.

Всего на диагонали 1997 клеток, поэтому каждое число из множества $\{1,\dots,1997\}$ встретится на диагонали ровно по одному разу. Вычисляя сумму арифметической прогрессии, находим ответ.

Ответ: 1995003.

6.3. Ответ: ШЕСТАЯОЛИМПИАДАПОКРИПТОГРАФИИПОСВЯЩЕНАСЕМИДЕСЯТИ
ПЯТИЛЕТИЮСПЕЦИАЛЬНОЙСЛУЖБЫРОССИИ

Указание. Пусть некоторая буква $\alpha$ при зашифровании первым способом заменялась на букву $\beta$ . Тогда количество повторов буквы $\beta$ в первой криптограмме будет равно числу повторов буквы $\alpha$ во второй криптограмме.

6.4. а) Определим моменты остановок после начала шифрования. Для этого каждой букве русского алфавита припишем ее порядковый номер: А - 0, Б - 1, и т.д. Тогда буквам из шифруемого слова будут соответствовать номера: О - 15, Л - 12, И - 9, М - 13, П -16, А - 0, Д - 4. Моменты остановок будем указывать числом одношаговых (на один зубец) поворотов I колеса до соответствующей остановки.

# остановки 1 2 3 4 5 6 7 8 9

Буква I колеса О Л И М П И А Д А

Число одношаговых поворотовот начала до остановки 15 45 75 79 82 108 132 136 165

Цифра II колеса 5 5 5 1 8 2 8 4 5

Цифра III колеса 1 2 5 2 5 3 6 3 4

Искомый шифртекст: 515355128523864354

б) Пусть - количество одношаговых поворотов I колеса от начала до остановки с номером , $k=1,2,\dots$ ,

- цифра, на которую указывает стрелка II колеса в момент остановки с номером ,

- цифра III колеса, на которую указывает стрелка III колеса в момент остановки с номером .

Тогда, учитывая, что начальное положение стрелок соответствует букве А на первом колесе и 0 на II и III колесах, справедливы равенства
$\begin{gather} t_k=10m_k-a_k,\quad k=1,2,\dots \\ t_k=7n_k+b_k,\quad k=1,2,\dots \end{gather}$
для подходящих неотрицательных целых чисел и .

Заметим, что $1=7\cdot3-10\cdot2$ . Отсюда справедливы равенства
$\begin{gather*} a_k=7\cdot(3a_k)-10\cdot(2a_k), k=1,2,\dots\\ b_k=7\cdot(3b_k)-10\cdot(2b_k), k=1,2,\dots \end{gather*}$
Подставляя эти значения в равенства (1) и (2), получим
$\begin{gather*} t_k=10(m_k+2a_k)-7(3a_k), k=1,2,\dots\\ t_k=7(n_k+3b_k)-10(2b_k), k=1,2,\dots \end{gather*}$
Следовательно,

$\begin{displaymath} 10(m_k+2a_k)-7(3a_k)= 7(n_k+3b_k)-10(2b_k), k=1,2,\dots \end{displaymath}$

Правая и левая части делятся на 70, то есть имеют вид

для подходящего неотрицательного целого

. Поэтому
$\begin{gather*} m_k=7s_k-2(a_k+b_k), k=1,2,\dots\\ n_k=10s_k-3(a_k+b_k), k=1,2,\dots \end{gather*}$
Подставляя

в (1), получим

$\begin{displaymath}t_k=70s_k-21a_k-20b_k, k=1,2,\dots . \end{displaymath}$

Учитывая условие $0<t_1<t_2<\dots<t_7$ и то, что остановка колеспроисходит в момент первого появления шифруемой буквы под стрелкой I колеса, имеем

k 1 2 3 4 5 6 7

2 8 9 8 9 1 1

4 0 2 3 1 2 1

18 42 51 52 71 79 99

Буквы C И С Т Е М А

6.5. Указание. Рассмотрим некоторую расстановку ненулевых цифр на окружности. Упорядоченную пару соседних цифр на этой окружности назовем 1-соседней, если является соседней с по часовой стрелке. Пару назовем 2-соседней, если существует цифра , для которой пары и являются 1-соседними.

Каждой расстановке ненулевых цифр на окружности однозначно соответствует цепочка 1-соседних пар вида: , , , ..., , , которой, в свою очередь, однозначно соответствует цепочка 2-соседних пар вида:

$\begin{displaymath}(1,a_2), (a_2,a_4), (a_4,a_6), (a_6,a_8),(a_8,a_1)(a_1,a_3)(a_3,a_5)(a_5,a_7)(a_7,1), \eqno(*) \end{displaymath}$

где $a_2,a_3,\dots,a_8\in\{2,\dots,9\}$ и $a_i\ne a_j$ при $i\ne j$ .

Если из цепочки удалить любую пару, то по оставшимся парам она восстанавливается однозначно.

Если из цепочки удалить две соседние пары, то она также восстанавливается однозначно.

Удаление из любых трех пар приводит к неоднозначности восстановления цепочки . В этом можно убедиться, рассмотрев следующие фрагменты цепочки вида :
$\begin{align*} & (a,b)(b,c)(c,d) \text{ и } (a,c)(c,b)(b,d), &&(a,b,c,d\text{ ... ...азличные }\\ &&&\phantom{(a,b,c,d,e,f \text{ - }} \text{цифры}). \end{align*}$
Таким образом, при наличии двух указанных в условии задачи цифровых текстов нам будут известны некоторые 2-соседние пары, в которых первая цифра берется из первой криптограммы, а вторая - из второй. Поэтому с учетом вышесказанного получаем условие однозначного восстановления порядка расстановки цифр на данной окружности.

Ответ: для однозначного восстановления расстановки цифр на окружности необходимо и достаточно, чтобы в одном из цифровых текстов было не менее 7 ненулевых цифр (это соответствует удалению из цепочки 2-соседних пар вида не более двух из них).

6.6. Последовательность остатков от деления чисел $a_1, a_2, \dots$ на 24 - периодическая с периодом 2, так как для любого натурального справедливо:

$\begin{displaymath} a_{n+2}-a_n=p^{n+4}-p^{n+2} =\left\{ \begin{array}{@{}ll} ... ...\ p^{n+1}(p^3-p), &\mbox{при }p\geq3 \end{array} \right. . \end{displaymath}$

Кроме того,

кратно 24, то есть остатки у $a_{n+2}$ и

равны.

6.7. Ответ: ; все решения имеют вид $\pm3992k+1996$ , $k=0,1,\dots,998$ .

Указание. При $a\leq0$ рассматриваемое уравнение равносильно $\vert x-a\vert-1995a=1996$ , которое имеет не более двух решений.

При из графика функции в левой части уравнения видно, что если $1996\in(0, a)$ , число решений будет четным, поэтому не может быть равно 1997. Если $1996\in(a, +\infty)$ , то уравнение имеет ровно 2 решения. Если же , то уравнение имеет ровно 1997 решений.