Задача 5
У исполнителя Омега две команды, которым присвоены номера:
- умножь на 2
- допиши единицу
Первая из них увеличивает число на экране в 2 раза, вторая заменяет число на экране числом, у которого дописана единица между его разрядами десятков и единиц.
Составьте алгоритм получения из числа 3 числа 614, содержащий не более 5 команд. В ответе запишите только номера команд.
Решение:
Нам нужно получить число 614 из числа 3, используя не более 5 команд.
Рассмотрим команды:
- Команда 1: умножить число на 2.
- Команда 2: дописать единицу между разрядами десятков и единиц. Это означает, что если число \(N\) имеет вид \(XY\), то оно превращается в \(X1Y\). Если число \(N\) однозначное, например \(X\), то оно превращается в \(X1\). Если число \(N\) трехзначное \(XYZ\), то оно превращается в \(XY1Z\).
Давайте попробуем двигаться от числа 3 к 614, используя эти команды.
Начнем с числа 3.
Шаг 1: Применим команду 1 (умножить на 2).
\(3 \times 2 = 6\)
Текущее число: 6. Использована 1 команда.
Шаг 2: Применим команду 1 (умножить на 2).
\(6 \times 2 = 12\)
Текущее число: 12. Использовано 2 команды.
Шаг 3: Применим команду 2 (дописать единицу).
Число 12. Разряд десятков - 1, разряд единиц - 2. Дописываем 1 между ними.
\(12 \rightarrow 112\)
Текущее число: 112. Использовано 3 команды.
Шаг 4: Применим команду 1 (умножить на 2).
\(112 \times 2 = 224\)
Текущее число: 224. Использовано 4 команды.
Шаг 5: Применим команду 1 (умножить на 2).
\(224 \times 2 = 448\)
Текущее число: 448. Использовано 5 команд.
Мы получили 448, а нужно 614. Этот путь не подходит.
Попробуем другой путь.
Начнем с числа 3.
Шаг 1: Применим команду 1 (умножить на 2).
\(3 \times 2 = 6\)
Текущее число: 6. Использована 1 команда.
Шаг 2: Применим команду 1 (умножить на 2).
\(6 \times 2 = 12\)
Текущее число: 12. Использовано 2 команды.
Шаг 3: Применим команду 1 (умножить на 2).
\(12 \times 2 = 24\)
Текущее число: 24. Использовано 3 команды.
Шаг 4: Применим команду 2 (дописать единицу).
Число 24. Разряд десятков - 2, разряд единиц - 4. Дописываем 1 между ними.
\(24 \rightarrow 214\)
Текущее число: 214. Использовано 4 команды.
Шаг 5: Применим команду 1 (умножить на 2).
\(214 \times 2 = 428\)
Текущее число: 428. Использовано 5 команд.
Мы получили 428, а нужно 614. Этот путь тоже не подходит.
Попробуем еще один путь, возможно, нужно использовать команду 2 раньше.
Начнем с числа 3.
Шаг 1: Применим команду 1 (умножить на 2).
\(3 \times 2 = 6\)
Текущее число: 6. Использована 1 команда.
Шаг 2: Применим команду 2 (дописать единицу).
Число 6. Это однозначное число. Дописываем 1 после него, чтобы получить 61.
\(6 \rightarrow 61\)
Текущее число: 61. Использовано 2 команды.
Шаг 3: Применим команду 1 (умножить на 2).
\(61 \times 2 = 122\)
Текущее число: 122. Использовано 3 команды.
Шаг 4: Применим команду 1 (умножить на 2).
\(122 \times 2 = 244\)
Текущее число: 244. Использовано 4 команды.
Шаг 5: Применим команду 1 (умножить на 2).
\(244 \times 2 = 488\)
Текущее число: 488. Использовано 5 команд.
Мы получили 488, а нужно 614. Этот путь тоже не подходит.
Давайте попробуем рассуждать "с конца". Если мы получили 614, то что было до этого?
Если последняя команда была 1 (умножить на 2), то предыдущее число было \(614 \div 2 = 307\).
Если последняя команда была 2 (дописать единицу), то число 614 получилось из числа 64 (единица была дописана между 6 и 4).
Рассмотрим вариант, что 614 получилось из 64 командой 2.
Цель: получить 64 из 3 за 4 команды.
Начнем с 3.
Шаг 1: Применим команду 1 (умножить на 2).
\(3 \times 2 = 6\)
Текущее число: 6. Использована 1 команда.
Шаг 2: Применим команду 1 (умножить на 2).
\(6 \times 2 = 12\)
Текущее число: 12. Использовано 2 команды.
Шаг 3: Применим команду 1 (умножить на 2).
\(12 \times 2 = 24\)
Текущее число: 24. Использовано 3 команды.
Шаг 4: Применим команду 1 (умножить на 2).
\(24 \times 2 = 48\)
Текущее число: 48. Использовано 4 команды.
Мы получили 48, а нужно 64. Этот путь не подходит.
Попробуем другой путь к 64.
Начнем с 3.
Шаг 1: Применим команду 1 (умножить на 2).
\(3 \times 2 = 6\)
Текущее число: 6. Использована 1 команда.
Шаг 2: Применим команду 1 (умножить на 2).
\(6 \times 2 = 12\)
Текущее число: 12. Использовано 2 команды.
Шаг 3: Применим команду 2 (дописать единицу).
\(12 \rightarrow 112\)
Это уже больше 64, так что этот путь не подходит.
Давайте вернемся к 307. Если 614 получилось из 307 командой 1.
Цель: получить 307 из 3 за 4 команды.
Число 307 нечетное, значит, последняя команда для получения 307 не могла быть "умножить на 2". Значит, 307 получилось командой 2 (дописать единицу).
Если 307 получилось командой 2, то оно было получено из числа 37 (единица была дописана между 3 и 7).
Цель: получить 37 из 3 за 3 команды.
Начнем с 3.
Шаг 1: Применим команду 1 (умножить на 2).
\(3 \times 2 = 6\)
Текущее число: 6. Использована 1 команда.
Шаг 2: Применим команду 1 (умножить на 2).
\(6 \times 2 = 12\)
Текущее число: 12. Использовано 2 команды.
Шаг 3: Применим команду 1 (умножить на 2).
\(12 \times 2 = 24\)
Текущее число: 24. Использовано 3 команды.
Мы получили 24, а нужно 37. Этот путь не подходит.
Попробуем другой путь к 37.
Начнем с 3.
Шаг 1: Применим команду 1 (умножить на 2).
\(3 \times 2 = 6\)
Текущее число: 6. Использована 1 команда.
Шаг 2: Применим команду 2 (дописать единицу).
\(6 \rightarrow 61\)
Текущее число: 61. Использовано 2 команды.
Это уже больше 37, так что этот путь не подходит.
Давайте попробуем еще раз с начала, более систематично.
Начальное число: 3
Попытка 1:
1. \(3 \xrightarrow{1} 6\)
2. \(6 \xrightarrow{1} 12\)
3. \(12 \xrightarrow{1} 24\)
4. \(24 \xrightarrow{1} 48\)
5. \(48 \xrightarrow{1} 96\)
Не 614.
Попытка 2:
1. \(3 \xrightarrow{1} 6\)
2. \(6 \xrightarrow{1} 12\)
3. \(12 \xrightarrow{1} 24\)
4. \(24 \xrightarrow{2} 214\)
5. \(214 \xrightarrow{1} 428\)
Не 614.
Попытка 3:
1. \(3 \xrightarrow{1} 6\)
2. \(6 \xrightarrow{1} 12\)
3. \(12 \xrightarrow{2} 112\)
4. \(112 \xrightarrow{1} 224\)
5. \(224 \xrightarrow{1} 448\)
Не 614.
Попытка 4:
1. \(3 \xrightarrow{1} 6\)
2. \(6 \xrightarrow{2} 61\)
3. \(61 \xrightarrow{1} 122\)
4. \(122 \xrightarrow{1} 244\)
5. \(244 \xrightarrow{1} 488\)
Не 614.
Давайте попробуем с конца, но более тщательно.
Целевое число: 614.
Вариант 1: Последняя команда была 1 (умножить на 2). Тогда предыдущее число было \(614 \div 2 = 307\). Нам нужно получить 307 из 3 за 4 команды.
Вариант 2: Последняя команда была 2 (дописать единицу). Число 614. Единица была дописана между 6 и 4. Значит, предыдущее число было 64. Нам нужно получить 64 из 3 за 4 команды.
Рассмотрим Вариант 2: Получить 64 из 3 за 4 команды.
Начнем с 3.
1. \(3 \xrightarrow{1} 6\)
2. \(6 \xrightarrow{1} 12\)
3. \(12 \xrightarrow{1} 24\)
4. \(24 \xrightarrow{1} 48\)
Не 64.
Попробуем использовать команду 2 для получения 64.
Если 64 получилось командой 2, то оно было получено из 6 (единица была дописана после 6, но это не между разрядами десятков и единиц, а просто дописывание. В условии сказано "между его разрядами десятков и единиц". Для однозначного числа, например 6, это означает, что оно превращается в 61. Если бы было 64, то это означало бы, что 64 получилось из 64, что бессмысленно. Значит, 64 не могло быть получено командой 2, если оно не имеет вида \(X1Y\)).
Значит, 64 должно быть получено умножением на 2.
Если 64 получено командой 1, то предыдущее число было \(64 \div 2 = 32\).
Нам нужно получить 32 из 3 за 3 команды.
Начнем с 3.
1. \(3 \xrightarrow{1} 6\)
2. \(6 \xrightarrow{1} 12\)
3. \(12 \xrightarrow{1} 24\)
Не 32.
Попробуем другой путь к 32.
Если 32 получено командой 2, то оно было получено из 32 (не подходит).
Значит, 32 должно быть получено умножением на 2.
Если 32 получено командой 1, то предыдущее число было \(