Question

Мистер Фокс разрабатывает программу для робота-лунохода. Сегодня его роботу нужно добраться по прямой дороге длиной 22 фута от космодрома до базы, попутно забрав ценный предмет. Будем считать дорогу отрезком, в левом конце которого находится космодром, в правом конце – база, а ровно посередине – лежит ценный предмет. Мистер Фокс может давать роботу три команды: A – сместиться на 1 фут вправо, B – сместиться на 2 фута вправо, C – сместиться на 3 фута вправо. Набор из 22 фута команд A является удачным, так как приводит робота на базу (попутно он заберет ценный предмет, потому что остановится около него), а вот набор BBCCCCCC удачным не является: робота на базу он приведет, но вот ценный предмет робот не заберет, поскольку не остановится около него. Сколько существует удачных наборов команд?

Answer 1

Я приведу программное решение, так как это все-таки информатика. Аналитическое решение ищите по ссылке в комментариях

Код на Ruby 2

def f0(number, log) #
  v = 1
  n = number + v
  log = "#{log}A"
  return [n, log]
end

def f1(number, log) #
  v = 2
  n = number + v
  log = "#{log}B"
  return [n, log]
end

def f2(number, log) #
  v = 3
  n = number + v
  log = "#{log}C"
  return [n, log]
end

def countWays(start_num, end_num, op_number, max_steps = 0)
  ways = {}
  ways.store(start_num.to_s, start_num)

  max_steps = max_steps == 0 ? (start_num - end_num).abs : max_steps
  count = 0

  for steps in 1..max_steps
      new_ways = {}
      ways.each_pair{|log, num|

          for k in 0..op_number-1
              num1, log1 = f0(num, log) if k == 0
              num1, log1 = f1(num, log) if k == 1
              num1, log1 = f2(num, log) if k == 2

              if num1 == end_num then
                  log1 += " = " + end_num.to_s
                  count += 1
                  # puts log1
              elsif num1.between?(start_num, end_num)
                  new_ways.store(log1, num1)
              end
          end
      }
      ways = new_ways
  end
  return count
end

p countWays(0, 11, 3) # с 0 до 11, 3 разных команды

Вывод 504

Поскольку длина путей до ценного объекта и от объекта до базы - равны, то всего вариантов 504*504 = 254016

Answer 2

Все удачные наборы команд должны включать остановку на отметке 11 футов.
На отметку 1 фут робот может попасть с помощью одной команды A;
на отметку 2 фута - с помощью команд AA и B (всего 2 набора команд);
на отметку 3 фута - с помощью команд AAA, AB, BA и C (4 набора).
Так как за одну команду робот может переместиться на 1, 2 или 3 фута, то для подсчета количества наборов команд, позволяющих роботу попасть на отметки N > 3, можно использовать формулу
K(N) = K(N-1)+K(N-2)+K(N-3).
K(4) = K(3)+K(2)+K(1) = 4+2+1 = 7
K(5) = K(4)+K(3)+K(2) = 7+4+2 = 13
K(6) = K(5)+K(4)+K(3) = 13+7+4 = 24
K(7) = K(6)+K(5)+K(4) = 24+13+7 = 44
K(8) = K(7)+K(6)+K(5) = 44+24+13 = 81
K(9) = K(8)+K(7)+K(6) = 81+44+24 = 149
K(10) = K(9)+K(8)+K(7) = 149+81+44 = 274
K(11) = K(10)+K(9)+K(8) = 274+149+81 = 504
Так как вторая часть пути робота также имеет длину 11, то общее количество удачных наборов команд = 504*504 = 254016