На детсадовских утренниках читают стихи с табуреточки глаша, даша, маша, паша, саша и георгий константинович. каждый из них за один утренник может либо рассказать стишок сам (при этом от волнения он никого не слышит), либо послушать стихи остальных. какое минимальное число утренников потребуется провести, чтобы каждый услышал стишок каждого?

Понадобится 6 утренников

((3 + 1) * 3) * 3 = 36
((3) * 3 + 1 + 1 + 1) * 3 = 36
((3) * 3 + 1 + 1) * 3 + 1 + 1 + 1 = 36
((3) * 3 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 = 36
(3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1) * 3 = 36
((3) * 3) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 36
(3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1) * 3 + 1 + 1 + 1 = 36
(3 + 1 + 1 + 1 + 1 + 1 + 1 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 = 36
(3 + 1 + 1 + 1 + 1 + 1 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 36
(3 + 1 + 1 + 1 + 1 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 36
(3 + 1 + 1 + 1 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 36
(3 + 1 + 1 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 36
(3 + 1 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 36
(3 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 36
(3) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 36
3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 36
ответ 16

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

def f1(number, log) #
  v = 3
  n = number * v
  log = "(#{log}) * #{v}"
  # log += "[" + n.to_s + "] "
  return [n, log]
end

def countWays(start_num, end_num, op_numbers, 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
      # puts "steps = #{steps}"
      new_ways = {}
      ways.each_pair{|log, num|

          for k in 0..op_numbers-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
                  # and log.include?('[8]')
              then
                  log1 += " = " + end_num.to_s
                  count += 1
                  puts log1
              elsif num1.between?(start_num, end_num)
                  new_ways.store(log1, num1)
              else
                  # log1 = log1 + " = " + num1.to_s + " BAD "
                  # puts log1
              end
          end
      }
      # p [steps, ways.size, new_ways.size]
      ways = new_ways
  end
  return count
end

((3 + 1) * 3) * 3 = 36
((3) * 3 + 1 + 1 + 1) * 3 = 36
((3) * 3 + 1 + 1) * 3 + 1 + 1 + 1 = 36
((3) * 3 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 = 36
(3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1) * 3 = 36
((3) * 3) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 36
(3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1) * 3 + 1 + 1 + 1 = 36
(3 + 1 + 1 + 1 + 1 + 1 + 1 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 = 36
(3 + 1 + 1 + 1 + 1 + 1 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 36
(3 + 1 + 1 + 1 + 1 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 36
(3 + 1 + 1 + 1 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 36
(3 + 1 + 1 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 36
(3 + 1 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 36
(3 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 36
(3) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 36
3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 36
ответ 16

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

def f1(number, log) #
  v = 3
  n = number * v
  log = "(#{log}) * #{v}"
  # log += "[" + n.to_s + "] "
  return [n, log]
end

def countWays(start_num, end_num, op_numbers, 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
      # puts "steps = #{steps}"
      new_ways = {}
      ways.each_pair{|log, num|

          for k in 0..op_numbers-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
                  # and log.include?('[8]')
              then
                  log1 += " = " + end_num.to_s
                  count += 1
                  puts log1
              elsif num1.between?(start_num, end_num)
                  new_ways.store(log1, num1)
              else
                  # log1 = log1 + " = " + num1.to_s + " BAD "
                  # puts log1
              end
          end
      }
      # p [steps, ways.size, new_ways.size]
      ways = new_ways
  end
  return count
end