Question

У исполнителя Множик две команды, которым присвоены номера: 1. Умножь на 2, 2. Раздели на 7. Первая из них увеличивает число на экране в 2 раза, вторая – уменьшает его в 7 раз. Программа для Множика – это последовательность команд. Сколько различных чисел можно получить из числа 75 при помощи программы, содержащей ровно 5 команд? Ответ обосновать.

Answer 1

Программы из 5 команд и результаты их выполнения:
11111: 7^5 * 2^5 = 16807 * 32 = 537824
11112: 7^5 / 7 * 2^4 = 2401 * 2^4 = 38416
11122: 7^5 / 7^2 * 2^3 = 343 * 8 = 2744
11222: 7^5 / 7^3 * 2^2 =  49 * 4 = 196
12222: 7^5 / 7^4 * 2 = 7 * 2 = 14
22222:  7^5 / 7^5 = 1
(Сами числа вычислять не обязательно)
Все другие программы будут давать в результате одно из перечисленных выше значений. Например, результат программы 12121 = результату программы 11122:
7^5 * 2 / 7 * 2 / 7 * 2 = 7^5 / 7^2 * 2^3
Ответ: количество различных чисел = 6

Answer 2

В общем виде все наборы можно представить в виде
$7^5 \frac{2^i}{7^{5-i}} (i = 0..5)$
Значит у нас столько вариантов сколько различных i, т.е. 6

Answer 3

Для решения этой задачи необходимо рассмотреть все возможные комбинации команд умножения на 2 и деления на 7, которые могут быть использованы для числа 75.

Пусть у нас есть 5 команд, которые мы можем использовать. Тогда все возможные комбинации команд можно представить в виде дерева решений, где каждая вершина представляет собой выполнение одной из команд, а пути от корня до листьев представляют собой различные комбинации команд.

Для числа 75 возможные комбинации команд будут выглядеть примерно так:

- Умножить на 2, умножить на 2, умножить на 2, умножить на 2, умножить на 2 - Умножить на 2, умножить на 2, умножить на 2, умножить на 2, разделить на 7 - Умножить на 2, умножить на 2, умножить на 2, разделить на 7, умножить на 2 - Умножить на 2, умножить на 2, умножить на 2, разделить на 7, разделить на 7 - ...

После того, как мы рассмотрим все возможные комбинации команд, мы сможем вычислить все значения, которые можно получить из числа 75 при помощи программы, содержащей ровно 5 команд.

Таким образом, мы можем получить различные числа из числа 75 при помощи программы, содержащей ровно 5 команд.