一見難しい問題を「小さい場合」から考える方法

「1から100までの整数をすべて足すといくつ？」と聞かれて、1から順に足し始める人はあまりいないでしょう。しかし、どうすればもっと賢く解けるのかは、すぐには思いつかないかもしれません。そんなときに頼りになるのが、「数を小さくして考えてみる」という方法です。この記事では、2つの問題で、この方法の使い方と注意点を見ていきます。

1から100の和を、小さい数で試す

問題：$1+2+3+\cdots+100$ はいくつでしょうか。

100個の数を足すのは大変ですが、1から4までなら簡単です。1から $n$ までの和を、$n=1,2,3,4,5$ について調べてみます。

1、3、6、10、15 となります。どうやって計算するかを見直すと、1から4までなら、$1+4=5$、$2+3=5$ のように、端から組にして足せることに気づきます。1から5までなら、$1+5=6$、$2+4=6$ と組を作ると、真ん中の3だけが余ります。

同じ作戦を100に使ってみましょう。$1+100=101$、$2+99=101$ のように、端から組を作ると、どの組も合計は101です。組の数は100個の数を2つずつに分けて50組なので、答えは次のとおりです。

$$101\times50=5050$$

この式は、「合計が101になる組が50個ある」という意味です。ガウスが子どものころにこの問題を解いたという逸話がよく語られますが、ここで大切なのは逸話の真偽ではなく、小さい例から「組にして足す」という方法が見つかったという流れです。一般には、1から $n$ までの和は $\frac{n(n+1)}{2}$ になります。

100人のトーナメント、何試合？

問題：100人が参加するトーナメント（負けたら脱落する勝ち抜き戦）で、優勝が決まるまでに何試合が行われるでしょうか。1回戦で人数が割り切れない場合は、不戦勝があるものとします。

まず、小さい場合から。4人なら、準決勝が2試合、決勝が1試合で、合計3試合です。8人なら、4+2+1で7試合です。人数より1少ない数になっています。

「人数−1」になるのはなぜでしょうか。1試合ごとに、ちょうど1人が負けて脱落します。優勝者が決まったとき、脱落しているのは優勝者以外の全員です。100人なら99人が脱落するので、試合数は99です。

この考え方には、大きな利点があります。トーナメントの組み方（不戦勝があるかどうか）に関係なく、答えが99と分かるのです。小さい場合の観察から、「試合数ではなく、脱落者の数を数える」という見方に気づけました。

小さい場合から、予想して、説明する

小さい場合から考えるときは、3つの段階を意識すると進めやすくなります。

1. 小さい場合を、実際に手を動かして調べる。
2. 規則を予想する（「人数−1になりそうだ」）。
3. その予想が、なぜ一般に成り立つのかを説明する。

注意したいのは、3番目を飛ばしてしまわないことです。小さい場合でうまくいっても、大きい場合で成り立つとは限りません。なぜそうなるのかを自分の言葉で説明できたときに、初めて「解けた」と言えます。

総当たり戦の試合数も、同じ流れで考えられます。$n$ 人の総当たり戦で、1人目は他の $n-1$ 人と対戦し、2人目は残りの $n-2$ 人と、というように数えると、$(n-1)+(n-2)+\cdots+1$ となり、さきほどの和の公式が使えます。10人なら $9+8+\cdots+1=45$ 試合です。まったく別の問題が、同じ形でつながりました。

まとめ

難しそうな問題に出会ったら、まず数を小さくして、手を動かしてみましょう。小さい場合なら、答えを実際に確かめられます。そこから規則を予想し、なぜ成り立つのかを説明できれば、大きな場合にも通用する考え方が手に入ります。大きな数の問題は、実は小さな問題の積み重ねです。