Решение задачи №232 (Вариант ЕГЭ 13): Найти минимальное R > 114

Задача № 232 (Вариант ЕГЭ 13) Условие: На вход алгоритма подаётся натуральное число \(N\). Алгоритм строит по нему новое число \(R\) следующим образом: 1. Строится двоичная запись числа \(N\). 2. К этой записи дописывается (дублируется) последняя цифра. 3. Справа дописывается бит чётности: 0, если в двоичном коде полученного числа чётное число единиц, и 1, если нечётное. 4. К полученному результату дописывается ещё один бит чётности. Нужно найти минимальное число \(R > 114\), которое может быть получено в результате работы автомата. Решение: Поскольку нам нужно найти минимальное \(R > 114\), начнем проверять числа, следующие за 114, и анализировать их двоичную запись на соответствие алгоритму. 1. Проверим число \(R = 115\): Двоичная запись: \(115_{10} = 1110011_{2}\). В этой записи 7 бит. По условию, \(R\) получается из \(N\) добавлением 3-х бит. Значит, исходное \(N\) должно иметь \(7 - 3 = 4\) бита. Пусть \(N = 1110_{2}\) (это 14). Шаг 2: Дублируем последнюю цифру (0): \(11100\). Шаг 3: Считаем количество единиц в \(11100\). Их 3 (нечётное), значит дописываем 1: \(111001\). Шаг 4: Считаем количество единиц в \(111001\). Их 4 (чётное), значит дописываем 0: \(1110010\). Полученное число \(1110010_{2} = 114\). Это не 115. Число 115 не подходит. 2. Проверим число \(R = 116\): Двоичная запись: \(116_{10} = 1110100_{2}\). Проверим алгоритм для \(N = 1110_{2}\): Шаг 2: \(11100\). Шаг 3: Единиц 3 (нечёт), дописываем 1: \(111001\). Шаг 4: Единиц 4 (чёт), дописываем 0: \(1110010\). Результат 114. Не подходит. 3. Проверим число \(R = 117\): Двоичная запись: \(117_{10} = 1110101_{2}\). Не подходит по структуре бит чётности (см. выше). 4. Проверим следующее возможное \(N\). Пусть \(N = 1111_{2}\) (это 15). Шаг 1: \(1111\). Шаг 2: Дублируем последнюю цифру (1): \(11111\). Шаг 3: Считаем единицы в \(11111\). Их 5 (нечётное), дописываем 1: \(111111\). Шаг 4: Считаем единицы в \(111111\). Их 6 (чётное), дописываем 0: \(1111110\). Переведем результат в десятичную систему: \[1111110_{2} = 1 \cdot 2^6 + 1 \cdot 2^5 + 1 \cdot 2^4 + 1 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2^1 + 0 \cdot 2^0\] \[R = 64 + 32 + 16 + 8 + 4 + 2 = 126\] Это число больше 114, но, возможно, есть число меньше. 5. Проверим \(N = 1110_{2}\) мы уже проверяли, оно дает \(R = 114\). Попробуем \(N = 10000_{2}\) (это 16). Шаг 1: \(10000\). Шаг 2: Дублируем последнюю цифру (0): \(100000\). Шаг 3: Единиц 1 (нечёт), дописываем 1: \(1000001\). Шаг 4: Единиц 2 (чёт), дописываем 0: \(10000010\). Переведем в десятичную систему: \[10000010_{2} = 2^7 + 2^1 = 128 + 2 = 130\] Это больше 126. 6. Вернемся к анализу чисел между 114 и 126. Чтобы \(R\) было в диапазоне (114, 126), его двоичная запись должна начинаться с \(1110...\) или \(1111...\). Мы проверили все варианты для \(N = 14\) (\(1110_2\)) и \(N = 15\) (\(1111_2\)). Для \(N = 14\) результат \(R = 114\). Для \(N = 15\) результат \(R = 126\). Любое \(N < 14\) даст \(R < 114\). Любое \(N > 15\) даст \(R \ge 130\). Следовательно, минимальное число \(R > 114\), которое может быть получено — это 126. Ответ: 126.