数学ラノベ『君と紡ぐソネット』作中問題の考察（１）

この記事では数学と東大受験を題材にしたライトノベル、講談社ラノベ文庫『君と紡ぐソネット ～黄昏の数学少女～』（暁社夕帆 著）に登場する作中問題で、特に難しいと思われるものについて解法を考察します。わたしは数学科などは出ていないので、あくまでも厳密性は欠く略解としてご容赦ください。なおこのライトノベル、学術系YouTuberヨビノリたくみ氏が帯の推薦文を書いています。ヘッダー画像はAmazonより。

君と紡ぐソネット ~黄昏の数学少女~ (講談社ラノベ文庫)

東京大学本試験・第六問

作中で東大理系（本試験）の最終問題として登場する、いわばラスボス的な問題です。ググっても同様の問題は見つかりませんでした。

【問題】

【東京大学本試験・第六問】
異なるｎ個の自然数を任意に選び、選んだｎ個の数の集合をＡとする。このとき、集合Ａの空でない部分集合Ｂで、次の条件を満たすものが存在することを証明せよ。
条件：部分集合Ｂの全ての要素の和がｎで割り切れる。

『君と紡ぐソネット』初版 p.289

実は作中で、「鳩の巣原理」を使うことが示唆されています。抽象度が高いので、まず具体例で検討します。

【具体例】

例えばn = 6とします。6個の自然数を任意に選び、集合Aを｛1, 2, 3, 8, 11, 20｝としてみます。部分集合Bとは例えば｛1, 2｝や｛1, 3, 20｝や｛3, 8, 11, 20｝などの作り方ができます。ここで｛1, 3, 20｝を見てみましょう。この要素を全て足すと24となり、これはn = 6で割り切れます。つまり、問題文の条件を満たす部分集合Bはn = 6でたしかに存在しましたね。他に｛1, 2, 3｝と抽出しても和が6で、n = 6で割り切れます。｛1, 3, 8｝や｛1, 2, 3, 8, 11, 20｝でも、その合計はn = 6で割り切れます。
このように、本問で証明するのは「集合A（任意のn個の自然数）から、その和がnで割り切れるような1個以上の数のセットを取り出すことは必ず可能である」ということです。

【略解】

集合Aのn個の要素をa1、a2、a3、…….、anとしてみます。
同時に、n個の要素を一つずつ足したものである
b1 = a1
b2 = a1 + a2
b3 = a1 + a2 + a3
……
bn = a1 + a2 + … + an
を考えてみます。ここで2通りの場合分けが生じます。

①これらのうちnで割り切れるものがある場合

例えば　b4 = a1 + a2 + a3 + a4　がnで割り切れたのであれば、b4は｛a1, a2, a3, a4｝という4つを集合Aから抜き出した部分集合Bの要素の和です。よって、条件を満たす部分集合が存在することになります。これは簡単。

②これらのいずれもnで割り切れない場合

鳩の巣原理より、b1からbnまでに、nで割った余りが等しい二数が必ず存在することになります（b1からbnまでn個あるので、必ずnで割った余りが重複する）。
これをbpとbq（p < q）とすると、bq - bpは必ずnで割り切れます。これは条件を満たす部分集合が存在することを意味します。
例えば　b2 = a1 + a2　と　b4 = a1 + a2 + a3 + a4　のnで割った余りが等しい場合、余りが等しいもの同士の引き算なので　b4 - b2 = a3 + a4　は必ずnで割り切れます。このb4 - b2は、｛a3, a4｝という2つを集合Aから抜き出した部分集合Bの要素の和になっています。

以上①②より、集合Aの空でない部分集合でその要素の和がnで割り切れるものが必ず存在することが証明できました。

---

部分集合Bの作り方と、鳩の巣原理の使い方がポイントになっています。高校数学として普通に解けるものの、集合についての理解が要求されますね。とりあえず小さなnで具体的に考えてみるのが近道でしょうか。