Question

Назовём семизначные шифры похожими, если представляющие их семизначные числа отличаются не более чем в одном разряде. Какое наибольшее число шифров можно выписать так, чтобы никакие два не были бы похожи?

Answer 1

Ответ:

1 000 000 (один миллион)

Пошаговое объяснение:

Оценка:

Заметим, что каждый выписанный шифр запрещает 7*9=63 шифра (потому что существует ровно 9 чисел отличающихся от нашего в заданном разряде, а таких разрядов 7).

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

Теперь построим граф, в котором каждому шифру соответствует вершина, а между похожими шифрами проведено ребро. Тогда наш граф разобьется на две доли: выписанные шифры и запрещенные. Пусть выписано N1 шифров, запрещено N2. Тогда кол-во ребер в этом графе 63*N1<7*N2, т. е. 9N1≤N2, при этом N1+N2=10^7, получаем N1≤10^6.

Пример:

Докажем, что можно выписать 10^(n-1) n-циферных шифров.

База:

Решим задачу, для случая, когда кол-во разрядов равно 1. Тогда, очевидно, ответ - 1 (пример - любая цифра).

Переход:

У нас есть 10^(n-1) n-циферных шифров (попарно непохожих). Построим 10^n (n+1)-циферных шифров. Вначале припишем к каждому из начальных шифров слева цифру 0, получим 10^(n-1) (n+1)-циферных шифров. После этого припишем к каждому из начальных шифров цифру 1 и циклически переставим последнюю цифру (т.е. 0 превратится в 1, 2 в 3, 9 в 0), так мы получим еще 10^(n-1) шифров. Далее припишем к начальному набору слева 2, а последнюю цифру циклически переставим дважды (0 в 2, 1 в 3, 9 в 1). И так далее, приписываем цифру A слева, и делаем A циклических перестановок последней цифры.

Так мы получим 10 наборов по 10^(n-1) шифров, т.е. 10^n. Доказать, что все эти шифры не похожи друг на друга легко: внутри одного набора нет похожих, так как он сделан приписываением слева одной и той же цифры к двум уже не похожим числам и изменением последней цифра так, что разные цифры не могут стать одинаковыми. Два шифра из разных наборов, произошедшие от одного и того же шифра в начальном наборе отличаются в 2 цифрах - первой и последней. Два шифра из разных наборов произошедшие от разных шифров отличаются минимум в 2 цифрах - первой и какой-то еще не последней (она точно есть, т. к. в начальном наборе они были не похожи друг на друга).

Answer 2

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

Итак, для создания максимального количества непохожих семизначных шифров, мы можем взять следующий подход:

1. Выберем 9 чисел, каждое с различным значением в первом разряде (миллионные).
2. В каждой из этих 9 групп выберем 10 чисел с различным значением во втором разряде (стотысячные).
3. Для каждой из этих 90 групп выберем 10 чисел с различным значением в третьем разряде (десятитысячные).
4. Продолжаем этот процесс для каждого разряда, пока не заполним все разряды.

Таким образом, у нас будет максимальное количество непохожих семизначных шифров. Давайте вычислим:

Количество возможных различных чисел в каждом разряде:

• Первый разряд (миллионные): 9 возможных значения (1-9).
• Второй разряд (стотысячные): 9 возможных значения (0-8) + 1 дополнительное значение (9) для первого разряда.
• Третий разряд (десятитысячные): 9 возможных значения (0-8) + 1 дополнительное значение (9) для второго разряда.
• Четвёртый разряд (тысячи): аналогично.
• Пятый разряд (сотни): аналогично.
• Шестой разряд (десятки): аналогично.
• Седьмой разряд (единицы): аналогично.

Итак, общее количество непохожих семизначных чисел будет: $9 \times 9 \times 9 \times 9 \times 9 \times 9 \times 9 = 531441.$