スポンサーサイト

-- -- --
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

たのしいすうがくのメモ

2011 07 14
たまたま見たツイートについハマってしまったので、その経過をメモしておく。

1から10000までの番号がついた電灯がある。1の倍数の電灯のスイッチを押し、次に2の倍数のスイッチを押し、次に3の倍数のスイッチを押し…と、これを10000回行った後、点灯している電灯の数はいくつか。初期状態で電球は消灯している。(コマ大数学科第12回・改) #mathless than a minute ago via twittbot.net Favorite Retweet Reply


スイッチは押すと点き、また押すと消えるというのは暗黙の前提だろう。
1試行目は全点灯、2試行目は2の倍数の電球が消灯、となる。
3試行目は、6の倍数を除く3の倍数の電球が消灯、6の倍数の電球が点灯、それ以外は前回の状態を維持…

だんだん分からなくなってきたし、文章で説明できなくなってきた。
ということで、10個くらいを0(消灯)、1(点灯)で整理することにしよう。
ちなみに列を揃えたいので10はAと書いた。

(n) 123456789A
--------------------
(0) 0000000000
(1) 1111111111
(2) 1010101010
(3) 1000111000
(4) 1001111100
(5) 1001011101
(6) 1001001101
(7) 1001000101
(8) 1001000001
(9) 1001000011
(A) 1001000010

ここで気付いた。n試行目以後ではn番目以前の電球の状態は二度と変化しない…!
それを踏まえて、確定部分だけ抜き出して見ると、

(n) 123456789A
--------------------
(1) 1
(2) 10
(3) 100
(4) 1001
(5) 10010
(6) 100100
(7) 1001000
(8) 10010000
(9) 100100001
(A) 1001000010

1、4、9番目が点灯のまま残る(10000試行目であっても)。
ここまで来て、ある仮説が浮かんでくる。

「もしかして、平方数の場所だけ点灯して残るのでは?」

では、その仮説を検証しよう。もしそれが正しければ、解は「10000までの平方数の個数」だと言える。


ところで、ある場所(n番目)の電球はどういう条件で変わるのか。
上の表を見れば、それは「(nの約数)試行目のとき」だと分かる。
4番目であれば1、2、4試行目で、6番目であれば1、2、3、6試行目で変わる。

0(消灯)なのか、1(点灯)なのかの分類は、約数の個数を調べれば良い。
約数の個数が奇数であれば点灯、偶数であれば消灯として結果を迎える。

ある2以上の自然数を素因数分解したとき、それを

p[1]^q[1] × p[2]^q[2] × … × p[m]^q[m]

と書くならば、約数の個数Iは、

I = (q[1]+1) × (q[2]+1) × … × (q[m]+1)

だ。なんでかというと、それぞれの素因数をいくつ使うか、というパターンの組み合わせの数だから。
そして、+1するのはその素因数を「使わない」場合もあるから。

ここで、平方数の約数の個数を考えたとき、あるq[k]は必ず偶数だ。
ゆえにq[k]+1は全て奇数であり、全ての積であるIは必ず奇数になる。
平方数でなければ、q[k]+1の少なくとも1つは偶数なので、Iは偶数になる。

従って、(1も含め)平方数の場合のみ約数の個数は奇数であり、
その性質によって、「平方数の場所だけが点灯して残る」と結論付けられる。
検証完了。
つまり、求めるべきものは「10000までの平方数の個数」で正しい。
10000 = 100^2 ゆえに、求める解は「100」
ちなみに1000個の電球だったら、31。

---------

はー。
と、いう具合に、試行錯誤→仮説提案→仮説検証→問題解決のフローを辿れたので楽しかった!
まさかとは思うけれど、間違いでありませぬように。

あとこれ全部iPadで書いたけど結構疲れた。カーソル移動とコピペが手間…

スポンサーサイト
Comment

管理者のみに表示
try{ var pageTracker = _gat._getTracker("UA-xxxxxx-x"); pageTracker._trackPageview(); } catch(err) {}
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。