Разделы 
Дополнительно
Задача по математике - 3731
2019-06-16 
Докажите, что из цифр 1 и 2 можно составить $2^{n+1}$ чисел, каждое из которых $2^n$ - значно и каждые два из которых различаются не менее чем в $2^{n-1}$ разрядах.
Решение:
При $n = 1$ четыре числа $11, 21, 12, 22$ удовлетворяют условию. Докажем утверждение задачи по индукции.
Обозначим через $a^{ \prime}$ число, полученное из а заменой цифр 1 на 2 и 2 на 1, а через $ab$ - число, полученное приписыванием
к $a$ числа $b$. Пусть построено множество $A_n$ из $2^{n+1}$ чисел, каждое из которых $2n$-значно, причем каждые 2 из чисел отличаются не менее чем в $2^{n-1}$ разрядах. Рассмотрим множество $A_{n+1}$, состоящее из чисел $aa$ и $aa^{ \prime}$, где $a \in A_n$. Все такие числа $2^{n+1}$-значны, всего их $2^{n+2}$. Кроме того, любые два из них отличаются не менее чем в $2^n$ разрядах. В самом деле, числа $aa$ и $aa^{ \prime}$, а также числа $aa$ и $bb^{ \prime}$ при любых $a$ и $b$ отличаются ровно в $2n$ разрядах (в тех разрядах, где $a$ и $b$ отличаются, $a^{ \prime}$ и $b^{ \prime}$ совпадают, и наоборот); числа $aa$ и $bb$ по предположению индукции отличаются не менее чем в $2^n$ разрядах. Утверждение доказано.
Докажите, что из цифр 1 и 2 можно составить $2^{n+1}$ чисел, каждое из которых $2^n$ - значно и каждые два из которых различаются не менее чем в $2^{n-1}$ разрядах.
Решение:
При $n = 1$ четыре числа $11, 21, 12, 22$ удовлетворяют условию. Докажем утверждение задачи по индукции.
Обозначим через $a^{ \prime}$ число, полученное из а заменой цифр 1 на 2 и 2 на 1, а через $ab$ - число, полученное приписыванием
к $a$ числа $b$. Пусть построено множество $A_n$ из $2^{n+1}$ чисел, каждое из которых $2n$-значно, причем каждые 2 из чисел отличаются не менее чем в $2^{n-1}$ разрядах. Рассмотрим множество $A_{n+1}$, состоящее из чисел $aa$ и $aa^{ \prime}$, где $a \in A_n$. Все такие числа $2^{n+1}$-значны, всего их $2^{n+2}$. Кроме того, любые два из них отличаются не менее чем в $2^n$ разрядах. В самом деле, числа $aa$ и $aa^{ \prime}$, а также числа $aa$ и $bb^{ \prime}$ при любых $a$ и $b$ отличаются ровно в $2n$ разрядах (в тех разрядах, где $a$ и $b$ отличаются, $a^{ \prime}$ и $b^{ \prime}$ совпадают, и наоборот); числа $aa$ и $bb$ по предположению индукции отличаются не менее чем в $2^n$ разрядах. Утверждение доказано.
