За один шаг автомат умеет выполнять одну из четырех операций: либо умножать данное число на 2 , либо умножать данное число на 3, либо возвести его в квадрат, либо в куб. Что может получиться после 5-ти шагов, если начать с числа 33? 2 8 • 3 4 • 11 2 2 6 • 3 6 • 11 4 2 3 • 3 8 • 11 6 2^8 • 3^4 • 11^2 2^6 • 3^6 • 11^4 2^3 • 3^8 • 11^6 2 • 3^4 • 11^2 2^5 • 3^13 • 11^12 2^8 • 3^5 • 11^6 2 • 3^2 • 11^6 2^3 • 3^11 • 11^9 задан 21 Фев '14 14:21 Natlash |
Я так понимаю, здесь первые три строки лишние, потому что они дублируют то, что идёт дальше. Всего здесь, таким образом, имеется 8 чисел. Требуется понять, какие из них могли быть получены за 5 шагов, а какие нет. В целях упрощения, можно переформулировать задачу так. Все числа, которые могут здесь в принципе получиться, имеют вид $%2^k3^l11^m$% для некоторых целых неотрицательных $%k$%, $%l$%, $%m$%. Поэтому вместо самих чисел можно работать с тройками вида $%(k,l,m)$%. Изначально имелась тройка $%(0;1;1)$%. Операций над тройками получается четыре: можно прибавить 1 к первой координате, или прибавить 1 ко второй координате, или умножить все координаты на 2, или умножить их на 3. У меня получилось, что за 5 шагов достижимы следующие 4 тройки из восьми: $%(6,6,4)$%, $%(3,8,6)$%, $%(1,4,2)$%, $%(3,11,9)$%. Остальные 4 тройки получены быть не могут. Для тех троек, которые могут быть получены, явно указывается цепочка преобразований. Например, для первой из них получается $$(0,1,1)\to(1,1,1)\to(2,2,2)\to(3,2,2)\to(3,3,2)\to(6,6,4).$$ Рассмотрим пример тройки, которая не может быть получена. Возьмём тройку $%(8,4,2)$%. Умножений на 3 быть не могло, а умножение на 2 могло быть только одно. В этом случае прибавление 1 к первой или второй координате осуществлялось 4 раза. Сумма первых двух координат могла при этом составить максимум 10 -- если все единицы прибавить сначала, и в конце всё удвоить (если удваивать не в конце, то сумма будет ещё меньше). Но у нас сумма первых двух координат равна 12: такой большой она стать не могла. Подробный разбор каждого из вариантов я проводить не буду, так как это долго, а использованные при анализе вариантов подходы здесь более или менее однотипны. отвечен 21 Фев '14 16:37 falcao |