ハサミを使うタイミング:CodeIQ 答えの最小性について

*この文章はCodeIQの「ハサミを使うタイミング」に答えた人にしか伝わらないと思います。まだ挑戦されていない方はgihyo.co.jpのこのページを読んで挑戦してみてください。

ハサミを使うタイミング(CodeIQ)について、フィードバックを受けてから考えたことについて書きます。フィードバック前は、紙のサイズが最小になるように答えを求めることにはこだわりませんでしたが、今回はそこに集中して考えてみます。

まずメモ化を使って、w=1, 2, 3...のときにハサミを使う回数の最大値と、そのときのhの値を求めます。

結果は

ハサミ  (w, h)
1回 ... (2, 3)
2回 ... (3, 5)
3回 ... (5, 8)
4回 ... (8, 13) 

でした。ここで都合よく、n回ハサミを使うときの紙のサイズの最小値は(w = fib(n + 2), h = fib(n+3))になると予想します。ただし、fib(n)はフィボナッチ数の第n項を意味します。この予想は、数学的帰納法を使って証明できます。n=1のときは上で検証したことから成り立つことが分かります(wに対して、ハサミを使う回数の最大値を求めたのですから。。多分良いですよね。)。次にn=kで成り立つと仮定して、n=k+1で成り立つか考えます。1回ハサミを使ったあと、w=fib(k+4) % fib(k+3) = (fib(k+3) + fib(k+2)) % fib(k + 3) = fib(k+2), h = fib(k + 3)になります。これはn=kの場合にあたるので、全体でハサミを使う回数はk+1回になります。

次にw=fib(k+3)がk+1回切る場合の最小値になっているか考えます。fib(k+3)より小さく、k+1回切る可能性があるのはfib(k+2) < w < fib(k+3)に限られます。なぜならば、仮定からw=fib(k+2)以下のとき、最大でk回切ることが言えるからです。この範囲にwを取ったとき、ハサミを1回使った後fib(k+2) < h < fib(k+3)になりますが、h=fib(k+3)のときにはじめて、最大k回切ることになるので、この範囲にhを取ったとき、ハサミを使う回数は最大k回未満だと分かります。これはfib(k+2) < w < fib(k+3)のときは全体でk+1回未満しかハサミを使わないことを意味し、従ってw=fib(k+3)のときはじめてk+1回ハサミを使うhが存在することになります。

これでw=fib(k+4)のときk+1回ハサミを使い、そのときのhの最小値はfib(h+5)だと分かりました。これでハサミをn回使うことになる紙のサイズの最小値は(fib(n + 2), fib(n+3))だと言えます。