Здавалка
Главная | Обратная связь

C r y p t o g r a p h i c a l g o r i t h m 4 страница



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

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

Решение

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

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

Гг

Задача 1. Для рисования на большой прямоугольной доске используется мел с квадратным сечением со стороной 1 см. При движении мела стороны сечения всегда параллельны краям доски. Как начертить выпуклый многоугольник площадью 1 м2 с наименьшей площадью границы (площадь границы не входит в площадь многоугольника)?

Решение

Если на доске нарисовать некоторый (выпуклый) многоугольник, то найдутся такие граничные "точки" этого многоугольника, которые являются ближайшими к одному из краев доски. Площадь границы прямоугольника, содержащей все такие "точки", равна площади границы нарисованного выпуклого многоугольника (см. рис.15 ).

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

Если многоугольник со сторонами a и b имеет площадь 10000 см2, то площадь его границы равна

КАРТИНКА

Минимум достигается в случае, когда возводимое в квадрат выражение равно 0. В этом случае a=100, что влечет b=100. Таким образом, наименьшую площадь границы, равную 404 см2, имеет квадрат со стороной 1 м.

Задача 2. При a > 0, b > 0, c > 0 докажите неравенство:

a3+b3+c3+6abc > 1/4 (a+b+c)3.

Решение

Из однородности всех членов следует, что неравенство эквивалентно неравенству a3+b3+c3+6abc > 1/4 при условии a+b+c=1, a > 0, b > 0, c > 0.

Пусть с - минимальное из чисел a,b,c (0 < c ≤ 1/3) и a=x. Тогда


A = a3+b3+c3+6abc-1/4 =


=x3+(1-c-x)3+c3+6x(1-c-x)c-1/4=3(1-3c)x2-3(1-c)(1-3c)x+(1-c)3+c3-1/4.

Находим минимум квадратного трехчлена с параметром с и положительным коэффициентом при х2. Минимум достигается в точке x=(1-c)/2, при этом значение A будет положительным.
Задача 3.Знаменитый математик Леонард Эйлер в 1759 г. нашел замкнутый маршрут обхода всех клеток шахматной доски ходом коня ровно по одному разу. Прочтите текст, вписанный в клетки шахматной доски по такому маршруту (см. рис.7). Начало текста в a4.

 

Решение

Последовательность обхода доски показана на рисунке:

 

 

Задача 4.В компьютерной сети используются пароли, состоящие из цифр. Чтобы избежать хищения паролей, их хранят на диске в зашифрованном виде. При необходимости использования происходит однозначное расшифрование соответствующего пароля. Зашифрование пароля происходит посимвольно одним и тем же преобразованием. Первая цифра остается без изменения, а результат зашифрования каждой следующей цифры зависит только от нее и от предыдущей цифры.

Известен список зашифрованных паролей: 4249188780319, 4245133784397, 5393511, 428540012393,
4262271910365, 4252370031465, 4245133784735 и два пароля 4208212275831, 4242592823026, имеющиеся в зашифрованном виде в этом списке. Можно ли определить какие-либо другие пароли? Если да, то восстановите их.


Решение

Процедура зашифрования может быть полностью описана квадратной таблицей 10×10. На пересечении строки с номером i и столбца с номером j записываем цифру, в которую при зашифровании переходит цифра j, если она стоит в пароле после цифры i. Из однозначности расшифрования следует, что в каждой строке каждая цифра встречается ровно один раз.

Обозначим через ш1, ш2, ... ,ш7 и о1, о2 зашифрованные пароли и два известных пароля в порядке, определяемом условием задачи. Процедура зашифрования сохраняет длину, поэтому ш3 и ш4 не могут соответствовать ни о1, ни о2. Предположив, что ш1 соответствует о1, получим часть таблицы, в которой в одной строке две одинаковые цифры. Это означает, что предположение неверно. Составляя таблицы, убеждаемся, что о2 не шифруется ни в ш6, ни в ш7, ни в ш5. В результате таких рассуждений остается только один вариант перехода о1 - ш2, о2 - ш5. Заполнение таблицы будет следующим:

 
                 
                 
           
                 
                 
                 
                   
                 
               
                   
                     

 

 
               
                 
 
               
                 
               
                   
                 
               
                 


Очевидно, что в строке с номером 2 в последней клетке стоит 1. Знание этой таблицы позволяет однозначно расшифровать ш3: получится 5830829. Пароли, соответствующие ш1, ш4, ш6, ш7, восстанавливаются не полностью.

Задача 5.Какое наименьшее число соединений требуется для организации проводной сети связи из 10 узлов, чтобы при выходе из строя любых двух узлов связи сохранялась возможность передачи информации между любыми двумя оставшимися (хотя бы по цепочке через другие узлы)?

Решение

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

 

недопустима, ибо при выходе из строя узлов B и C узел A становится недоступным. Значит, всего линий должно быть не менее [(10×3)/2]=15. Вот пример, удовлетворяющий условиям задачи с 15-ю линиями связи:

Приведем доказательство. Если вышли из строя два узла на одном пятиугольнике, то связь сохранится через другие пятиугольники. Если вышли из строя по одному узлу на разных пятиугольниках, то связь сохранится по линиям, соединяющим эти пятиугольники.

 

Гг

Задача 1. Разложите число 230+1 на простые сомножители.

Решение

Число 230+1 представляет собой сумму кубов, сумму пятых степеней, а также из него можно выделить полный квадрат. Каждое из этих представлений позволяет найти некоторые делители исходного числа:

230+1=210×3+13=(210+1)(220-210+1) =


= 1025×(220-210+1)=41×25×(220-210+1).


230+1=26×5+15 = (26+1)(224-218+212-26+1) =


= 65×(224-218+212-26+1)=13×5×(224-218+212-26+1).


230+1=(215+1)2-2×215=(215+28+1)(215+1-28) =


= 33025×32513 = 25×1321×32513

Таким образом, установлено, что среди простых делителей числа 230+1 содержатся 41, 13, 5. Непосредственной проверкой получаем равенство 32513=41×793 = 41×13×61.

Осталось проверить, что 1321 - простое число. Для этого достаточно показать, что 1321 не делится ни на одно простое число, меньшее 37 (372=1369, 1369 > 1321).
Задача 2. Для всех действительных чисел a, b решите уравнение


a / (1 - bx) = b / (1 - ax)

Решение

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

1. Пусть а=0, b=0. Уравнение имеет вид [0/(1-0x)]=[0/(1-0x)], то есть x - любое число.

2. Пусть a=0, b ≠ 0. Уравнение имеет вид [0/(1-bx)]=[b/(1-0x)], или 0=b, то есть не имеет решений.

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

4. При a ≠ 0, b ≠ 0 удобно рассмотреть три случая: а) a=b, b) a=-b, c) a ≠ ±b.
a) a=b: [a/(1-ax)]=[a/(1-ax)], x ≠ [1/a], x - любое, кроме [b][1/a].
b) mumu a=-b: mumu[a/(1+ax)]=[(-a)/(1-ax)], mumu x ≠ ±[1/a], mumu [1/a]+x=-[1/a]+x, mumu[2/a]=0, решений нет.
c) a ≠ ±b:

a=b, x1, x1,
1-bx=1-ax,
x(a-b)=1-1,
x=(a-b)ab=1.

Задача 3. Сообщение, подлежащее зашифрованию, представляет собой цифровую последовательность, составленную из дат рождения 6 членов оргкомитета олимпиады. Каждая дата представлена в виде последовательности из 8 цифр, первые две из которых обозначают день, следующие две - месяц, а остальные - год. Например, дата рождения великого математика Л. Эйлера 4 апреля 1707 года представляется в виде последовательности 04041707. Для зашифрования сообщения строится ключевая последовательность длины 48. Для ее построения все нечетные простые числа, меньшие 100, выписываются через запятую в таком порядке, что модуль разности любых двух соседних чисел есть та или иная степень числа 2. При этом каждое простое число выписано ровно один раз, а числа 3, 5 и 7 записаны в виде 03, 05 и 07 соответственно. Удалив запятые из записи этой последовательности, получим искомую ключевую последовательность.

При зашифровании цифровой последовательности, представляющей сообщение, ее цифры почленно складываются с соответствующими цифрами ключевой последовательности, при этом каждая полученная сумма заменяется ее остатком от деления на 10. В результате зашифрования сообщения получена последовательность:

Определите даты рождения членов оргкомитета олимпиады.

Решение

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

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

 
число  
соседи
13, 19, 43, 7, 3
13, 19
79, 43, 31
61, 37
79, 67, 19
97, 73.

Учитывая, что первая цифра в номере месяца принимает значения только 0 или 1, построим следующую таблицу:

 

                                   
                       
                                   
                                   
                                             
                                             
                                             


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

Снова выпишем известные числа последовательности простых чисел и варианты для их соседей (первые две строки таблицы на этом шаге не понадобятся):

                       
                                   
                                   
                                             
                                             
                                             

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

             
                                     
                                     
                                             
                                             

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

       
               
               


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

 

   
               
               


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

Таким образом, приходим к выводу, что возможен всего один вариант ключевой последовательности. Получим окончательный вариант таблицы и найдем ответ:

 

Задача 4.Сообщение, составленное из нулей и единиц, шифруется двумя способами. При первом способе каждый нуль заменяется на последовательность из k1 нулей и следующих за ними k2 единиц, а каждая единица заменяется на последовательность из k3 нулей. При втором способе шифрования каждая единица заменяется на последовательность из k4 единиц и следующих за ними k5 нулей, а каждый нуль заменяется на последовательность из k6нулей. При каких натуральных значениях ki, i=1,2,...,6, найдется хотя бы одно сообщение, которое будет одинаково зашифровано обоими способами? Укажите общий вид таких сообщений.







©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.