CITForum Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети ОС Hardware
Next: ...к задачам девятой олимпиады Up: 7.6. Указания и решения Previous: ...к задачам седьмой олимпиады Contents: Содержание

...к задачам восьмой олимпиады

Рис. 22.

\epsfbox{oli89.81}

8.1. Проведем прямые, проходящие через точки пересечения границ сложенной ленты параллельно ее краям. Очевидно, что тогда лента разобьется на равные равносторонние треугольники. Отметим цифрой 0 все просветы, а цифрой 2 все треугольники, которые получились наложением друг на друга двух треугольников в сложенной ленте. Построим дополнительно ряд треугольников вне эмблемы, как показано на рисунке 22. В полученной фигуре число треугольников, отмеченных цифрой 2, равно числу треугольников, отмеченных цифрой 0. Поэтому площадь всей ленты равна площади трапеции $ ABCD$. Количества треугольников в горизонтальных рядах $ ABCD$ являются 9 последовательными членами арифметической прогрессии с первым членом, равным 3 (нижний ряд), и разностью 2. Следовательно, общее число треугольников равно

\begin{displaymath}N=\frac{2\cdot3+(9-1)\cdot2}{2}\cdot9=99. \end{displaymath}

Если $ h$ - ширина ленты, то площадь одного равностороннего треугольника с высотой $ h$ равна

\begin{displaymath} S_0=h^2\ctg60^\circ=h^2/\sqrt3. \end{displaymath}

С другой стороны, если длина прямоугольника, полученного послеразрезания ленты, равна $ l$, то $ S \double= lh$. Отсюда находим искомую величину: $ l/h=33\sqrt3$.


Ответ: $ 33\sqrt3$.

8.2. Последовательность из $ k$ нулей или $ k$ единиц обозначим соответственно через $ 0^k$ или $ 1^k$. Тогда шифрование каждого знака сообщения состоит в замене
\begin{displaymath} \left\{\begin{array}{@{}r@{\:\to\:}l} 0&0^{k_1}1^{k_2}\\ 1... ...5}\\ 0&0^{k_6} \end{array}\right. \text{для II способа.} \end{displaymath} (1)

В зашифрованном сообщении все серии из единиц имеют длину $ k_2$ для первого способа и длину $ k_4$ для второго способа, поэтому, для совпадения результатов зашифрования необходимо, чтобы
\begin{displaymath} k_2=k_4. \end{displaymath} (2)

Теперь легко получить, что в сообщении должно быть одинаковое число нулей и единиц.

Пусть $ n$ - число нулей в сообщении. Тогда число нулей в зашифрованном I способом сообщении равно $ nk_1 + nk_3$, а II способом - $ nk_5 + nk_6$. Таким образом,
\begin{displaymath} nk_1 + nk_3 = nk_5 + nk_6. \end{displaymath} (3)

Из (1) видно, что сообщение должно начинаться с нуля и оканчиваться единицей. Пусть перед первой единицей сообщения расположено $ a$ нулей. Тогда первые $ а +1$ знаков сообщения представляются при шифровании в виде:
\begin{displaymath} \begin{split} \text{при} а=1\qquad&\left\{\begin{array}{@{}... ...&\quad\text{для II способа.} \end{array}\right. \end{split} \end{displaymath} (4)

При $ a=1$ получаем необходимость равенства $ k_1=k_6$, а значит, с учетом (3) - равенства $ k_3=k_5$.

При $ а >1$ получаем условия:

\begin{displaymath} \begin{array}{l@{\qquad}l} k_1=ak_6 ,& а\text{натуральн... ...k_1=k_5+bk_6,& b\text{натуральное или нуль}. \end{array} \end{displaymath}

Подставляя $ k_1=k_5+bk_6$ в (3), получаем равенство $ k_3=(1-b)k_6$, которое при натуральных $ k_3$, $ k_6$ и $ b\geq0$ возможно лишь в случае $ b=0$. Следовательно, $ k_3=k_6$, а значит, с учетом (3) $ k_1=k_5$.

Таким образом, при $ а >1$ необходимы условия $ k_2=k_4$, $ k_5=k_1\double=ak_6=ak_3$, где $ a$ - натуральное. Из (4) следует, что сообщение должно иметь вид $ 0\dots01\dots1$, где число нулей и число единиц равно $ a$.

Ответ: При $ k_2=k_4$, $ k_1=k_6$, $ k_3=k_5$ сообщения вида $ 0101\dots01$ шифруются одинаково.

При $ k_2=k_4$, $ k_5=k_1=ak_6=ak_3$, где $ a$ - натуральное, сообщения вида $ (0\dots01\dots1) \dots (0\dots01\dots1)$ (группы из $ a$ нулей и $ a$ единиц) шифруются одинаково.

Примечание. Первый ответ не является частным случаем второго при $ a=1$.

8.3. Естественно предположить, что все члены оргкомитета родились в ХХ веке. Отсюда сразу замечаем, что на 3, 7, 11, 15, 19 и 23 местах последовательности простых чисел расположены числа 11, 17, 47, 53, 83 и 89 соответственно.

Выясним, какие числа являются соседними с указанными шестью числами. Для этого составим таблицу их возможных ``соседей''. В соответствии с условием имеем:

число соседи
11 13, 19, 43, 7, 3
17 13, 19
47 79, 43, 31
53 61, 37
83 79, 67, 19
89 97, 73.

Учитывая, что первая цифра в номере месяца принимает значения только 0 или 1, построим следующую таблицу:
 15 02 20 45 42 13 26 67 44 30 56 82 53 33 62 32 73 63 92 49 75 70 98 49  
     19       19       19       19       19       19    
     11       17     31 47     37 53 61   67 83     73 89 97  
   03   03   13   13       43               19          
   07   07   19   19       79               79          
       13                                          
       19                                          
       43                                          

где в первой строке расположено шифрованное сообщение, во второй строке - известные участки исходного сообщения, в третьей строке - ставшие известными участки ключевой последовательности, в остальных строках - возможные варианты ключевой последовательности в соответствующих позициях. При составлении таблицы учитывалось, что каждое число должно встретиться ровно один раз. Позиции чисел 31, 37, 67, 73 определяются однозначно. Их расположение однозначно определяет места для простых чисел 61 и 97.

Снова выпишем известные числа последовательности простых чисел и варианты для их соседей (первые две строки таблицы на этом шаге не понадобятся):
     11       17     31 47     37 53 61   67 83     73 89 97  
   03   03   13   13       43               19          
   07   07   19   19       79               79          
       13                                          
       19                                          
       43                                          

Возможные соседи для числа 61 - лишь 59 и 29, а для 67 - лишь 59 и 3. Поэтому между 61 и 67 может находиться только число 59. Возможными соседями для числа 73 являются 89, 71 и 41. Ни одно из этих чисел не может быть соседом для 19, а для 79 может быть только 71. Таким образом, однозначно определяется расположение чисел 71 и 79. Для числа 47 остался только один кандидат в соседи справа - число 43. Общим соседом для 43 и 37 может быть только 41. Скорректируем таблицу с учетом сделанных выводов:
     11       17     31 47 43 41 37 53 61 59 67 83 79 71 73 89 97  
   03   03   13   13 29                                
   07   07   19   19 23                                
       13                                          
       19                                          

Участок последовательности $ 17\:*\:*\:31$ имеет только два варианта доопределения: (а) $ 17{-}19{-}23{-}31$ и (б) $ 17{-}13{-}29{-}31$. Рассмотрим оба случая.
а) Выпишем фрагмент таблицы для первого случая:
     11     13 17 19 23 31  
   03   03              
   07   07              

Очевидно, что числа 3 и 7 должны обязательно быть соседними с числом 11. Число 29 еще не встречалось, значит оно должно располагаться либо на первом месте, либо на пятом. И то и другое невозможно, так как в обоих позициях оно является соседом либо для числа 3, либо для числа 7, что не соответствует условию (отличие соседних чисел на степень двойки). Следовательно, рассматриваемый случай невозможен.
б) Выпишем фрагмент таблицы для второго случая:
 05   11   23 19 17 13 29 31  
   03   03              
   07   07              

Очевидно, что числа 3 и 7 должны обязательно быть соседями для числа 11. Число 5 может попасть только на первую позицию (т.к. оно не может находиться рядом с 19). Значит, в пятой позиции должно быть число 23. Ясно, что числа 3 и 7 теперь расставляются однозначно.

Таким образом, приходим к выводу, что возможен всего один вариант ключевой последовательности. Получим окончательный вариант таблицы и найдем ответ:
 15 02 20 45 42 13 26 67 44 30 56 82 53 33 62 32 73 63 92 49 75 70 98 49  
 10 09 19 48 29 04 19 54 25 09 19 49 12 06 19 71 24 06 19 70 04 07 19 52  
 05 03 11 07 23 19 17 13 29 31 47 43 41 37 53 61 59 67 83 79 71 73 89 97  

Ответ: 10.09.1948 29.04.1954 25.09.1949 12.06.1971 24.06.1970 04.07.1952

8.4. Занумеруем горизонтали и вертикали квадрата натуральными числами от 1 до 13 сверху вниз и слева направо соответственно. Тогда каждая клетка квадрата однозначно определяется парой чисел $ (i;j)$, где $ i$ - номер горизонтали, а $ j$ - номер вертикали, в которых находится клетка.

Расстояние между центром клетки $ (a;b)$ и центром клетки $ (c;d)$ равно $ \sqrt{(a-c)^2+(b-d)^2}$. Заметим, что $ \vert a-c\vert\in\{0,1,\dots,12\}$ и $ \vert b-d\vert\hph\in\{0,1,\dots,12\}$. Обозначим $ x=\vert a-c\vert$, $ y=\vert b-d\vert$, $ z=\sqrt{x^2+y^2}$. Тогда $ z$ - число натуральное, если $ x^2= (z+y)(z-y)$. Отсюда получаем, что

\begin{displaymath} \begin{split} 1=(z+y)(z-y) \Iff & \left\{\begin{array}{@{}l... ...{}}z=5\ y=4\end{array}\right.; \text{и т. д.} \end{split} \end{displaymath}


\begin{displaymath} \begin{split} 12^2=(z+y)(z-y) \Iff & \left\{\begin{array}{@... ...gin{array}{@{}l@{}}z=13\ y=5\end{array}\right.. \end{split} \end{displaymath}

В общем случае, если $ x^2 =mn$, то

\begin{displaymath} \left\{\begin{array}{@{}l@{}} z=\nfrac{m+n}{2}\\ y=\left\vert\nfrac{m-n}{2}\right\vert\end{array}\right.. \end{displaymath}

Ясно, что $ m$ и $ n$ должны быть одинаковой четности. По условию, $ y\leq12$, поэтому искомыми решениями будут только пары

\begin{displaymath} \begin{split} (x;y)\in A =&\{(3;4),(4;3),(6;8),(8;6),(9;12),... ...12;5)\}\\ \cup&\{(0;a),(a;0), a={1,\dots,12}\}. \end{split} \end{displaymath}

Клетку $ (a;b)$ назовем существенной для клетки $ (c;d)$, если выполнено условие $ (\vert a-c\vert;\vert b-d\vert)\in A$. Ясно, что цвет данной клетки менялся лишь тогда, когда Криптоша находился в какой-либо существенной для нее клетке. А так как в каждой клетке Криптоша побывал ровно 1999 раз (нечетное число), то цвет данной клетки изменился, если общее число существенных для нее клеток нечетно.

Для определения четности числа всех существенных клеток для данной клетки воспользуемся тем, что у симметричных клеток относительно той или иной диагонали квадрата или относительно центрального вертикального или центрального горизонтального рядов эти числа будут одинаковы. Это, в частности, означает, что достаточно определить указанную четность только для клеток $ (a;b)$, где $ a=1,\dots,5$, $ b\hph={a+1,\dots,6}$ (этих клеток 15, занумеруем их, как показано на рис. 23).

Рис. 23. Для клетки 1 жирными линиями выделена зона асимметрии. Серым цветом отмечены клетки верхнего левого угла $ 6\times 6$, меняющие свой цвет

\epsfbox{oli89.841}

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

Зоной асимметрии для той или иной клетки мы назовем множество тех клеток, которые в пределах исходного квадрата не имеют клеток, симметричных относительно вертикального, горизонтального и правого диагональных рядов, содержащих данную клетку. Ясно, что для данной клетки число существенных клеток, не лежащих в ее зоне асимметрии, четно.

На рис. 23 показана зона асимметрии для клетки 1, а также все клетки верхнего левого угла $ 6\times 6$, меняющие свой цвет.

Ответ на рис. 24.

Рис. 24.

\epsfbox{oli89.842}

8.5. При решении этого уравнения надо учитывать возможные ограничения: $ a\ne0$, $ b\ne0$, $ a-b\ne0$, $ a+b\ne0$. Поэтому целесообразно выделить их сразу.

1. Пусть $ а=0$, $ b=0$. Уравнение имеет вид $ \nfrac{0}{1-0x}=\nfrac{0}{1-0x}$, то есть $ x$ - любое число.

2. Пусть $ a=0$, $ b\ne0$. Уравнение имеет вид $ \nfrac{0}{1-bx}=\nfrac{b}{1-0x}$, или $ 0=b$, то есть не имеет решений.

3. Аналогично, при $ b=0$, $ a\ne0$ нет решений.

4. При $ a\ne0$, $ b\ne0$ удобно рассмотреть три случая: а) $ a=b$, b) $ a=-b$, c) $ a\ne\pm b$.
a) $ a=b$:     $ \nfrac{a}{1-ax}=\nfrac{a}{1-ax}$, $ x\ne\nfrac{1}{a}$,
$ x$ - любое, кроме $ \nfrac{1}{a}$.
b) $ a=-b$:     $ \nfrac{a}{1+ax}=\nfrac{-a}{1-ax}$, $ x\ne\pm\nfrac{1}{a}$, $ \nfrac{1}{a}+x=-\nfrac{1}{a}+x$, $ \nfrac{2}{a}=0$, решений нет.
c) $ a\ne\pm b$:
\begin{gather*} \frac{a}{1-bx}=\frac{b}{1-ax}, \qquad x\ne\frac{1}{a}, x\ne\fr... ...\frac{1}{a},\ [2pt] x=\frac{(a-b)ab}{ab(a^2-b^2}=\frac{1}{a+b}. \end{gather*}

Ответ. При $ a=b=0$ $ x$ - любое число.

При $ a=b\ne0$ $ x\in(-\infty;\nfrac{1}{a})\cup(\nfrac{1}{a};\infty)$.

При $ a=0,b\ne0$ или $ a\ne0, b=0$ или $ a=-b\ne0$ решений нет.

При $\left\{\begin{array}{@{}l}a\ne-b\ a\ne0\ b\ne0\\ a\ne+b\end{array}\right.$ $ x=\nfrac{1}{a+b}$.

8.6. Число $ 2^{30}+1$ представляет собой сумму кубов, сумму пятых степеней, а также из него можно выделить полный квадрат. Каждое из этих представлений позволяет найти некоторые делители исходного числа:
\begin{align*} 2^{30}+1=&2^{10\times3}+1^3=(2^{10}+1)(2^{20}-2^{10}+1) =1025\ti... ...8+1)(2^{15}+1-2^8)=\\ =&33025\times32513=25\times1321\times32513. \end{align*}

Таким образом, установлено, что среди простых делителей числа $ 2^{30}+1$ содержатся 41, 13, 5. Непосредственной проверкой получаем равенство $ 32513=41\times793=41\times13\times61$.

Осталось проверить, что 1321 - простое число. Для этого достаточно показать, что 1321 не делится ни на одно простое число, меньшее 37 ($ 37^2=1369$, $ 1369>1321$).

Ответ: $ 2^{30}+1=5\times5\times13\times41\times61\times1321$.

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

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети ОС Hardware

CITForum © 1997–2025