Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Зашифрование с помощью прогрессии



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

Найдите исходное цифровое сообщение по шифрованному сообщению:
4 2 3 4 6 1 4 0 5 3 1 3

Решение

Согласно условию, исходное сообщение состоит из двух пятерок цифр: A1A2A3A4A5 и B1B2B3B4B5. Пусть C1C2 - последние две цифры суммы чисел, изображенных этими пятерками. Через ab обозначим последнюю цифру суммы чисел a и b. Пусть D обозначает цифру переноса (цифру десятков) суммы (A5 ⊕ B5). По условию имеем, что A5B5=C2 и (A4B4)D=C1.

Пусть 1 - первый член, а X - разность арифметической прогрессии, которую коммерсант использовал при шифровании. Тогда из условия получаем:

A1 1 = 4 (1)
A2 (1+X) = 2 (2)
A3 (1+2X) = 3 (3)
A4 (1+3X) = 4 (4)
A5 (1+4X) = 6 (5)
B1 (1+5X) = 1 (6)
B2 (1+6X) = 4 (7)
B3 (1+7X) = 0 (8)
B4 (1+8X) = 5 (9)
B5 (1+9X) = 3 (10)
B5 (1+9X) = 3 (10)
((A4 B4) D) (1+10X) = 1 (11)
(A5 B5) (1+11X) = 3 (12)

 

Обозначим символом A  B равенство остатков от деления на 10 чисел A и B. Тогда записи AB=C и (A+B)  C имеют одинаковый смысл. Если A  B и C D, то A+B  C+D, AB  CD. Всегда A  A, так как остаток от деления единствен.

Из соотношений (4), (5), (9) и (10) находим соответственно:

A4  4(1+3X)(13)A5  6(1+4X),(14)B4  5(1+8X)(15)B5  3(1+9X)(16)

 

Подставляя эти значения в равенства (11) и (12), получим следующие равенства: 9+DX  1 и 92X  3. Отсюда следует, что

X  (2D) (17)
1  2D (18)

Подставив X из (17) и 1 из (18) в (1), (2),(3), (13, (14), (6), (7), (8), (15), (16), найдем выражения для цифр исходного сообщения:

A1  42D, A2  4D, A3  7, A4  D, A5  4+2D)  
B1  1+3D, B2  6+4D, B3  4+5D, B4  1+6D  
B5  1+7D  

Можно ли так шифровать?

Рассмотрим преобразование цифрового текста, в котором каждая цифра заменяется остатком от деления значения многочлена F(х)=b(x3+7x2+3x+a) на число 10, где a, b - фиксированные натуральные числа.

Выясните, при каких значениях a, b указанное преобразованиеможет быть шифрпреобразованием (т. е. допускает однозначное расшифрование).

 

Решение

Обозначим через f(x) - остаток от деления значения многочлена F(x) на 10. Для однозначного расшифрования необходимо и достаточно, чтобы разным значениям x соответствовали разные значения f(x). Поэтому f(0), f(1), ..., f(9) принимают все значения от 0 до 9. Найдем эти значения:

f(0) = r10(b(a+0)) f(1) = r10(b(a+1))
f(2) = r10(b(a+2)) f(3) = r10(b(a+9))
f(4) = r10(b(a+8)) f(5) = r10(b(a+5))
f(6) = r10(b(a+6)) f(7) = r10(b(a+7))
f(8) = r10(b(a+4)) f(9) = r10(b(a+3))

где r10(y) - остаток от деления числа y на 10.

Отсюда, пользуясь свойствами остатков, замечаем, что b должно быть нечетным (иначе f(x) будут только четные числа) и b не должно делиться на 5 (иначе f(x) будут только 0 и 5). Непосредственной проверкой можно убедиться, что при любом a и при всех b, удовлетворяющим приведенным условиям, гарантируется однозначность расшифрования.

Поиск слова

При зашифровании текста на русском языке (в текстах строчные и заглавные буквы не различались, а пробелы и знаки препинания опускались) каждую букву заменяли парой цифр. При этом разные буквы текста заменялись разными парами, а одинаковые - одинаковыми. Найдите все возможные места расположения слова ПОДЪЕЗД в исходном тексте по шифрованному тексту:

92 97 36 72 97 92 70 73 97 90 97 72 38 39 74 76
97 34 79 78 97 70 76 74 72 74 73 74 76 70 70 97
76 74 96 74 37 39 75 97 70 39 74 79 39 37 71 74
98 35 94 90 98 97 94 96 74 98 74 76 97

 

Решение

Если две буквы с порядковыми номерами Т1 и Т2 зашифрованы в буквы с порядковыми номерами С1 и С2 с помощью одной и той же буквы, то остатки от деления чисел (С1Т1) и (С2 Т2) на 30 равны между собой и совпадают с порядковым номером шифрующей буквы (порядковым номером буквы Я удобно считать число 0). Тогда, с учетом соглашения о порядковом номере буквы Я, справедливо, что Т1 равен остатку от деления числа (Т2+(С1С2)) на 30, а, вместе с тем, Т2 равен остатку от деления числа (Т1+(С2С1)) на 30. Если каждое из выражений в скобках заменить соответствующим остатком от деления на 30, то упомянутая связь не нарушится.

Представим в виде набора порядковых номеров известные шифрованные сообщения (обозначим их соответственно ш. с. 1 и ш. с. 2) и слово КОРАБЛИ:

слово К О Р А Б Л И
Т

 

ш.с.1 Ю П Т Ц А Р Г Ш А Л Ж Ж Е В Ц Щ Ы Р В У У
С1

 

ш.с.2 Ю П Я Т Б Н Щ М С Д Т Л Ж Г П С Г Х С Ц Ц
С2

Возможны 15 вариантов (номер варианта обозначим буквой k) расположения слова КОРАБЛИ в каждом из двух исходных сообщений (и. с. 1, и. с. 2).

Вначале для каждого из 15 вариантов расположения слова КОРАБЛИ в и. с. 1 найдем соответствующий участок и. с. 2. Имеем:

C2C1

 

 

T1
T2 T21 T22 T23 T24 T25 T26 T27

Поэтому для участка и. с. 2 получаем следующие 15 вариантов:

k
T21
T22
T23
T24
T25
T26
T27

Теперь для каждого из 15 вариантов расположения слова КОРАБЛИ в и. с. 2 найдем соответствующий участок и. с. 1. Имеем:

C1C2

 

 

T2
T1 T11 T12 T13 T14 T15 T16 T17

Поэтому для участка и. с. 1 получаем следующие 15 вариантов:

k
T11
T12
T13
T14
T15
T16
T17

 

Заменим порядковые номера в найденных вариантах участков и. с. 1 и и. с. 2 на буквы русского алфавита. Получаем следующие таблицы:

k
  К К Ц Е Л Ж А Э Ь Г Х О Л Л В
  О Ь К П Л Д Б Я З Щ Т П П Ж Е
участок Э М С Н Ж Г Б К Ы Ф С С И З Ч
и.с.2 Ы Б Э Ц У С Щ М Д Б Б Ш Ч З Е
  В Ю Ч Ф Т Ь Н Е В В Щ Ш И Ж Р
  Э Б Ю Ы Д Ц П М М Г В Т Р Щ О
  Я Ы Щ В Ф Н К К Б А Р О Ч М М

 

k
  К К Э О И Н У Ц Ш Р Ю Е И И С
  О Б Т Н С Ч Ь Э Ф В К Н Н Х Ц
участок Г Ф П У Щ Э Я Ц Д М П П Ч Ш И
и.с.1 Д Я Г К Н П Ж Ф Ы Я Я З И Ш Ь
  А Д Л О Р З Х Э А А И К Щ Ы Т
  О Ф Ч Щ С Я Ж К К Т У Г Е Ы З
  Т Х Ч П Э Д З З Р С Б Г Щ Е Е


Из таблиц видно, что осмысленными являются варианты:

и.с.1 = К О Г Д А О Т . . . . . . . К О Р А Б Л И
и.с.2 = К О Р А Б Л И . . . . . . . В Е Ч Е Р О М

Квадрат числа

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

Решение

Квадрат натурального числа может оканчиваться только на цифры 0, 1, 4, 5, 6, 9. Число 0ј0 натуральным не является. Число 5...5 не может быть квадратом, так как оно делится на 5, но не делится на 25. Аналогично 6...6 ≠ n2, так как это число делится на 2, но не делится на 4. Числа 4ј4 и 9ј9 являются полными квадратами в том и только том случае, когда полным квадратом будет 1ј1.

Докажем, что 1...1 ≠ n2. Предположим, что это не так: существует такое натуральное число n, что 1...1 = n2. Тогда n = 10k ± 1 и, следовательно, 100k2 ± 20k = 1...10 ⇔ 10k2 ± 2k = 1...1. Получили противоречие: нечетное число равно четному.

Гамма Фибоначчи

Для зашифрования сообщения используют последовательность неотрицательных целых чисел x1, x2,…, удовлетворяющую соотношению xk+3=xk+xk+2, k=1,2,… Две строки известного стихотворения, последние 5 букв которых совпадают, зашифровали следующим образом. Первую букву заменили числом согласно таблице

А Б В Г Д Е Ж З И К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я

и сложили с x1, вторую заменили и сложили с x2 и т.д. Затем все суммы заменили остатками от деления на 31, а остатки заменили буквами согласно таблице. Получили текст

СЕЗНПБКЬЛЧЕЮЩЦТНИЭЛЬЩБШЬЕЮ

ЛУАЕЧЖЪЭШЭЛЪШЩХЧШДЮВЫЮИД.

Восстановите три буквы, соответствующие в таблице числам x1,x2,x3, и прочитайте двустишие.

Решение

Обозначим a = x1, b = x2, c = x3. Так как эти числа соответствуют буквам в таблице, они принимают значения от 0 до 30. Из соотношения

xk+3 = xk + xk+2

последовательно получим

x1 = a ,

x2 = b ,

x3 = c,

x4 = a + c,

x5 = a + b + c,

x6 = a + b+ 2c,

x7 = 2a + b+ 3c,

x8 = 3a + 2b+ 4c,

x9 = 4a + 3b+ 6c,

x10= 6a + 4b+ 9c,

и т.д.

При дальнейшем построении этой последовательности используем следующие правила.

 

Для построения следующей строки последнюю строку складываем с предпредпоследней.

Легко заметить, что столбцы чисел отличаются сдвигом по вертикали, поэтому сначала можно определить только коэффициенты при c.

Так как нас интересуют только остатки от деления на 31, то, например, 41c = 31c + 10c можно заменить на 10c.

Продолжая аналогично, получим

x11 = 13,

x12 = 19,

x13 = 28,

x14 = 10,

x15 = 29,

x16 = 26,

x17 = 5,

x18 = 3,

x19 = 29,

x20= 3,

x21 = 6,

x22 = 6a + 3b+ 4c,

x23 = 7a + 4b+ 13c,

x25 = 13a + 7b+ 17c,

x26= 17a + 13b+ 24c,

x26= 6a + 4b+ 9c,

Используя сдвиги столбцов, получили значения x22, x23, x24, x25, x26. Продолжая аналогично, получим последние пять значений x46, x47, x48, x49,x50:

x27 = 6,

x28 = 23,

x29 = 16,

x30 = 22,

x31 = 14,

x32 = 30,

x33 = 21,

x34 = 4,

x35 = 3,

x36= 24,

x37 = 28,

x38 = 0,

x39 = 24,

x40= 21,

x41 = 21,

x42 = 14,

x43 = 4,

x44= 25,

x45 = 8,

x46 = 8a + 25b+ 12c,

x47 = 12a + 8b+ 6c,

x48 = 6a + 12b+ 14c,

x49= 14a + 6b+ 26c,

x50= 26a + 14b+ 1c.

Итак, получено выражение чисел x22, x23, x24, x25, x26 и чисел x46, x47, x48,x49, x50 через a, b, c. Обозначим через Оi, Шi числа, соответствующие i-м буквам стихотворения и полученного шифрованного текста. Тогда числа О22+x22 и Ш22 имеют одинаковые остатки от деления на 31. То же самое и с числами О46+x46 и Ш46.

А так как числа О22 и О46 одинаковые, рассмотрев разности соответствующих частей, получим, что

x46 - x22 и Ш46 - Ш22 (*)

дают одинаковые остатки от деления на 31.

Последним пяти буквам первой строки шифрованного текста соответствуют следующие числа Шi:

Б, Ш, Ь, Е, Ю — 1, 23, 27, 5, 29,

а последним буквам второй строки — следующие:

В, Ы, Ю, И, Д — 2, 26, 29, 8, 4.

 

2a − 9b + 8c = 1,
8a + 2b − c = 3,
−a + 8b + c = 2,
a − b + 9c = 3,
9a + b + 8c = 6,

 

где равенство означает равенство остатков от деления на 31. При этом использовали правило 3. Например, в первом уравнении +22b заменили на −9b. Осталось решить полученную систему. Складывая второе и третье, четвертое и пятое, третье и четвертое уравнения, получим


7a + 10b = 5, (**)10a + 17c = 9,7b + 10c = 5.

Выразим b и c через a и подставим в первое уравнение:

b = (5 − 7a)/10, c = (9 − 10a)/17,

2a − 9((5 − 7a)/10) + 8((9 − 10a)/17) = 1,

340a − 9·17(5 − 7a) + 80(9 − 10a) = 170,

611a = 215,

22a = 29.

Последнее уравнение можно решить методом подбора и обнаружить, что 22 ·14 и 29 дают одинаковые остатки от деления на 31. Итак,

a=14.

Из системы (**) находим, что 10b = 0 и 10с = 5, откуда

b=0,
c=16.

Зная a, b, c, можно последовательно найти все xi и из соотношения Oi=Шi-xiполучить стихотворение:

ВЕЧОРТЫПОМНИШЬВЬЮГАЗЛИЛАСЬ
НАМУТНОМНЕБЕМГЛАНОСИЛАСЬ

Последние цифры

Найдите:

а) последнюю цифру числа 22002;

б) три последние цифры числа 22002.

Решение

а) Большинство участников с этой задачей справились. Для ее решения надо рассмотреть последовательность степеней двойки и обнаружить закономерность: 21 =2, 22=4, 23 = 8, 24 = ...6, 25 = ...2 и т.д. Последние цифры 2, 4, 8, 6 периодически повторяются. Таким образом, 22002 = (2500)4·22= (...6)4 ·4 = ...6 ·4 = ...4. Последняя цифра — 4.

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

Первое решение. Некоторые школьники, используя умножение на 2, получили степени двойки до 2103 включительно и при этом заметили, что 23=8 и 2103=... 008, а перед этим было число 2102=...504. Значит, последовательность остатков 008,..., 504 длины 100 повторяется, начиная с 23. Таким образом, на число 2002 приходится остаток 504.

Второе решение. Легко получить следующие соотношения:

210 = 1024,
220 =... 24 · ... 24 = ... 576,
240 =... 576 · ... 576 =... 776,
280 =... 776 · ... 776 =... 176,
2160 =... 176 · ... 176 =... 976,
2320 =... 976 · ... 976 =... 576.

Выписав 4 произведения трехзначных чисел, дальше сразу получаем

2640 = ... 776,
21280 = ... 176.

Отсюда 22002 = 4 · 21280 · 2640 · 280 = 4 · 176·176 · 776 = 4 · 976 · 776 =504.

В последней строке пользуемся тем, что 1762=...976.

Третье решение. Несложно вычислить следующее:

210 = ... 024,
2100 = ((... 24)3 )3 · ... 24 = ... 376,
376 · 376 = ... 376,
22002 = 22 · (2100)20 = 4 · ... · 376 = ... 504.

Общий подход. Имеет место соотношение 22k ·22k=22k+1. Следовательно, путем нескольких умножений трехзначных чисел можно получить 220 = 2, 221 = 4, 222 = 16, 223 = 256, 224 = ...536, 225 = ...296,
226 = ...616, 227 = ...456, 228 = ...936, 229 = ...096, 2210 = ...216

Раскладывая 2002 по степеням двойки:

Раскладывая 2002 по степеням двойки:

2002=1024+512+256+120+64+16+2,

Получим

22002 = ...216 ·...096 ·...936 ·...456 ·...616 ·...536 ·...4.

Проведя несколько умножений, получим, что последние три цифры — 504.

Нет названия

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

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

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


Решение

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

Расстояние между центром клетки (a;b) и центром клетки (c;d) равно {(ac)2+(bd)2}. Заметим, что ac  {0,1,...,12} и bd  {0,1,...,12}. Обозначим x=ac, y=bd, z={x2+y2}. Тогда z - число натуральное, если x2 = (z+y)(zy). Отсюда получаем, что

 

1=(z+y)(zy)      
z=1

 

y=0

 

 

 
22=(z+y)(z-y) Ы     
z=2

 

y=0

 

 

 

 

32=(z+y)(zy) 



z=3

 

y=0

 

или 



z=5

 

y=4

 

; и т. д.

В общем случае, если x2 = mn, то

 

        
z= m+n  

 

y=   mn    

 

 

.

 

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

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

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

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

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

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

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

 

 

 




Поиск по сайту:

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