151220(3)

Ruby

郵便切手の問題(1)

「数学１００の問題」 数学セミナー編集部[編]に載っていた
郵便切手の問題について考えてみた。
n = 12のとき 12196と載っているが、12198の間違いである。

また、オンライン整数列大辞典の
A000682のCOMMENTSにあるように

number of ways a semi-infinite directed curve can cross a straight line n times は

number of ways to fold a strip of n+1 labeled stamps with leaf 1 on top に等しいので、

番号はずれるが、求めた数値の正しさは

https://oeis.org/A000682/list

で確かめればよい。

なお、コード中のtest_intersect(ary) は

http://ja.stackoverflow.com/questions/20208/%E5%90%8C%E3%81%98%E6%95%B0%E5%90%8C%E5%A3%AB%E7%B7%9A%E3%81%A7%E7%B5%90%E3%82%93%E3%81%A0%E3%81%A8%E3%81%8D-%E4%BA%A4%E7%82%B9%E3%81%8C%E3%81%A7%E3%81%8D%E3%82%8B%E3%81%8B%E5%90%A6%E3%81%8B%E3%81%AE%E5%88%A4%E5%AE%9A%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6

のunarist さんの回答が元です。

# 切手が貫通していないか
def test_intersect(ary)
  ary.inject([]){|stack, i| stack.last == i ? stack[0..-2] : stack << i} == []
end

def up_check(ary)
  ary1 = ary.map{|i| (i + 1) / 2}
  ary1.delete((ary.size + 1) / 2) if ary.size % 2 == 1
  test_intersect(ary1)
end

def down_check(ary)
  ary2 = ary[1..-1].map{|i| i / 2}
  ary2.delete(ary.size / 2) if ary.size % 2 == 0
  test_intersect(ary2)
end

def f(n)
  cnt = 0
  (2..n).to_a.permutation(n - 1){|c|
    # 左が一番上
    c = [1] + c
    if up_check(c)
      cnt += 1 if down_check(c)
    end
  }
  cnt
end

(1..12).each{|i| p f(i)}

出力結果
1
1
2
4
10
24
66
174
504
1406
4210
12198