Panda Noir

JavaScript の限界を究めるブログでした。最近はいろんな分野を幅広めに書いてます。

数学的帰納法・応用編

刀語最終話の七花八裂・応用編という響きが好きなので。響きの好き嫌いってなにで決定してるんでしょうかね?

この記事は数学的帰納法を用いてより幅広く日常的に応用しようというものです。

厳密な数学的帰納法

さて、今回紹介するのは「日常的に活かす」ものなので厳密な数学的帰納法ではないです。ゆるーい感じの数学的帰納法です。ちなみに着想は競技プログラミングからです。

概要

まず数学的帰納法を忘れた・知らない人のためにざっくりいうと、まず、小さいパターンで当てはまることを確かめます。数学の授業ではn=1とおいてやりますよね。次に、n=kのとき成り立つと仮定し、n=k+1でも成り立つことを証明します。すると、n=1のとき、n=1+1つまりn=2のときも成り立ちます。ということはn=3でも、n=4でも以下すべての正の整数で成り立ちます。

このような方法でしたよね。では、これを応用していきます。

方法

では、応用編です。ちょっと上に書いたものとは手順が違います。

では、試しに次のような問題をときます。2048というゲームにおいて作れる最大の数字はいくつか(2048がわからない人は検索してみてください。面白いゲームです。ちなみに私は2048までは作れました)。

2048をやってみると、無限に大きい数字が作れそうです。しかし、限界が存在します。では、帰納法もどきで求めていきましょう。

まず、小さいパターンを考えます。この場合、4x4の盤ではなく、1x1の盤を想定します。

1x1の盤では、はじめに数字が出て、それで終わりです。動かせませんから。そのため、最大の数字は4です(出現する数字は2または4のため)。

次がポイントなのですが、これを法則などを見出さぬように拡張します。変なことをしなければ多分大丈夫です。2048でいう拡張は、盤の拡張です。盤を2x2に拡張します。

この場合、適当にゲームオーバーせずやっていくと32ができると思います。この32を64にするには、残る3マスで32を作らなければなりません。これはできるのでしょうか?いいえ、できません。なぜなら、3マスでやりくりしていくと16ができあがり、残る2マスで16は作れず、残る2マスでは8ができますが、残る1マスで8はつくれません。

こう考えると、32が最高とわかります。

さて、3x3はどうでしょうか?正直言うと考えるのがめんどうになったので私はやりません。しかし、この拡張で、作れる最大の数字は無限になるでしょうか?答えは否です。2x2の場合を見ていてもそれは明確です。

ということは4x4に拡張しても当てはまります。

厳密な求め方ではありませんが、日常生活ではこの程度の軽い感じで問題無いと思います。

終わりに

ちょっと問題が悪かったと思いました。でも、これを使えると数学の問題でも、すぐに自分の考えを確かめられるので、安心して問題を解き進めることができるようになれるので、おすすめです。

(説明力がほしいです)