2006年07月07日 22:30 [Edit]

コマネチ大学数学科第12講 + javascript

今回もかけ声はαριθμοι κυβερυουν συμπανのコマネチ大学数学科。顧問は中村先生。

今回はプログラマーにとってもうれしい問題。

問題:
1から1000までの番号とスイッチがついた電球があります。まず、1の倍数の電球のスイッチを押し、次に2の倍数のスイッチを押し....これを1000回行った後、点灯している電球の数はいくつあるでしょう?ただし、最初の状態では電球は消灯状態です。

この問題は「1から1000までの数において、1とそれ自身を含む因数の数が奇数のものはいくつあるでしょう?」という問題に還元される。

エレガントな解答に行く前に、コマ大生たちの足跡をjavascriptでたぐってみよう。

どんな数が現れただろう?そう。平方数なのである。よって問題は「1から1000までの間に、平方数はいくつあるか?」に還元されて、あとは1000の平方根を取って少数以下を切り捨てれば、答えの31が出るという仕掛け。マス北野と女子東大生チーム、見事正解。

ところで、第12講では、「約数の和が奇数になるのは、常に平方数である」ということをきちんと証明していない(直感的な説明は中村先生がしていたが)。なぜそうなのかは、↑の「素数入門」にも載っている以下の定理を使うことが出来る。

pp.195

正整数nの標準素因数分解を、
n = paqbrc... とすると、 [因数の数]σ0(n) = (a + 1)(b + 1)(c + 1)...

σ0(n) が奇数ということは、 (a + 1)(b + 1)(c + 1)...の全ての項が奇数ということなので、a,b,c....は全て偶数。よってpaqbrc...は平方数となる。

そんなわけで、因数の不思議についてもっと知りたい人は是非本書を入手のこと。以前も紹介したが、手頃な問題ということで、ここで改めて紹介する次第。

Dan the Auditor


この記事へのトラックバックURL

この記事へのトラックバック
撮れてない....なぜだ....
コマネチ大学数学科13課-見逃しました【404 Blog Not Found】at 2006年07月14日 17:24
ポジティブシンキングばかりでは、見落とす・無理難題をほおって置いて現場がやる気な
【新しい手法の模索】ネガティブミーティングというものがあるそうです【気ままにブログる】at 2006年07月09日 16:49
また録画忘れちゃったよ。多分僕みたいな人のために予約録画機能があるんだろう。はやくHDDを手に入れなさいということだろうか。 しょうがないから弾さんのブログで問題を確認。弾さん、もうこの番組の解説においてデファクトスタンダードとなっていますね。 404 Blog Not
[Python Memo]コマネチ大学数学課(電球の問題)【二十代は模索のときブログ】at 2006年07月08日 08:51
この記事へのコメント
「約数の個数が奇数なのは平方数だけ」の証明だけなら、以下のようにすれば、件の素因数分解に関する定理を使うまでもないです。(中村先生のご説明を見ていないので、内容が重なってるかもしれませんが。)
nの約数kのそれぞれについて、n/k(これもnの約数)とペアを組ませます。もし、どの約数も自分以外の数とペアになっているならば、約数の個数はペアの数の2倍(つまり偶数)のはずですが、今はそうではありません。よって、ある約数kは自分自身とペアになっている(妙な表現ですが…)はずで、n/k=k、つまりn=k^2でnは平方数となります。
Posted by MarriageTheorem at 2008年04月05日 11:53