Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Книги
 Обсудить в форуме  Добавить новое сообщение
Next: ...к задачам седьмой олимпиады Up: 7.6. Указания и решения Previous: ...к задачам пятой олимпиады Contents: Содержание

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

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

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

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

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

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

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

Тогда, учитывая, что начальное положение стрелок соответствует букве А на первом колесе и 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}
для подходящих неотрицательных целых чисел $ m_k$ и $ n_k$.

Заметим, что $ 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, то есть имеют вид $ 70s_k$ для подходящего неотрицательного целого $ s_k$. Поэтому
\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*}
Подставляя $ m_k$ в (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
$ a_k$ 2 8 9 8 9 1 1
$ b_k$ 4 0 2 3 1 2 1
$ -(21a_k+20b_k)$ $ -122$ $ -168$ $ -229$ $ -228$ $ -209$ $ -61 $ $ -41 $
$ t_k$ 18 42 51 52 71 79 99
Буквы C И С Т Е М А

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

Каждой расстановке ненулевых цифр на окружности однозначно соответствует цепочка 1-соседних пар вида: $ (1,a_1)$, $ (a_1,a_2)$, $ (a_2,a_3)$, ..., $ (a_7,a_8)$, $ (a_8,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, так как для любого натурального $ n$ справедливо:

\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}

Кроме того, $ p^3-p=(p-1)p(p+1)$ кратно 24, то есть остатки у $ a_{n+2}$ и $ a_n$ равны.

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

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

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

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

Проект осуществляется при поддержке:
 Геологического факультета МГУ,
РФФИ
    
TopList Rambler's Top100