この記事では一切の高校数学の知識、プログラミングの知識を仮定しません。
ほんの少しでもパズルが好きな人であれば、恐らく最後まで読み通せるでしょう。
(苦手な方は、プログラムのコードや数式部分は飛ばして読んでも構いません)
皆さんこんにちは。東進衛星予備校 金沢南校の北川と申します。
気が付くとGWも終わり、どころか5月も終わりそうになっていますね。時間の流れが過ぎるのは早いものです。さらに悪いことに、私はブログのネタ帳を先月末に使い果たしてしまい、月末になっても真っ白なままです。困りました。
さて、ブログのネタに困ると入試数学問題の一覧を眺めるわけですが、そのうちに2020年京大理系の問題に目が留まりました。この年は文理問わず、京大が受験生をいじめ抜くために問題を作ったのではないかと思えるほど難問揃いのセットでした。
実際、とある予備校では「こんなに難しくしたら入試として意味あるん?(意訳)」というような講評がされていましたし、そう言ってしまうのも仕方がないレベルの出題だったのは事実です。
ですが、そういう問題ほど何か裏技で解いてしまいたくなるのもまた事実。
最近趣味でPython3を扱い始めたので、これを使って超難問をElephant[1]に解いていきたいと思います。勿論、それだけでは何にもならないので、人間の手で時間内に解くにはどうしたらいいのかも最後に解説します。
[1] 数学ではスマートな解法をElegant(素晴らしい)な解法と言うことがあるのですが、これに引っ掛けて力技で解く解法をElephant(象)な解法と言うことがあります。
目次
2. 人間の手で解く ~パソコンに教えるのとはまた違った工夫~
今回扱う問題は以下の通りです。
縦4個、横4個のマス目のそれぞれに1,2,3,4の数字を入れていく。このマス目の横の並びを行といい、縦の並びを列という。どの行にも、どの列にも同じ数字が1回しか現れない入れ方は何通りあるか求めよ。下図はこのような入れ方の1例である。
1 | 2 | 3 | 4 |
3 | 4 | 1 | 2 |
4 | 1 | 2 | 3 |
2 | 3 | 4 | 1 |
さて、問題の意味は割と分かりやすいかと思います。
4×4のマス目の縦横に同じ数字が入らないように、1~4の数字を入れる方法は何通りあるかという問題で、難しい数式が出てこない、本当にシンプルなパズルのような内容です。
では、この問題をプログラミングで解こうと思うとどうすればよいでしょうか?
この手の問題をプログラミングで解こうと思った時、まず思いつくのは「あり得る全パターンをパソコンに調べさせることは可能か?」ということです。
今回ならばまず、マス目に文字を入れるにあたって(問題文の条件を満たすかどうかはさておき)あり得るパターンの数を考えてみましょう。
もっとも単純に考えると、1つのマスに1~4の4通りの数字が入り、これが24マスありますから、合計で/(4^24=281,474,976,710,656/)
通りの可能性が考えられます。ざっくり280兆通りぐらいとみてみることにします。
さて、この280兆通りに対して、「これは条件を満たしている」「これは条件を満たしていない」と判別するのは、パソコンだとどれぐらいで出来るでしょうか? 家庭用のパソコンであれば、1秒間に10億回の計算ができるそうです。しかし、仮に1回の計算で1個のパターンが正しいかどうか判断できると仮定しても[2]、280000秒≒77時間以上かかる計算になります。3日かかっても計算が終わらない(そして本当は3日どころではないくらい計算しないと終わらない)のであれば、実用的とは言いにくいですね。
もっと楽をしましょう。
さっきの考え方だと、例えば1行目に「1,1,1,1」とか並んでいるパターンについても律義に考えていることになりますね。ですが、1行目がこうなっていたら明らかに条件を満たさないのは分かります。だって、同じ数字が出ていますからね。
1マスの単位で考えると、上記のような無駄がかなり多く生じます。そこで、もっと効率の良い方法として、「1行の単位で考える」という方針に切り替えてみます。
条件を満たしている入れ方の、それぞれの行に注目してみましょう。これらは当然「1,3,2,4」とか「3,2,1,4」のように、1~4までの数字が1個ずつバラバラに出てきているはずです。
これに注目すると、以下のように考えることができます。
・「1~4までの数字が1個ずつバラバラに出てくる行」全体の中から4つ選んで繋げて、それが条件を満たす入れ方になっているかどうかを判断すればよいのではないか?
具体的に見てみましょう。
例えば、「1~4までの数字が1個ずつバラバラに出てくる行」の中から、「1,2,3,4」「3,4,1,2」「4,1,2,3」「2,3,4,1」の4つを選んで縦に繋げると、以下のようになります。
1 | 2 | 3 | 4 |
3 | 4 | 1 | 2 |
4 | 1 | 2 | 3 |
2 | 3 | 4 | 1 |
これはまさしく、最初に問題文に書いてあった例そのものです。もちろんこれは条件を満たします。
次に、「1~4までの数字が1個ずつバラバラに出てくる行」の中から、「1,2,3,4」「3,4,1,2」「3,2,4,1」「2,3,4,1」を選んだ場合はどうでしょうか? この場合は以下のようになります。
1 | 2 | 3 | 4 |
3 | 4 | 1 | 2 |
3 | 2 | 4 | 1 |
2 | 3 | 4 | 1 |
これは赤字でハイライトした部分を見ればわかる通り、条件を満たしていません。
……と、こういった具合に「「1~4までの数字が1個ずつバラバラに出てくる行」全体から4つの行を選んで繋ぎ合わせたもの」が条件を満たすかどうかを調べていくのはどうか、という発想です。
「1~4までの数字が1個ずつバラバラに出てくる行」全体は、区別がつくものを4個並べる方法ですから合計で24個あります。全部書き出して調べても良いですね。以下の通りです。
[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,2,3],[1,4,3,2],
[2,1,3,4],[2,1,4,3],[2,3,1,4],[2,3,4,1],[2,4,1,3],[2,4,3,1],
[3,1,2,4],[3,1,4,2],[3,2,1,4],[3,2,4,1],[3,4,1,2],[3,4,2,1],
[4,1,2,3],[4,1,3,2],[4,2,1,3],[4,2,3,1],[4,3,1,2],[4,3,2,1]
そして、この24個の中から4個を選んで繋ぎ合わせて、4×4のマス目全体に数字の入れ方を作る方法は/(24^4=331,776/)通りです。この入れ方が条件を満たすかどうかは、各4つの列に同じ数字が出てきていないかを判断すればよいので、331,776通りに対して4回ずつで、合計1,327,104回の計算が必要だと見積もれます[3]。
計算回数たったの130万回! これなら、1秒に10億回計算できる機械にお願いすれば、それこそ1秒とかからず結果を返してくれそうです。
ということで、私がPython3で実装したコードがこちら。
import time
start = time.time()
#あり得る行を人力で全列挙
check_list = [[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,2,3],[1,4,3,2],
[2,1,3,4],[2,1,4,3],[2,3,1,4],[2,3,4,1],[2,4,1,3],[2,4,3,1],
[3,1,2,4],[3,1,4,2],[3,2,1,4],[3,2,4,1],[3,4,1,2],[3,4,2,1],
[4,1,2,3],[4,1,3,2],[4,2,1,3],[4,2,3,1],[4,3,1,2],[4,3,2,1]]
count = 0
check_set = {1,2,3,4}
#各行を選ぶ
#各列が1から4が1つずつで構成されているか確かめる
for i in range(24):
for j in range(24):
for k in range(24):
for m in range(24):
p = check_list[i]
q = check_list[j]
r = check_list[k]
s = check_list[m]
if {p[0],q[0],r[0],s[0]} == check_set:
if {p[1],q[1],r[1],s[1]} == check_set:
if {p[2],q[2],r[2],s[2]} == check_set:
if {p[3],q[3],r[3],s[3]} == check_set:
count += 1
end = time.time()
#結果を出力する
print(count)
print('in',end - start,'sec.')
中身はさっき説明した通り、4つの行を順番に選び出し、その後4つの列がちゃんと1~4が1回ずつで構成されているかを調べる、という手順です。時間計測の機能も付けて、どれくらいの時間で実行されるのかも調べてみることにします。
これを実行してみた結果がこちら。
576
in 0.14403176307678223 sec.
つまり、このコンピュータは「およそ0.14秒で、この問題の答えは576通りだという結果を出力した」ということになります。
実際に各予備校の解答速報などで結果を調べてみると、確かに答えは576通りだと分かりますから、どうやら本当に1秒と掛からず正解を出してしまったようです。
パソコン、すごい!
[2] 実際はもっと複雑な計算をするのでこれどころではないです。
[3] 本当はもう少し細々としたことが間に挟まるのでこれよりは多いですが、それでも大した量にはならないです。
で、まあ、ここで「パソコン、すごい!」で終わっても良いのですが、それはちょっと味気ないですよね。だってそりゃパソコンがすごいのは当たり前です[4]。人間より高速で計算を処理できるなんて分かり切っていたことです。
しかし、現実に入試問題としてこれが出されたということは、理論上20~30分かければ人間にも解けるように何か工夫のしようがあるということです[5]。少なくとも、人間には130万回の計算を20~30分で処理する能力はありませんから、もっと人間が解くのに適した方法が何かあるはずです。
それを考えていきましょう。
「どのように数字を置いても良い」という状態は、最初の一歩を踏み出すには余りにも大変です。まずは、仮に文字を置くところから始めましょう。
最初の一行には、1~4の数字がそれぞれ1つずつ入ります。どこに何が入るかは分かりませんが、とりあえず左から順に「1,2,3,4」と入れます。
1 | 2 | 3 | 4 |
☆ | |||
さて、残りのマスを左上から順に埋めていくことを考えます。手始めに、上記の赤い星マークがついた地点には、どんな数字が入りうるでしょうか?
少し考えてみると、2,3,4のいずれかが入ることが分かります。ここからは場合分けが必要です。
・☆に2が入るとき
こんな感じになります。
1 | 2 | 3 | 4 |
2 | 〇 | ||
次に○マークを付けた位置には何が入るでしょうか?
先ほどと同じように考えると「1,3,4」のいずれかが入ると分かります。
(1-i) ☆に2を、○に1を入れた場合
先ほどの○マークに1を入れると、その行の4と3が入る位置が確定します。
1 | 2 | 3 | 4 |
2 | 1 | 4 | 3 |
◎ | |||
次の◎マークには何が入るでしょうか? 同様に考えると、3か4が入ることが分かります。
⇒(1-i-i) ☆に2、○に1、◎に3を入れた場合
先ほどの◎マークに3を入れると、その下が4で確定し、ついでに連鎖して左から2列目の残りも確定します。
1 | 2 | 3 | 4 |
2 | 1 | 4 | 3 |
3 | 4 | ||
4 | 3 |
残った左下2マスは、以下のいずれかの形になることが分かります。
1 | 2 | 3 | 4 |
2 | 1 | 4 | 3 |
3 | 4 | 1 | 2 |
4 | 3 | 2 | 1 |
1 | 2 | 3 | 4 |
2 | 1 | 4 | 3 |
3 | 4 | 2 | 1 |
4 | 3 | 1 | 2 |
このパターンの探索はこれで終了です。
⇒(1-i-ii) ☆に2、○に1、◎に4を入れた場合
◎に4を入れると以下の通りです。
1 | 2 | 3 | 4 |
2 | 1 | 4 | 3 |
4 | 3 | ||
3 | 4 |
左下の埋め方は(1-i-ii)と同様に2パターンあります。
よって、このパターンの探索もこれで終了です。
(1-ii) ☆に2を、○に3を入れた場合
再び「〇に何を入れるか」の分岐に戻ります。
1 | 2 | 3 | 4 |
2 | 3 | 4 | 1 |
◎ | |||
◎には3か4のいずれかが入ります。どちらが入るかによって場合分けをします。
・◎に3を入れた場合、入れ方は以下の1通りに確定します。
1 | 2 | 3 | 4 |
2 | 3 | 4 | 1 |
3 | 4 | 1 | 2 |
4 | 1 | 2 | 3 |
・◎に4を入れた場合、入れ方は以下の1通りに確定します。
1 | 2 | 3 | 4 |
2 | 3 | 4 | 1 |
4 | 1 | 2 | 3 |
3 | 4 | 1 | 2 |
1箇所埋めると残りも決まるのは気持ちいいですね!
ともあれ、この節は2パターンが考えられます。
(1-iii) ☆に2を、○に4を入れた場合
以下のような形になります。
1 | 2 | 3 | 4 |
2 | 4 | 1 | 3 |
◎ | |||
上記の◎に入りうる数は3,4のいずれかです。
先ほどの(1-ii)で考察した通り、3が入るパターンは以下のように確定します。
1 | 2 | 3 | 4 |
2 | 4 | 1 | 3 |
3 | 4 | 1 | 2 |
4 | 3 | 2 | 1 |
また、4が入るパターンは以下のように確定します。
1 | 2 | 3 | 4 |
2 | 4 | 1 | 3 |
4 | 3 | 2 | 1 |
3 | 1 | 4 | 2 |
よって、この節も2パターンになります。
∴以上より、(1)☆に2を入れるパターンは合計で8パターンあります。
・☆に3を入れる場合
・☆に4を入れる場合
については、今ほどと同様に考えるとそれぞれ8パターンずつであると分かります[6]。
というわけで、これらの合計は8+8+8=24パターンになります。
これらに加え、1行目の1~4をどう並べるのかによってさらに4!=24パターンがあるので、合計は24×24=576通りになります。
やった! 576通りになった! 人間が工夫して精緻に場合分けを行えば、コンピュータほどの速さではないにせよ20~30分で解けるようになるわけですね。
……まあ、精緻化すると何十パターンにもなる場合分けを、1つのミスもなく正確に数え上げられればの話ですが。こうなると数学力というよりは、腕力と注意力の試験ではないかという気もしますね。
[4] 当たり前の理由を説明しようとすると、これはまたドツボにハマるんですが……。
[5] そうじゃないことも多いですが!
[6] 詳細に書いても良いのですが、先ほどの(1)と同じことをやるだけなのでカットします。本質的には同様ではないので、本番の試験ではちゃんと書いた方が良いです。
今回は大学入試の数学を、プログラミングと手計算の両方で解いてみました。どちらの方が良い悪いという話ではないですし、そもそも今回はかなり小さい範囲での求値問題で、プログラムも簡単なので、(プログラムを書く時間を含めたとて)どうあがいても最終的にはコンピュータが勝つのは当然でした。
それでも尚面白いのは、プログラミングの場合と手計算の場合とで効率化のレベル、レイヤーが全然違うことにあると思います。プログラミングは「コンピュータが解けるレベルまでの効率化」であり、手計算は「人間が解けるレベルの効率化」が必要で、同じ問題をどこまで細かい粒度に分解するかによって問題の見え方が全然違うのです。
かたや、行単位で見て組み合わせの総列挙をする。
かたや、左上に入るマスで場合分けと仮置きを繰り返す。
解く主体によって問題の見え方が変わる、ちょっと素敵だと思いませんか?
余談ですが、この記事を書くにあたって私は別の入試問題もプログラミングで解いてみました。
2020年京大理系第4問(ある多項式が3で割れる回数の最大値)や、2015年東大理系第5問(comb(2015,m)が偶数になる最小の正整数m)あたりを解いてみたのですが、どちらも問題文の内容をPythonの言葉で書き起こしてしまえば、何の工夫もなく解けるような問題でした。
これはこれでPythonのすごさを実感できる良いケースになったのですが、とはいえ「コンピュータがすごい!」という話だけをいくら記事にしたところで、それ単体だと面白くはないわけです(特に、技術ブログでもない市井の数学ファンのブログとしては尚更面白くはないでしょう)。
そんな中で今回取り上げたこの問題は、「見方を変える面白さ」が伝わる良い問題だったのではないかと思います。是非、この面白さが伝われば幸いです。
Copyright ©金沢市・野々市市・白山市の塾なら東大セミナー All Rights Reserved.