日本数学オリンピック本選　組合せ論問題を解くのに知っておきたいこと

2025年1月21日 22:00

はじめに

JMO本選の出題分野の１つに組み合わせ論（数え上げ、ゲーム理論、グラフ理論、離散数学）があり、毎年出題されています。
他の分野と違って教科書レベルではあまり取り扱わないようなタイプの問題が多く、
慣れなくて困惑する受験者も多いと思います。
ですが、そのせいか、他の分野の問題よりも易しめに設定されている印象です。

問題のほとんどは文章で書かれているので、
状況を数理的に考えるモデルをどのように頭の中で構築するかが鍵になります。
解答も数式はほとんど使わず、
論理的に誤りのない文章で説明する必要があり、
このあたりはよく訓練しておいた方が良いでしょう。

組み合わせ論問題の解き方の方針を一概に語るのは難しいですが、
第３問までの過去問を解いた経験から、
いくつかのよくあるテクニックを紹介します。

組み合わせ問題の基本的な問題は以下にまとめてあります。
JMO本選　組み合わせ・ゲームの基礎問題　～実は結構簡単～｜光捷｜note

基本：具体例の提示と、それが最善であることの証明

組み合わせ論の問題のうち証明問題でないものの基本方針は
①実際にやってみて最も良さそうな具体例を作る
②それよりいいものはできないことを証明する
です。ですので、基本は実験してみることです。

結論を答案にする際、
①は実際の例を１つ提示すれば良いだけですので
論理的には難しいところはありません。
（言葉でどう表現するかが難しいケースはありますが・・・。）
論理的に特に気を遣うのは②です。
一つ一つの論理展開に誤りがないか、注意深く示していきましょう。

ゲームの問題

２人で（あまり面白くない）ゲームを行う問題も頻出です。
２人の行う操作が同じ場合、お互いの最善戦略も同じことが多いです。
つまり、①の結論が出たあと、
同じ議論を２人の立場を入れ替えて行うだけで容易に②が示せるケースが多々あります。
検討方針として、まずは行ってみるべきといえるでしょう。

極端な例を考える

①の最も良さそうな例を考えるときのコツは、
極端なパターンを考えることです。
例えば以下の問題では、ひたすら端から順に選ぶことが最善手となります。
2022年日本数学オリンピック本選　第１問解答例｜光捷
また、以下の問題では、左端から右端への移動を考えるだけで
問題の全体像がほとんど見えてきます。
2021年日本数学オリンピック本選　第２問解答例｜光捷

マス目問題　～マスの塗分け～

頻出ではないですが、マス目にブロックなどを置いて埋める問題が出てきます。
このような問題には、マス目に色を付けることが常套テクニックです。

最もシンプルな問題として以下の問題を考えてみてください。

問題：
８×８のマス目から２つのマスを除いた以下のマス目を考える。
１×２のブロックを重ねることなくおいて
このマス目を全て埋めることができるか。

答え：
以下のように白と黒に色分けをすると、
１×２のブロックはどのようにおいても白と黒のマスを１つずつ埋めることになる。
全体の白と黒のマス目の数は等しくないので、
すべて埋めることは不可能である。

このような考え方を応用して解く典型的な問題が以下の過去問です。
2005年日本数学オリンピック本選　第１問解答例｜光捷

グラフと木

数学のグラフ理論とは、点を線でつないだ形状です。
グラフ理論 - Wikipedia
その中ですべてつながっていて（連結）ループ（閉路）を持たないものが木と呼ばれます。
木 (数学) - Wikipedia

あらわにグラフ理論の用語で出題されることはありませんが、
問題を頭の中で整理するときにこのようなモデルをイメージすると便利なことがしばしばあります。
また、「閉路」「連結」といった用語が答案作成時に便利になることがあります。
これらの記事を一読しておく価値はあります。

あからさまにこのようなモデルを使う出題もありました。
2010年日本数学オリンピック本選　第３問解答例｜光捷

おわりに

繰り返しますが、組み合わせ論問題といっても多種多様であり、
本記事もかなりトピックがばらばらになってしまいました。
とはいえ、「どんなモデルをイメージして考えるかを考える」ことを丁寧に行えば、
解にたどり着くのは他の分野よりも易しい分野になっていると思います。
臆せず挑戦してみましょう。

お知らせ：

少しでも興味深い、楽しいと感じたらぜひスキやコメント、フォローください！
間違いなど見つけましたら是非お教えください。
他に公開している記事などの一覧はこちら
ぜひ初めに見てください。｜光捷 (note.com)