Славику задали очень сложные примеры по математике. И он надеется решить их с помощью калькулятора. Вот только беда, у Славика очень старый калькулятор, и он умеет исполнять только некоторые действия с натуральными числами. А имено отнять 3(если число больше 3), умножить на 3 и поделить на 3(если число делится на 3). У старых калькуляторов(таких как у Славика) используются старые аккумуляторы марки AKB-121, которые найти в наше время не представляется возможным. Следовательно Славик хочет как можно меньше разрядить аккумулятор(У него контрольная через неделю). Помогите Славику определить за какое минимально количество операций можно получить из числа a число b пользуясь калькулятором? Найдите ответ для a=51, b=52

задан 22 Окт '13 12:11

изменен 22 Окт '13 12:14

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

За 12 преобразований одно число из другого можно получить так: $$51, 48, 45, 15, 5, 2, 6, 18, 54, 162, 159, 156, 52.$$

Доказательство того, что меньшим число преобразований не обойтись, я, к сожалению, умею получать только при помощи перебора вариантов. Организовать его можно так. Из числа 51 за один шаг можно получить 17, 48 или 153. На следующем шаге появятся числа 14, 16, 45, 144, 150, 159. Если так продолжать 11 шагов, то число 52 ещё не появится, откуда следовало бы доказательство. Но это процесс очень долгий, и вручную его осуществить почти нереально. Однако можно поступить немного иначе: осуществить не 11 шагов, а всего 6. Тогда получается не слишком большое множество, и его вручную выписать можно. Общее количество чисел, которые в этом процессе участвуют (на всех шагах), равно 158. Это многовато, но приемлемо.

Далее надо осуществить обратный процесс на 5 шагов, начиная с числа 52 и осуществляя обратные преобразования. Теперь мы, как и раньше, умножаем и делим на 3 (когда возможно), но уже не вычитаем, а прибавляем 3. И первый шаг приводит тогда к числам 55, 156. Далее идут 58, 159, 165, 468, и так пять раз. Здесь общее количество чисел, вовлечённых в процесс, будет поменьше. Оно равно 69.

Сравнивая два списка -- я на всякий случай их здесь приведу --

первый: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 21, 24, 27, 30, 33, 36, 39, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 72, 90, 96, 99, 108, 114, 117, 120, 123, 126, 129, 132, 134, 135, 138, 140, 141, 142, 143, 144, 146, 147, 148, 149, 150, 151, 152, 153, 297, 351, 369, 375, 378, 387, 393, 396, 399, 402, 405, 411, 414, 417, 420, 423, 426, 429, 431, 432, 435, 438, 441, 444, 447, 449, 450, 453, 455, 456, 457, 458, 459, 1134, 1188, 1206, 1212, 1215, 1242, 1260, 1266, 1269, 1278, 1284, 1287, 1290, 1293, 1296, 1314, 1320, 1323, 1332, 1338, 1341, 1344, 1347, 1350, 1356, 1359, 1362, 1365, 1368, 1371, 1374, 1376, 1377, 3645, 3807, 3861, 3879, 3885, 3888, 3969, 4023, 4041, 4047, 4050, 4077, 4095, 4101, 4104, 4113, 4119, 4122, 4125, 4128, 4131, 11664, 12150, 12312, 12366, 12384, 12390, 12393, 37179;

второй: 18, 52, 53, 54, 55, 56, 57, 58, 59, 61, 64, 67, 156, 157, 158, 159, 160, 162, 165, 166, 168, 171, 174, 177, 180, 183, 186, 192, 468, 469, 471, 474, 477, 480, 483, 486, 489, 495, 498, 501, 504, 507, 513, 522, 525, 531, 549, 1404, 1407, 1410, 1413, 1416, 1422, 1431, 1434, 1440, 1458, 1485, 1488, 1494, 1512, 1566, 4212, 4215, 4221, 4239, 4293, 4455, 12636, можно убедиться в том, что они не имеют общих элементов. Значит, менее чем за 12 шагов нельзя получить одно число из другого.

Здесь наверняка есть какое-то решение, не основанное на переборе, но мне его пока не удалось придумать.

ссылка

отвечен 23 Окт '13 6:17

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

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

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

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

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

отмечен:

×591
×338

задан
22 Окт '13 12:11

показан
493 раза

обновлен
23 Окт '13 6:17

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

по почте:

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

по RSS:

Ответы

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

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