За один шаг автомат умеет выполнять одну из четырех операций: либо умножать данное число на 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

10|600 символов нужно символов осталось
0

Я так понимаю, здесь первые три строки лишние, потому что они дублируют то, что идёт дальше. Всего здесь, таким образом, имеется 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

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×54

задан
21 Фев '14 14:21

показан
2792 раза

обновлен
21 Фев '14 16:37

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru