понедельник, 5 августа 2013 г.

Необычный калькулятор

На калькуляторе есть всего две клавиши с нестандартными операциями: 2а+1 и (а-1)/3. При этом вторая операция доступна, если а-1 делится на 3. Как с помощью этого калькулятора из 1 получить 8, выполнив наименьшее число операций?
Необычный калькулятор
update
Наименьшее количество операций предложил Andrew Antonets.
Ответ
Из 1 можно получить 8 за 15 операций:
1-3-7-15-31-63-127-42-85-171-343-114-229-76-25-8.

Какая пара не является решением?

4 комментария:

  1. Доказать, что этот путь - кратчайший, видимо, невозможно (только перебором вручную всего дерева), но вариант в 20 операций такой:
    1-3-7-15-31-63-127-42-85-28-9-19-6-13-27-55-18-37-12-25-8
    Операции очевидны, поэтому не стал указывать.

    Но построение дерева с 20 уровнями узлов - дело трудоемкое. Теоретически на нижнем уровне будет миллион узлов, но вторая операция не всегда возможна, да и будут образовываться "кольца"... Так, на 9-м уровне будет 7 узлов. Но к 20-му до тысячи наберется, так что доказательство оставлю или более усидчивым головоломщикам, или избыточно любознательным программистам.

    ОтветитьУдалить
    Ответы
    1. я сходу нашел в 15 операций (комментарий ниже), но с доказательством пока туго.
      Пытался рассуждать от обратного, в духе "8 четное, четные числа можно получить только второй операцией..." до пока дело не пошло

      Удалить
  2. 1-3-7-15-31-63-127-42-85-171-343--114-229-76-25-8
    вопросы с доказательством пока не решены :)

    ОтветитьУдалить
    Ответы
    1. Доказательства у меня тоже нет. Есть только ответ и 15 - минимальное количество операций.

      Удалить