1 から 100 までの和

足し算

僕は普通の子供だったから「１から１００までの和を求めなさい」の問題を出されても １＋２＋３＋４＋５＋６…９８＋９９＋１００ と頭から順に足したと思う。途中で面倒臭くなって、もしかしたら １，１１，２１，３１…２，１２，２２，３２… と何かの纏まりを使って工夫できないかと考えた人も居ただろう。

１から９の合計

まず １ から ９ までの合計が ４５ になることを確かめてみる。これは １＋２＋３＋４＋５＋６＋７＋８＋９ の事。

沢山の足し算をする時は、切りのいい数で計算する方が簡単。足し算は順序を変えても答えが同じだから。
１＋２＋３＋４＋５＋６＋７＋８＋９ ＝
３　　＋３＋９　　＋６＋１５　＋９ ＝
６　　　　＋９　　＋２１　　　＋９ ＝
６　　　　＋９　　＋３０　　　　　 ＝
１５　　　　　　　＋３０ 　　　　　＝ ４５

１０ から ９９ の合計（１０の位だけ合計する）

さて次は １０ から ９９ の合計を求める。

まずは１０の位だけを合計したい。１０＋２０＋…＋８０＋９０ は ４５０。これは１から９の合計の１０倍と同じ。式にしたら１０*（１＋２＋…＋８＋９）＝１０*４５＝４５０。

この固まりが １ から １００ の間に １０個ある。１０個というのは １０（２０、３０…８０、９０）の段、１１（２１、３１…８１、９１）の段、１２（２２、３２…８２、９２）の段…１８（２８、３８…８８、９８）の段、１９（２９、３９…８９、９９）の段、という事。その合計は ４５０*１０＝４５００。これが十の位の合計。

10～99までの合計。

段	式	合計
10	10+20+30+40+50+60+70+80+90	450
11	10+20+30+40+50+60+70+80+90+1+1+1+1+1+1+1+1+1	450+0
12	10+20+30+40+50+60+70+80+90+2+2+2+2+2+2+2+2+2	450+?
13	10+20+30+40+50+60+70+80+90+3+3+3+3+3+3+3+3+3	450+?
14	10+20+30+40+50+60+70+80+90+4+4+4+4+4+4+4+4+4	450+?
15	10+20+30+40+50+60+70+80+90+5+5+5+5+5+5+5+5+5	450+?
16	10+20+30+40+50+60+70+80+90+6+6+6+6+6+6+6+6+6	450+?
17	10+20+30+40+50+60+70+80+90+7+7+7+7+7+7+7+7+7	450+?
18	10+20+30+40+50+60+70+80+90+8+8+8+8+8+8+8+8+8	450+?
19	10+20+30+40+50+60+70+80+90+9+9+9+9+9+9+9+9+9	450+?
合計	450*10+?	4500+?

１０ から ９９ の合計（１の位だけ合計する）

次に一の位を合計する。上の図を縦に見れば１～９が並んでいるのが分かる。これは１が９個、２が９個…８が９個、９が９個あると言えるね。

これを式にすると次の感じ。
（９*１）＋（９*２）＋（９*３）＋…＋（９*７）＋（９*８）＋（９*９）

これは９の段の掛け算の合計（９＋１８＋２７…＋６３＋７２＋８１）と同じだよ。

（２が９個）は（１が９個）の ２倍、３は（１が９個）の ３倍。だから、次の感じになる。
（９*１）＋（９*２）＋（９*３）＋…＋（９*７）＋（９*８）＋（９*９） ＝
（９*１）*１＋（９*１）*２＋（９*１）*３＋…＋（９*１）*７＋（９*１）*８＋（９*１）*９ ＝
（９*１）（１＋２＋３＋…＋７＋８＋９）

（１～９）が縦に並んでいるのを見れば、それが９個あるから ９*(１＋２…８＋９）と考えてもいいね。

１ から ９ の合計は ４５。その１０倍が４５０、それから４５を引く。
９*(１＋２…８＋９） ＝
１０*(１＋２…８＋９）―(１＋２…８＋９） ＝
１０*４５－４５ ＝
４５０－４５ ＝
４０５

十の位の合計は ４５００、一の位の合計は ４０５。
４５００ ＋ ４０５ ＝ ４９０５

こうして １０ から ９９ までの合計が求められました。

１ から １００ の合計

その他

段	式	合計
0-9	0+1+2+3+4+5+6+7+8+9	45
100		100

１０から９９の合計にその他を合計すれば１から１００までの合計が求まります。
４９０５ ＋ ４５ ＋ １００ ＝
４９５０ ＋ １００ ＝
５０５０

将棋盤で考える

これを足し算の式じゃなくて、正方形の面積として考えてもいいはず。正方形に対角線を引いて半分のマス目を数える。これは正方形を半分にしたのと同じ。

９*９の正方形と言えば将棋盤。だから１ から ９ の合計は将棋盤のマス目を数えてもいい。



９*９ の正方形の面積は８１。その半分は ８１÷２＝４０．５。これに ９ の半分の ４．５ を足せば ４５。これは対角線を引いたら半分だけはみ出すマスがあるので、このはみ出した部分を足したもの。

これを式にすれば（９ * ９ ÷ ２）＋（９ ÷ ２）。これをｎの一般式にすると（ｎ*ｎ÷２）＋（ｎ÷２）になる。
（ｎ÷２） を仮に ｙ と置けば
ｎ*（ｎ÷２）＋（ｎ÷２） ＝
ｎ*ｙ＋ｙ ＝
ｎ*ｙ＋1*ｙ ＝
（ｎ＋1）*ｙ

ｙ を元に戻せば
（ｎ＋１）*（ｎ÷２） ＝
（１＋ｎ）ｎ／２

この式が正しい事はブレーズ・パスカル(1623 - 1662)が１０歳の時に証明したそうだ。この式は総和Σ(i=1, n) i の公式でもある。

ガウスの解法

さてこの問題をヨハン・カール・フリードリヒ・ガウス (1777 - 1855) は次のように解いた。１ から １００ までの和を求めるのに順番通りに計算する必要はない。そこで次のような２つのペアを作った。

0		0
1	100	101
2	99	101
3	98	101
4	97	101
...	...	101
47	54	101
48	53	101
49	52	101
50	51	101

１０１ が ５０個ある。
１０１ * ５０ ＝ ５０５０

将棋盤を次のように使ったのと同じ。



これは合計を100になるようによっとずらしても使える。

0	100	100
1	99	100
2	98	100
3	97	100
4	96	100
...	...	100
47	53	100
48	52	100
49	51	100
50		50

これなら４９個の１００と残りの１００と５０がある。
４９００＋１００＋５０ ＝
５０００＋５０ ＝
５０５０。

計算に必要な時間

さて １ から １００ までを計算するのに 一回の和を求めるのに １ 秒かかる計算機があるとする。一つの計算から次の計算に移るmまでの時間を０とした時、この計算機が答えを出すのは必要なのは何秒であろうか。

これは １ から １００ までの足し算の式から ＋ のマークの個数を数えればよい。１ から ９９ の数字の右側に ＋ のマークがあり １００ の右側にはないので ＋ マークの個数は ９９個ある。よって ９９回の計算をするので ９９秒後に答えが出る。

0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45, +の数は (n-1), この場合は9個。

この ＋マークを演算子と呼ぶ。これが 一回の計算を意味する。一回の計算とは、数に対する１回の操作と考えてよい。

では複数台の計算機を使えば最短で何秒で答えが出るだろうか。

１回目	一回の演算で和を作るには二つの数が必要。１ から １００ の数を（１と２）、（３と４）と５０個のまとまりを作る。これを計算機を使って和を求める。
２回目	これで ５０個の和が求まったので次にまた２つずつの組み合わせを作り ２５ 個の計算機で計算する。
３回目	また二つずつの組み合わせを作り １２個の計算機で計算する。このとき１つだけ計算できない数が余る（２５ は奇数で ２ で割り切れないから余りがある）。
４回目	１２個の数を計算して ６個。
５回目	６個の数を計算して ３個。
６回目	３個の計算結果にさっきの余りの一つを加えて ４ つの数にして計算して 二個。
７回目	２個を計算して １ つの和が求まる。

５０個の計算機を使えば ７ 秒後に答えが求まる。並列に計算すれば速くなる。これは ÷２ を繰り返しているのと同じ。

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

足し算とトーナメント

さて、足し算を 二つずつ足してゆくのは何かに似ていると思いませんか。二つの数が 一つになる、二つのものが 一つになる、二つのものから 一つだけが選ばれる。

野球やオリンピック、サッカー、囲碁などのトーナメント方式による勝ち上がり方はこの足し算と同じ構造を持っていそうだよ。

１００人の選手やチームがトーナメントで戦うと、優勝者が決まる迄に何試合が必要か。これは対戦会場を幾つ用意すればよいかとか、対戦が終わるまでに何日掛かるか、を解くのと同じ問題だね。

１００名のうち、優勝者を１名とすれば、残りの ９９名は負ける。９９名が負けるためには負けるための試合が必要。つまり ９９の試合が必要。

９９の試合をするためには、９９の会場が必要だし、一日一試合だけなら９９日が必要。

一人が一日に一回の試合ならば、平行して試合をしていい。この場合、トーナメントは何日必要か、また何会場を用意すればよいか。これは最後に１以下になるまで １００を２で割って行けばよい。途中で割り切れない数（奇数）が出るので端数があったら切り上げる。

1) 100 / 2 = 50
2) 50 / 2 = 25
3) 25 / 2 = 12.5 = 13
4) 13 / 2 = 6.5 = 7
5) 7 / 2 = 3.5 = 4
6) 4 / 2 = 2
7) 2 / 2 = 1

１になるまで２で割る問題は、逆に言えば １００を超えるまで ２を掛けても同じはず。これは ２の何乗が １００を超えるかという問題になる。２、４、８、１６、３２、６４、１２８、２５６…

２の７乗が１２８だから ７日目で優勝者が決まる。

では ６５ 人から １２８ 人が参加するトーナメントは必ず ７ 日で終わるか。これを最小と最大で確かめてみよう。
1) 65 / 2 = 32 余り1
2) 32 / 2 = 16
3) 16 / 2 = 8
4) 8 / 2 = 4
5) 4 / 2 = 2
6) 2 / 2 = 1 だだし余りが１あるので
7) 2 / 2 = 1

1) 128 / 2 = 64
2) 64 / 2 = 32
3) 32 / 2 = 16
4) 16 / 2 = 8
5) 8 / 2 = 4
6) 4 / 2 = 2
7) 2 / 2 = 1

１２９ 人だと最初の段階で 一 人余ってその人との戦いがどこかで挟まれるのでもう 一日多くなる計算だ。

では、最初に ５０部屋も用意できないよと言う場合はどうすればよいか。用意できる部屋数を ２０とすると 一部屋で 二人が対戦するのだから 一度に ４０人が試合を行う。すると １００人が ４０人になるまでは ２０部屋を使ってゆく。

1) 100 - 20 = 80
2) 80 - 20 = 60
3) 60 - 20 = 40
4) 40 / 2 = 20
5) 20 / 2 = 10
6) 10 / 2 = 5
7) 5 / 2 = 2 ...1
8) 2 / 2 = 1 (+1)
9) 2 / 2 = 1

よって優勝者が出るまでに ９日間を必要とする。

数の和は、面積を求めたりトーナメントを計算したりするのと、よく似ているというお話でした。