Города и провинции криптоландии

Функции

Функции с областью определения и областью значений заданы таблицами (табл.1)

табл. 1

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

Решение

(б) Пусть . Выберем среди такую функцию , что . Пусть . Ясно, что . Выберем среди функцию такую, что . Тогда функция удовлетворяет условию . Пусть . Ясно, что . Выберем среди функцию такую, что . Тогда функция удоволетворяет равенствам . Значит, и для всех

(а) Используя рассуждения п.(б) можно прийти к одному из вариантов ответа: a = 2, b = 5, c = 6.

Ответ:a = 2, b = 5, c = 6.

Латинский квадрат

Пусть – число, стоящее в строке с номером i и столбце с номером j квадратной таблицы А (табл. 6). По таблице А построена таблица В, в строке с номером i и столбце с номером j которой стоит выражение . Набор из десяти клеток таблицы будем называть «правильным», если в нем присутствуют ровно по одной клетке из каждого столбца и каждой строки. Вычисляются произведения элементов, входящих в правильные наборы. Результатом являются выражения вида . Найдите наибольшую возможную степень правильного набора (число n) и число правильных наборов степени 1023.

Решение

Наибольшая возможная степень правильного набора получается при перемножении элементов, стоящих в таблице B на местах, соответствующих местам в таблице A, которые в табл. 6 выделены жирным шрифтом. Поэтому наибольшая степень равна .

Табл. 6

Чтобы решить вторую часть задачи, заметим, что верно следующее:

Отсюда следует, что искомый коэффициент равен числу таких наборов по 10 элементов, стоящих в различных строках и столбцах в табл. 6, в которых каждое число от 0 до 9 встречается по одному разу. Любой такой набор распадается на 3 набора: набор с числами 2, 3, 4 в нижнем правом квадрате, набор с числами 0, 1, 9 в центральном квадрате и набор с числами 5, 6, 7, 8 в верхнем левом квадрате. Непосредственной проверкой убеждаемся в том, что в каждом из указанных квадратов соответственно имеется 3, 3 и 8 таких наборов, следовательно, общее число наборов равно 3*3*8 = 72.

Ответ:2608; 72.

Номера гостиницы Криптохауз

Номера гостиницы Криптохауз открываются магнитными карточками, на которых записаны ключевые последовательности из нулей и единиц длины 8. Чтобы карточка открыла номер класса «эконом» необходимо, чтобы на ней был записан ключ вида (10****0*), номер «стандарт» - ключ вида (**1*1***), «люкс» - (1****0**). На местах, помеченных символом «*», может быть любой из двух символов. Каждый из 176 работников Криптохауза имеет ровно по 5 различных ключей и может использовать только их. Известно, что любой из существующих ключей изготовлен ровно в 16 экземплярах и находится в пользовании. Найдите минимальное число работников, открывающих номера класса «эконом», если получена информация о наличии ключей существующих типов (см. табл. 1).

Табл.1:

Вид	Количество
(**1*1***)
(1****0**)
(101*1*0*)
(1*1*10**)
(10***00*)
(101*100*)

Решение

Найдем общее число различных ключей. Для этого посчитаем количество всех используемых в гостинице ключей с учетом их повторений. Если x – общее число различных ключей, то количество всех используемых ключей с учетом их повторений равно 16х, поскольку каждый ключ изготовлен ровно в 16 экземплярах. В то же время, каждый из 176 работников имеет ровно по 5 различных ключей, а значит количество используемых в гостинице ключей с учетом их повторений равно 176×5 = 880. Отсюда, 16х=880 и х=55.

Теперь найдем количество ключей, открывающих номера класса «эконом». Ясно, что ключи имеющихся трех видов связаны так называемой диаграммой Эйлера (см. рис. 2). Пометим получившиеся 7 областей соответствующими числами. Так, например, области 7 соответствуют ключи, открывающие номера всех типов, области 1 – только номера класса «эконом» и т.д.

В соответствии с условием задачи, составим таблицу количества ключей, находящихся в различных областях диаграммы (табл. 2).

Табл. 2
Область	4U7U6U2	5U7U6U3	4U7	6U7	5U7
Количество

Из полученной таблицы легко найти количество ключей в каждой из областей 2,…,7, находя последовательно число элементов сначала в областях 4,5,6, а затем в 2,3. Эти данные запишем в таблицу (табл. 3).

Табл. 3
Область
Количество

Чтобы найти количество ключей, открывающих номера класса «эконом», нужно найти количество ключей, находящихся в области 1U4U5U7. Для этого вычтем из общего числа различных ключей суммарное количество ключей, находящихся в других областях: 55 – (7+9+15) = 24. Итак, количество ключей, открывающих только номера класса «эконом» равно 24.

Найдем минимальное число работников, имеющих ключи, которые открывают номера класса «эконом». Покажем, что это число равно [16·24/5]=77, где [x] – наименьшее целое, больше либо равное x. Расположим данные ключи в табл. 4 размера 16 на 24, в столбцах которой будут экземпляры одного и того же ключа, и покроем ее элементы «пятерками» - наборами, содержащими не более 5 различных ключей.

Табл. 4

В этих терминах задача переформулируется так: найти минимальное число «пятерок», покрывающих построенную таблицу. Начнем покрывать ее с первой строки. Ясно, что минимальное число «пятерок» равно 4, т.к. 24=5·4+4, значит оставшееся число ключей в первой строке равно 4. Теперь выберем во второй строке один отличный от этих 4-х ключей ключ (они образуют «пятерку»), и покроем строку минимальным числом «пятерок» (их ровно четыре), тогда оставшееся число ключей во второй строке равно 3. Продолжим данный процесс, выбирая в очередной строке подходящее число ключей для образования «пятерки» с оставшимися ключами предыдущей строки, и разбивая затем строку на минимальное число «пятерок».

Как видно, набор остатков в каждых последовательно идущих пяти строках будет одинаковым. Всего таких повторений - 3, т.к. 16=5·3+1, а каждое такое повторение строк дает 5·4+4=24 «пятерок». Итого всего «пятерок», приходящихся на 15 строк, будет 24·3=72. Таким образом, остается одна строка (последняя), которая даст 4 «пятерки», и в остатке еще 4 ключа, которые покроет еще одна «пятерка». Отсюда, общее их количество равно 72+4+1=77.

Ответ:77.

Решение

Если число городов m^k, а число провинций m и в каждой по m^k-1городов, то отнесем к каждой провинции с номером i города с названиями(a₀, …, a_k-1), удовлетворяющими условиям: сумма a₀₊ …+ a_k-1 кратна i. Очевидно, что каждый город будет отнесен к какой-либо провинции,и любые два города в одной провинции будут отличаться не менее чем в 2-х

символах.

Решение

Сравним посимвольно последовательности цветов, приведённые в условии и сформируем таблицу:

С К З К К К К З З К К С С К К З С З С К Светофильтры Чебурашки К К З З З С К С К С З З С К С К С К З К Светофильтры Шапокляк           *       * *     *               Ответ:420 - 29

Решение

Обозначим через х число букв, получившихся при наборе цифры 7 (их может быть от 1 до 3), у – число букв при наборе цифры 5 (1 или 2) и z – число букв при наборе цифры 9 (от 2 до 5). Перечислим возможные варианты представления числа 10 в виде суммы x+1+y+1+z:

1) 3+1+2+1+3; 2) 3+1+1+1+4; 3) 2+1+2+1+4; 4) 2+1+1+1+5; 5) 1+1+2+1+5.

Для варианта 1 получить три буквы, нажимая 7, можно только одним способом; получить две буквы, нажимая 5, можно опять-таки только одним способом; а вот получить три буквы с помощью пяти девяток можно 6 способами. В итоге, для варианта 1 имеем 1·1·6 вариантов паролей, аналогично для варианта 2 будет 1·1·4 вариантов паролей и т.д. Всего получаем 6+4+2·4+2+1=21 вариант.

Ответ:21

Совпадение при замене

Сообщение, составленное из нулей и единиц, шифруется двумя способами. При первом способе каждый нуль заменяется на последовательность из k₁ нулей и следующих за ними k₂ единиц, а каждая единица заменяется на последовательность из k₃ нулей. При втором способе шифрования каждая единица заменяется на последовательность из k₄ единиц и следующих за ними k₅ нулей, а каждый нуль заменяется на последовательность из k₆ нулей. При каких натуральных значениях k_i, i=1,2,...,6, найдется хотя бы одно сообщение, которое будет одинаково зашифровано обоими способами? Укажите общий вид таких сообщений.

Решение

Последовательность из k нулей или k единиц обозначим соответственно через 0^k или 1^k. Тогда шифрование каждого знака сообщения состоит в замене

ì ï í ï î ® 0k11k2 ® 0k3 для I способа, ì ï í ï î ® 1k40k5 ® 0k6 для II способа.

(1)

В зашифрованном сообщении все серии из единиц имеют длину k₂ для первого способа и длину k₄ для второго способа, поэтому, для совпадения результатов зашифрования необходимо, чтобы

k2=k4.

(2)

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

Пусть n - число нулей в сообщении. Тогда число нулей в зашифрованном I способом сообщении равно nk₁ + nk₃, а II способом - nk₅ + nk₆. Таким образом,

nk1 + nk3 = nk5 + nk6.

(3)

Из видно, что сообщение должно начинаться с нуля и оканчиваться единицей. Пусть перед первой единицей сообщения расположено a нулей. Тогда первые а +1 знаков сообщения представляются при шифровании в виде:

при а=1 ì ï í ï î 0k11k20k3 для I способа, 0k61k40k5 для II способа,

при а > 1 ì ï í ï î 0k11k20k11k2...0k11k20k3 для I способа, 0ak61k40k5 для II способа.

При a=1 получаем необходимость равенства k₁=k₆, а значит, с учетом - равенства k₃=k₅.

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

k1=ak6 , а - натуральное,

k1=k5+bk6, b - натуральное или нуль.

Подставляя k₁=k₅+bk₆ в , получаем равенство k₃=(1-b)k₆, которое при натуральных k₃, k₆ и b ³ 0 возможно лишь в случае b = 0. Следовательно, k₃=k₆, а значит, с учетом k₁=k₅.

Таким образом, при а > 1 необходимы условия k₂=k₄, k₅=k₁=ak₆=ak₃, где a - натуральное. Из следует, что сообщение должно иметь вид 0...01...1, где число нулей и число единиц равно a.

Ответ:При k₂=k₄, k₁=k₆, k₃=k₅ сообщения вида 0101...01 шифруются одинаково.

При k₂=k₄, k₅=k₁=ak₆=ak₃, где a - натуральное, сообщения вида (0...01...1) ... (0...01...1) (группы из a нулей и a единиц) шифруются одинаково.

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

Подбор пароля

Одна фирма предложила устройство для автоматической проверки пароля. Паролем может быть любой непустой упорядоченный набор букв в алфавите {a,b,c}. Будем обозначать такие наборы большими латинскими буквами. Устройство перерабатывает введенный в него набор P в набор Q=j(P). Отображение j держится в секрете, однако про него известно, что оно определено не для каждого набора букв и обладает следующими свойствами. Для любого набора букв P

1) j(aP)=P;

2) j(bP) = j(P)aj(P);

3) набор j(cP) получается из набора j(P) выписыванием букв в обратном порядке.

Устройство признает предъявленный пароль верным, если j(P)=P. Например, трехбуквенный набор bab является верным паролем, так как j(bab) = j(ab)aj(ab)=bab. Подберите верный пароль, состоящий более чем из трех букв.

Решение

Обозначим [j(P)] - набор j(P) , выписанный в обратном порядке.

j(cbcacbc)=[j(bcacbc)] = [j(cacbc)aj(cacbc)] = [[j(acbc)]a[j(acbc)]] = [[cbc]a[cbc]]=[cbcacbc]=cbcacbc.

В общем случае можно показать, что множество искомых наборов состоит из слов вида:

P= ì ï í ï î cb c... c k раз acb c... c k раз   k - нечетное; b c... c k раз ab c... c kраз   k - четное.

Ответ:например, cbcacbc.

НОД и НОК

Сколько существует упорядоченных пар натуральных чисел a и b, для которых известны их наибольший общий делитель d=6 и их наименьшее общее кратное m=6930. Сформулируйте ответ и в общем случае, используя канонические разложения d и m на простые множители.

Решение

Разложим числа m и d на простые множители: d=6=2·3; m=6930=2·3·3·5·7·11. Обозначим буквой t число m/d, равное произведению 3·5·7·11 . Найдем все его делители q вида: q=3^x5^y7^z11^u, где числа x, y, z и u принимают только значения 0 и 1. Тогда, как нетрудно видеть, числа q и t/q окажутся взаимно простыми. Полагая а=dq и b=dt/q, получим все искомые пары (a,b). В самом деле, в указанных выше условиях наибольший общий делитель такой пары равен d, а ее наименьшее общее кратное равно dqt/q=dt=dm/d=m. Таким образом, искомое число упорядоченных пар совпадает с числом всех делителей q вида: 3^x5^y7^z11^u, которое равно числу всех упорядоченных наборов длины 4 и состоящих только из 0 и 1. Число всех таких наборов равно 2⁴=16, так как для каждого места в наборах существует ровно 2 варианта его значений независимо от значений на других местах. В общем случае число m/d представляется в виде m/d=pⁱr^j... s^h, где p, r, ..., s - различные простые числа, а i, j, ..., h - натуральные числа. Число всех делителей вида: q=p^xr^y... s^z, где числа x, y, ..., z принимают только по два значения (0 и соответствующий натуральный показатель степени в представлении числа m/d), равно 2^k, где k - число всех простых делителей числа m/d. Если число различных простых множителей в каноническом разложении числа m/d равно k, то число различных упорядоченных пар (a,b) равно 2^k.

Ответ:16 пар (пары (a,b) и (b,a) разные). В общем случае число упорядоченных пар равно 2^k, где k - число всех простых делителей m/d.

Поворотная решетка

Ключом шифра, называемого "поворотная решетка", является трафарет, изготовленный из квадратного листа клетчатой бумаги размера n×n (n - четно). Некоторые из клеток вырезаются. Одна из сторон трафарета помечена. При наложении этого трафарета на чистый лист бумаги четырьмя возможными способами (помеченной стороной вверх, вправо, вниз, влево) его вырезы полностью покрывают всю площадь квадрата, причем каждая клетка оказывается под вырезом ровно один раз. Буквы сообщения, имеющего длину n², последовательно вписываются в вырезы трафарета, сначала наложенного на чистый лист бумаги помеченной стороной вверх. После заполнения всех вырезов трафарета буквами сообщения трафарет располагается в следующем положении и т. д. После снятия трафарета на листе бумаги оказывается зашифрованное сообщение. Найдите число различных ключей для произвольного четного числа n.

Решение

Все клетки квадрата размера n×n разобьем на непересекающиеся группы по четыре клетки в каждой. Отнесем клетки к одной и той же группе, если при каждом повороте квадрата до его самосовмещения они перемещаются на места клеток этой же группы. На рисунке показано такое разбиение на группы всех клеток квадрата 6×6, причем клетки одной группы помечены одной и той же цифрой. Всего таких групп будет n²/4 (целое, так как n - четное число). При наложении трафарета на квадрат ровно одна клетка из каждой группы окажется под его вырезами. Каждому трафарету поставим в соответствие упорядоченный набор всех клеток из таких групп, оказавшихся под вырезами трафарета при наложении его на квадрат помеченной стороной вверх. Такое соответствие является взаимнооднозначным, поскольку каждому ключу будет однозначно соответствовать упорядоченный набор из n²/4 клеток (по одной из каждой группы), вырезанных в трафарете, и наоборот. Всего таких наборов 4^n2/4. В самом деле, существует ровно четыре различных варианта выбора клетки из каждой группы независимо от выбранных клеток из других таких групп.

Ответ:Число различных ключей шифра "поворотная решетка" при четных значениях n равно 4^n2/4.

Правила доступа

На фирме работают P служащих. В гараже фирмы имеется B автомобилей. Каждый служащий имеет ключи от t автомобилей, причем ключи от разных автомобилей разные. (Будем говорить, что каждый служащий «владеет» i автомобилями.) Каждой машиной «владеют» ровно s служащих. При этом наборы ключей любых двух служащих содержат не более одного одинакового ключа. Известно также, что если служащий x не «владеет» автомобилем L, то из всех владельцев автомобиля L только у одного есть в наборе такой же ключ, как у служащего x.

Выразите числа P, B, а также общее количество ключей, имеющихся у служащих, через s и t. Числа s и t целые, большие 1.

Решение

Сопоставим каждому служащему «точку», а каждому автомобилю - «линию». Если p - служащий, владеющий автомобилем L, то будем говорить, что точка p инцидентна линии L, а линия L инцидентна точке p. При этом пару (L,р) назовем «флагом». Условия задачи можно сформулировать в следующем виде:

1. для каждой точки p имеется ровно t флагов вида

(L₁,p), (L₂,p), ј, (L_t,p);

2. для каждой линии L имеется ровно s флагов вида

(L,p₁), (L,p₂), ј, (L,p_s);

3. если точка x не инцидентна линии L, то имеются ровно одна такая линия M и одна такая точка y, что (L, y), (М,x) и (M,y) - флаги.

Изобразим условия 1-3 графически:

1. («пучок линий с центром в точке p»)

2. (точки «располагаются на линии L»)

3. («треугольники» (с точкой z) исключаются)

Вычисляя число F флагов двумя способами, получаем, согласно условиям 2 и 3, равенство F = P·t = B·s. Из условия 3 следует, что все точки располагаются на линиях пучков, центрами которых служат точки любой линии, например L. Отсюда (с учетом условий 1 и 2) следует, что число точек, не лежащих на линии L, равно t·(s-1)·5. Добавляя к этому число точек линии L, получаем общее число точек:

P = t·(s−1)·s+s = s·(t·(s−1)+1).

Теперь находим число линий:

B = p·t s = t·(t·(s-1)+1).

Наконец, число флагов равно

F = t·s(t·(s−1)+1).

Ответ:P=t·(s−1)·s+s=s·(t·(s−1)+1);B=t·(t·(s−1)+1); F=t·s(t·(s−1)+1).

Сейфовый замок (щелчки)

Кодовая комбинация сейфа устанавливается на внутренней стороне дверцы с помощью трех дисков. Каждый из них может быть установлен в одно из 20 положений, пронумерованных числами от 0 до 19, поворотом по часовой стрелке. В начальный момент диски установлены в положение (0, 0, 0). За положение с номером 19 диск не поворачивается. При повороте каждого диска на одно положение раздается щелчок. Сравните число возможных кодовых комбинаций, при установке которых раздается 33, 32, 25 щелчков.

Решение

Пусть MN - число различных комбинаций, при установке которых раздается N (NЈ 57) щелчков.

Заметим, что из соображений симметрии M_N = M_57−N. Для обоснования этого равенства достаточно установить взаимно однозначное соответствие между комбинациями, получаемыми за N и за 57−N поворотов. Это можно, например, сделать так: сопоставим комбинации (n₁,n₂,n₃), где n₁+n₂+n₃=N, комбинацию (19−n₁,19−n₂,19−n₃), получаемую за 19−n₁+19−n₂+19−n₃=57−(n₁+n₂+n₃)=57−>N щелчков. Отсюда заключаем, что число комбинаций, при установке которых раздается 32 и 25 щелчков, одинаково (M₃₂=M₂₅).

Из предыдущего рассуждения также следует, что М₂₄=М₃₃. Поэтому для завершения решения достаточно сравнить числа М₂₄ и M₂₅.

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

Все комбинации, устанавливаемые за 24 щелчка, разделим на четыре группы: насыщенные и содержащие нуль, насыщенные без нуля, ненасыщенные с нулем, ненасыщенные без нуля. Легко подсчитать, что в первую группу входит 6 комбинаций (всевозможные перестановки чисел 19, 5 и 0), во вторую - 3·4=12 (три варианта места для числа 19; для каждого из них по четыре варианта значения первой незаполненной позиции, после чего оставшееся число находится однозначно), а в третью - 3·13 = 39 (три варианта выбора места для 0; для каждого из них возможно 13 вариантов выбора значения первой незаполненной позиции числами от 6 до 18). Число комбинаций в четвертой группе находить не будем, а просто обозначим его через X.

Мысленно выпишем все комбинации, получаемые за 24 щелчка, в один столбец, а получаемые за 25 щелчков - в другой. Если какая-либо комбинация первого столбца с помощью еще одного щелчка может быть преобразована в комбинацию второго столбца, то соединим их стрелкой. Проведем все такие стрелки. Из каждой комбинации первой группы выходит ровно две стрелки. Шесть из них ведут к комбинациям, содержащим 0, а шесть - к не содержащим 0. Каждую комбинацию второй группы также можно продолжить двумя способами, и все получаемые стрелки (их 24) ведут к комбинациям, не содержащим 0. Каждая комбинация третьей группы продолжается тремя способами, всего при этом получится 39·2 стрелок к комбинациям с нулем и 39 - к комбинациям без нуля. Комбинации последней группы можно продолжить также тремя способами. При этом получится 3X стрелок, все ведут к комбинациям, не содержащим 0.

Всего получим 6+39·2 = 84 стрелки, ведущие к комбинациям с нулем, и 6+24+39+3X - без нуля.

С другой стороны, к каждой комбинации, получаемой за 25 щелчков и не содержащей 0, ведет ровно три стрелки, а к комбинациям, содержащим 0, - ровно по две. Таким образом, число различных комбинаций, получаемых за 25 щелчков, составит 42+23+X=65+X, что на 8 больше, чем 6+12+39+X=57+X - число различных комбинаций, получаемых за 24 щелчка.

Ответ:Количества комбинаций, получаемых за 25 и 32 щелчка, совпадают, комбинаций для 33 щелчков меньше.

Телебанк

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

Решение

Цифры пароля будем подбирать последовательно. Свяжемся с банком и наберем цифру 0. Если связь не оборвалась, то первая цифра пароля - 0. Если связь прервана, то первая цифра отлична от 0 и, связываясь заново с банком, пробуем набрать 1, и т.д. Не позднее чем через девять звонков мы будем точно знать, какая цифра стоит на первом месте в пароле, и сможем перейти к подбору второй цифры и т.д.

Общее количество звонков, которое понадобится для выяснения пароля, не более 7·9=63. Еще один звонок может понадобиться для получения доступа после полного выяснения пароля.

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

Где ключей больше?

Два криптографа выясняют, чей шифр содержит больше ключей. Первый говорит, что ключ его шифра состоит из 50 упорядоченных символов, каждый из которых принимает 7 значений. Второй говорит, что ключ его шифра состоит всего из 43 упорядоченных символов, зато каждый из них принимает 10 значений. Чей шифр содержит больше ключей?

Решение

У первого криптографа каждый из 50 символов ключа выбирается из 7 возможных значений. Значит, всего 7·7·...·7 = 7⁵⁰ различных вариантов выбора ключа шифра. Аналогично у второго криптографа всего 10⁴³ различных вариантов выбора ключа. Задача сводится к сравнению чисел 7⁵⁰ и 10⁴³. Это можно сделать несколькими способами:

а) 2²⁵ = 2¹⁰·2¹⁰·2⁵> 10³·10³·32 > 10⁷, следовательно,

750 = 4925< 5025 = 10025 225 < 1050 107 = 1043;

б) 7⁷< 50·50·50·7 = 125·7·10³< 900·10³< 10⁶, следовательно,

750 = 77 ·7 + 1<   (106)7   ·10 = 1043;

в) некоторые школьники использовали оценку 10/7=1,42... > 1,4.

Основные недостатки в работах:

• часто сравнивали числа 350 и 430;
• использовали приближенные равенства без оценки сверху или снизу.

Надежный сейф

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

Решение

Число вариантов положений колес для первого типа сейфов равно 100⁸, а для второго – 2¹⁰⁰. Для определения того, какой сейф надежнее, надо сравнить эти числа. Преобразуем первое число к виду 10¹⁶, а второе – 16²⁵. Теперь становится очевидно, что первое число меньше, чем второе. Таким образом, получаем, что второй сейф надежнее.

Некоторые из участников конкурса отметили, что отпирающую комбинацию первого сейфа (для ее записи потребуется 16 цифр) запомнить проще, чем для второго. Это абсолютно справедливо. Однако, в задаче спрашивалось, какой сейф надежнее, а не какой удобнее (если уж рассуждать в терминах “удобства”, то лучше хранить кораллы в незапирающемся ящике стола, а не в сейфе – тогда вообще не надо запоминать кодовую комбинацию).

Ответ:Второй сейф надежнее.

Функции

Функции с областью определения и областью значений заданы таблицами (табл.1)

табл. 1

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

Решение

(б) Пусть . Выберем среди такую функцию , что . Пусть . Ясно, что . Выберем среди функцию такую, что . Тогда функция удовлетворяет условию . Пусть . Ясно, что . Выберем среди функцию такую, что . Тогда функция удоволетворяет равенствам . Значит, и для всех

(а) Используя рассуждения п.(б) можно прийти к одному из вариантов ответа: a = 2, b = 5, c = 6.

Ответ:a = 2, b = 5, c = 6.

Латинский квадрат