Rambler's Top100 Service
Поиск   
 
Обратите внимание!   Обратите внимание!
 
  Наука >> Математика >> Алгебра, математическая логика и теория чисел | Книги
 Написать комментарий  Добавить новое сообщение
Next: Литература к главе 7 Up: 7.6. Указания и решения Previous: ...к задачам восьмой олимпиады Contents: Содержание

...к задачам девятой олимпиады

9.1. а) Для доказательства достаточно указать хотя бы одну последовательность из 33 различных букв, сумма которой с русским алфавитом из 33 букв не содержит одинаковых букв. В качестве искомой последовательности возьмем сам алфавит. Докажем, что сумма алфавита с самим собой не содержит одинаковых букв. Пусть $ m$ и $ n$ - порядковые номера различных букв алфавита. Тогда по определению сложения букв достаточно показать, что числа $ 2m$ и $ 2n$ имеют разные остатки от деления на 33. В самом деле, если бы они были одинаковы, то число $ 2m-2n$ делилось бы на 33 без остатка. В силу того что $ \mathrm{НОД}(2, 33)=1$, разность $ m-n$ также делилась бы на 33 без остатка, что невозможно. Утверждение пункта а) доказано.

Замечание. Утверждение пункта а) остается в силе для любого алфавита из нечетного числа букв.

б) При сложении двух последовательностей сумма порядковых номеров всех букв получаемой при этом последовательности и сумма порядковых номеров всех букв обоих слагаемых имеет один и тот же остаток от деления на 26. Значит, разность упомянутых сумм должна делиться на 26 без остатка. Докажем утверждение пункта б) методом от противного. В самом деле, если такая последовательность из 26 различных букв существует, то упомянутая разность равна сумме порядковых номеров букв алфавита. Однако сумма $ 1+2+\dots+26=13\cdot27=26\cdot13+13$ при делении на 26 имеет остаток 13. Это доказывает утверждение пункта б).

Замечание. Утверждение пункта б) остается в силе для любого алфавита из четного числа букв.

Представляет интерес доказательство пункта б), предложенноеучастниками олимпиады.

При делении на любое четное число суммы двух четных или двух нечетных чисел получается четный остаток, а при делении суммы четного и нечетного чисел - нечетный остаток.

Соответствующие буквы складываемых последовательностей могут быть как одинаковой, так и различной четности. (Для краткости мы называем букву четной, если ее номер четен, и нечетной - если номер нечетен.) Будем решать задачу от противного. Предположим, что требуемая последовательность существует. Всего в сложении участвуют 52 буквы. Пар букв одинаковой и различной четности должно быть одинаковое количество, а именно 13 (так как в результате сложения должно получиться 13 четных и 13 нечетных букв). Пары букв различной четности включают в себя 26 букв. Оставшиеся 26 букв входят в 13 пар букв одинаковой четности. Однако, 13 пар букв одинаковой четности не могут содержать одинаковое количество четных и нечетных букв (так как 13 - нечетное число). Полученное противоречие доказывает утверждение пункта б).

9.2. В этой задаче условимся писать $ a\equiv b$, если числа $ a$ и $ b$ имеют одинаковые остатки при делении на 33. Пусть $ n$ - номер первой буквы искомой последовательности. Эту букву указанное число раз прибавили к букве К, в результате получили букву А. Запишем соответствующее уравнение:
\begin{displaymath}
12+1949^{1999}\cdot n \equiv1.
\end{displaymath} (1)

Имеем следующую цепочку соотношений:

\begin{displaymath}
1949^{1999}\equiv 2^{5\cdot399+4}\equiv(-1)^{399}\cdot16\equiv
-16\equiv 17.
\end{displaymath}

Уравнение (1) принимает вид: $ 12+17\cdot n \equiv1$, или
\begin{displaymath}
17\cdot n\equiv 22.
\end{displaymath} (2)

Пользуясь арифметикой остатков, несложно составить следующую таблицу
А Б В Г Д Е \myYott Ж З И Й К Л М Н О П Р С Т У Ф
17 1 18 2 19 3 20 4 21 5 22 6 23 7 24 8 25 9 26 10 27 11
 
Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я  
28 12 29 13 30 14 31 15 32 16 0  

Здесь под каждой буквой подписан остаток от деления на 33 результата умножения ее номера на 17. Как видно из таблицы, уравнение (2) имеет единственное решение $ n=11$, т.е. первая буква искомой последовательности - Й. Аналогично могут быть найдены и остальные буквы. Искомая последовательность имеет вид
\begin{displaymath}
\mathtt{ЙЩНЧЛЖАФ}.
\end{displaymath} (3)

Если последовательность (3) прибавить 17 раз к слову КРИПТОША, то получится слово АНАЛИТИК. Ясно, что если последовательность (3) прибавить к слову КРИПТОША 33 раза, то вновь получится КРИПТОША. Значит, если (3) прибавить 16 раз к слову АНАЛИТИК, то получится КРИПТОША. Получить слово КРИПТОША меньше чем за 16 прибавлений не удастся. Действительно, рассмотрим предпоследние буквы в этих словах и в последовательности (3): Ш, И, А. Очевидно, что для получения буквы Ш из буквы И необходимо букву А прибавить к И по крайней мере 16 раз.

Ответ: ЙЩНЧЛЖАФ; 16 раз.

9.3. В этой задаче условимся писать $ a\equiv b$, если числа $ a$ и $ b$ имеют одинаковые остатки при делении на 1000. Для нахождения последней буквы исходного сообщения необходимо решить уравнение
\begin{displaymath}
77\cdot n \equiv355.
\end{displaymath} (1)

Здесь $ n$ - пока неизвестное трехзначное число. Пусть $ n = 100\cdot a + 10\cdot b + c$ ($ a$, $ b$, $ c$ - цифры). Тогда


\begin{multline*}
(100\cdot a + 10\cdot b + c)\cdot 77\equiv 355 \Iff\\
\Iff 70...
... \Iff
700\cdot (a + b) + 70\cdot (b + c) + 7\cdot c\equiv 355.
\end{multline*}
Значит, $ с=5$. Далее,

\begin{displaymath}
700\cdot(a + b) + 70\cdot b + 30 \equiv0.
\end{displaymath}

Отсюда $ b=1$. Тогда

\begin{displaymath}
700\cdot a + 800 \equiv 0.
\end{displaymath}

Значит, $ a = 6$ и поэтому $ n = 615$.

Уравнение (1) могло быть решено иначе. Умножив обе части (1) на 13, получим $ 1001\cdot n \equiv 13\cdot 355$. Ясно, что последние три цифры числа, стоящего в левой части равенства, совпадают с тремя последними цифрами самого числа $ n$. Вычислив $ 13\cdot355= 4615$, найдем $ n = 615$. Теперь аналогично решаем уравнение (1), в правой части которого стоят другие трехзначные цифровые группы шифрсообщения (850, 547, 550 и т.д.).

Искомая цифровая последовательность имеет вид

\begin{displaymath}
121332252610221801150111050615.
\end{displaymath}

Ответ: КЛЮЧШИФРАНАЙДЕН.

9.4. Сначала восстановим магический квадрат. Сумма чисел во всех клетках квадрата равна $ 1+2+\ldots+16=\nfrac{16\cdot17}{2}=136$, значит, в каждом столбце (а также в строке, на диагонали) сумма чисел составляет $ 136:4=34$. Попытаемся построить магические квадраты с суммой на линии, равной 34, и единицей в правом нижнем углу. Имеется несколько таких квадратов. Например,

4 10 7 13
5 15 2 12
9 3 14 8
16 6 11 1
10 5 11 8
6 9 7 12
3 4 14 13
15 16 2 1
12 2 5 15
7 13 10 4
9 3 8 14
6 16 11 1
16 3 2 13
5 10 11 8
9 6 7 12
4 15 14 1


Расставляя буквы в соответствии с условием, только в одном случае, отвечающем четвертому квадрату, получаем читаемый текст:

Ы Р Е У
С Т Е В
Ь Т А Б
Е В К П
        
П Е Р Е
С Т А В
Ь Т Е Б
У К В Ы


Ответ: $\vcenter{\hbox to2.5cm{%
\begin{tabular}{\vert r\vert r\vert r\vert r\vert}\hl...
...14 &
1  \hline
\end{tabular}\hfill}}\qquad,\quad\mathtt{ПЕРЕСТАВЬТЕБУКВЫ}.$

9.5. Пусть $ \angle AOB=\alpha$, $ \angle COD=\beta$, $ \angle AOE=\gamma$, $ r$ радиус окружности (см. рис. 25). Условие (4) задачи эквивалентно равенству

\begin{displaymath}
S_{ABE}+S_{CED}=S_{AED}.
\end{displaymath}

С учетом выражений $ S_{AOB}+S_{AOE}-S_{BOE}=S_{ABE}$ и $ S_{EOD}+S_{OCD}\double-S_{COE}=S_{ECD}$, это равенство можно записать в виде:
\begin{multline}
r^2(\sin\alpha+\sin\gamma)-r^2\sin(\alpha+\gamma)
+r^2(\sin\be...
...os\gamma)\cdot\sin\beta
=\sin\gamma\cdot(\cos\alpha+\cos\beta).
\end{multline}

Рис. 25.

\epsfbox{oli89.951}

Без ограничения общности можно считать, что $ \gamma\leq90^\circ$. Далее, поскольку координаты точки $ E$ - целые числа, меньшие 5, могут иметь место три случая.

Случай 1. $ \sin\gamma=1$. Равенство (1) примет вид: $ \sin\alpha+\sin\beta=\cos\alpha\double+\cos\beta$. Это дает два варианта расположения точек: 1) $ B(-3;4)$, $ C(4;3)$, $ E(0;-5)$; 2) $ B(-4;3)$, $ C(3;4)$, $ E(0;-5)$.

Случай 2. $ \sin\gamma=\nfrac{3}{5}, \cos\gamma=\nfrac{4}{5}$. Из (1) получаем: $ \sin\alpha+9\cdot\sin\beta\double=3\cdot\cos\alpha+3\cdot\cos\beta$. Последнее равенство невозможно, так как правая часть равенства строго меньше 6, а левая часть равенства не меньше, чем $ \nfrac{3}{5}+9\cdot\nfrac{3}{5}=6$.

Случай 3. $ \sin\gamma=\nfrac{4}{5}, \cos\gamma=\nfrac{3}{5}$. Равенство (1) запишется в виде: $ \sin\alpha\double+4\cdot\sin\beta=2\cdot\cos\alpha+2\cdot\cos\beta$. Это равенство невозможно, так как $ \sin\alpha+4\cdot\sin\beta\geq\nfrac{3}{5}+4\cdot\nfrac{3}{5}$ и $ 2\cdot\cos\alpha+2\cdot\cos\beta\leq2\cdot\nfrac{4}{5}$.

Ответ: 1) $ B(-3;4)$, $ C(4;3)$, $ E(0;-5)$; 2) $ B(-4;3)$, $ C(3;4)$, $ E(0;-5)$.

9.6. Выделим под знаками радикала полный квадрат:

\begin{displaymath}
\sqrt{-\left(x+\frac{1}{2}\right)^2+a^2}\geq
1+
\sqrt{-\left(x-\frac{1}{2}\right)^2+4}.
\end{displaymath}

В результате замены $ x+\nfrac{1}{2}=t$ неравенство примет вид:

\begin{displaymath}
\sqrt{a^2-t^2}\geq1+\sqrt{4-(t-1)^2}.
\end{displaymath}

Для решения последнего неравенства изучим взаимное расположение на плоскости $ (t,y)$ полуокружностей

\begin{displaymath}
y_1(t)=\sqrt{a^2-t^2} (\text{центр} (0;0), \text{радиус} \vert a\vert)
\end{displaymath}

и

\begin{displaymath}
y_2(t)=1+\sqrt{4-(t-1)^2} (\text{центр} (1;1), \text{радиус} 2).
\end{displaymath}

Точки пересечения полуокружностей (если этих точек две) расположены симметрично относительно прямой, соединяющей их центры. В данном случае это прямая $ y=t$. Рассмотрим вначале качественно возможные взаимные расположения полуокружностей. Если величина $ \vert a\vert$ мала, то полуокружности не пересекаются (рис. 26).

Рис. 26.

\epsfbox{oli89.961}

Рис. 27.

\epsfbox{oli89.962}

Рис. 28.

\epsfbox{oli89.963}

Рис. 29.

\epsfbox{oli89.964}

С ростом $ \vert a\vert$ у полуокружностей появляется общая точка $ B$ (с абсциссой $ t_0$) (рис. 27). При дальнейшем увеличении $ \vert a\vert$ точка пересечения $ B$ ``движется'' по окружности $ y_2(t)$ по часовой стрелке. Значение $ \vert a\vert$, при котором точка $ B$ совпадает с точкой $ C(1;3)$, является критическим, так как при дальнейшем увеличении $ \vert a\vert$ полуокружности имеют две точки пересечения (рис. 28). И, наконец, при $ \vert a\vert$, превосходящем некоторое значение, полуокружности вновь не пересекаются (рис. 29). Рассмотрим указанные случаи подробно.

Случай 1. При $ \vert a\vert<OA=\sqrt2$ полуокружности не пересекаются, и неравенство решений не имеет (рис. 26).

Случай 2. Полуокружности имеют единственную точку пересечения с абсциссой $ t_0<1$ (рис. 27). При этом $ \sqrt2\leq\vert a\vert<OC=\sqrt{10}$. Решение неравенства имеет вид $ t\in[-1;t_0]$.

Случай 3. Полуокружности имеют две точки пересечения (рис. 28). При этом $ \sqrt{10}\leq\vert a\vert\leq 2+\sqrt2$. Решение неравенства имеет вид $ t\hph\in[-1;t_1]\cup[t_2;3]$. При $ \vert a\vert=2+\sqrt2$ имеет место касание полуокружностей (можно считать, что точек пересечения по-прежнему две, но просто они совпадают).

Случай 4. При $ \vert a\vert>2+\sqrt2$ полуокружности вновь не имеют общих точек, и $ t\in[-1;3]$.

Найдем теперь точные выражения для абсцисс $ t_1,t_2$ точек пересечения окружностей. Эти величины удовлетворяют системе

\begin{displaymath}
\left\{\begin{array}{@{}r@{\:=\:}l@{}}
t^2+y^2&a^2\\
(t{-}...
...Longrightarrow
t^2+\left(\frac{a^2{-}2}{2}{-}t\right)^2=a^2.
\end{displaymath}

Решая квадратное уравнение, находим

\begin{displaymath}
t_{1,2}=\frac{a^2-2\mp\sqrt{12\cdot a^2-a^4-4}}{4}
\hskip2dd.
\end{displaymath}

Итак, решение неравенства имеет вид:

1. $ \vert a\vert<\sqrt2$ $ \Longrightarrow$ решений нет.

2. $ \sqrt2\leq\vert a\vert<\sqrt{10}$ $ \Longrightarrow$ $ t\in[-1;t_1]$.

3. $ \sqrt{10}\leq\vert a\vert\leq 2+\sqrt2$ $ \Longrightarrow$ $ t\in[-1;t_1]\cup[t_2;3]$.

4. $ \vert a\vert>2+\sqrt2$ $ \Longrightarrow$ $ t\in[-1;3]$.

Переходя к переменной $ x$ и используя явные выражения для $ t_1,t_2$, получаем окончательный

Ответ:

1. $ \vert a\vert<\sqrt2$ $ \Longrightarrow$ решений нет.

2. $ \sqrt2\leq\vert a\vert<\sqrt{10}$ $ \Longrightarrow$ $ x\in[-\nfrac{3}{2};\nfrac{a^2-2-\sqrt{12\cdot a^2-a^4-4}}{4}]$.

3. $ \sqrt{10}\leq\vert a\vert\leq 2+\sqrt2$ $ \Longrightarrow$
$ x\in[-\nfrac{3}{2};
\nfrac{a^2-2-\sqrt{12\cdot a^2-a^4-4}}{4}]\cup[
\nfrac{a^2-2+\sqrt{12\cdot a^2-a^4-4}}{4};\nfrac{5}{2}]$.

4. $ \vert a\vert>2+\sqrt2$ $ \Longrightarrow$ $ x\in[-\nfrac{3}{2};\nfrac{5}{2}]$.


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


Написать комментарий
 Copyright © 2000-2015, РОО "Мир Науки и Культуры". ISSN 1684-9876 Rambler's Top100 Яндекс цитирования