Hatena::ブログ(Diary)

小人さんの妄想 このページをアンテナに追加 RSSフィード Twitter

2008-11-29

円で隙間を埋め尽くす

平面上で円をぴったりくっつけて置くと、6角形の配置に並びます。

3つの円の間には隙間が残るので、この隙間にぴったり入るような小さな円をはめこみます。

それでも隙間が残るので、残った小さな隙間にも、さらにぴったり収まるような小さい円をはめこみます。

このように、円と円の隙間に、もっと小さな円を次々に、どこまでもあてはめていったら・・・

最後には、平面は円で隙間なく埋め尽くすことができるのでしょうか?

それとも、どこまで行っても隙間が残るのでしょうか?

f:id:rikunora:20081129230701p:image


 答: 平面は円で埋め尽くされる。隙間は「ほとんど」残らない。


えー、そんなバカな?

もちろん「有限回の操作」では、絶対に隙間は残りますよ。

でも「有限回」ではなくて、「無限に」繰り返したら・・・隙間は「ほとんど」残らないんです。

実はこれ、私にとっても積年の疑問(?!)だったんです。

 >> 油滴鍋の天下統一 id:rikunora:20080513

今頃になってようやく「残りの隙間はほとんどゼロ」に納得できたので、その経緯を書いておくことにします。


もし隙間が残るのであれば、その隙間に属している点を取り出すことができるはずです。

逆に言えば、平面上のどんな点を取ってきても、その点を含んでいる円を示すことができれば、隙間は全く残っていないのだと言えるでしょう。

平面上の一点はXY座標を用いて(X=いくつ, Y=しかじか)といった2つの数字の組で表せます。

円の方を示すにはちょっと工夫が必要です。

一番大きな、6角形の配置で平面を埋め尽くしている円を「レベル1」としましょう。

レベル1の円は、XY座標と似たような感じで「何行の、何列目」といった2つの数字で表すことができます。

(この行、列の数字にはマイナスもありです。)

レベル1の円の隙間にあてはめた、次の大きさの円を「レベル2」としましょう。

レベル2の円も、レベル1の円と同様に「何行の、何列目」という2つの数字で示すことができるでしょう。

以下、3番目の大きさの円はレベル3、4番目はレベル4・・・といった感じで、全ての円をレベル付けすることができます。

なので結局、全ての円は「レベルいくつの、何行、何列目」という3つの数字で指定できるわけですね。

つまり、平面に隙間が無いことを示すには、

「(X=いくつ, Y=しかじか)という点を => レベルいくつの、何行、何列目、という数字の組に変換する方法を見つけ出せばよい」

ってなことになるでしょう。

ここでもし、どうがんばっても3つの数字に変換できないような点があったなら、それが隙間となって残る点なのだということになります。

そうではなくて、どんな点でも必ず3つの数字に変換できるのであれば、隙間は全く残らない、ということになるでしょう。


いったいどうやって、この変換ができるのでしょうか。

ここで円のままで変換を計算するのはたいへんなので、「円を三角形に変形する」というアイデアを導入しましょう。

円で平面を埋め尽くしたのと似たようなことを、今度は正三角形で考えてみます。

正三角形の、3つの辺の真ん中を線で結ぶと、中に小さな正三角形ができます。

中央の正三角形をとり除いて、残りの3つの正三角形の中に、同じようにもっと小さな正三角形を作ります。

この手順を繰り返すと、三角形の中に、小さな三角形が、どこまでも無限に続いているような図形ができます。

 >> wikipedia:シェルピンスキーのギャスケット

この三角形が無限に連なった図形と、円で平面を埋め尽くした図形を比較してみると、点と点のつながり具合、面と面のつながり具合が同じだということに気付くでしょう。

なので、円と円の隙間を三角形に変形することができれば、問題を円よりも簡単な三角形に置き換えることができるわけです。

では、3つの円に挟まれた隙間を、三角形に変形するにはどうすれば良いか。

例えばこんな考え方ではどうでしょうか。

f:id:rikunora:20081129230702p:image

三角形の1つの頂点から、対辺に向かって直線を引いたとします。

この直線が、円の隙間では図のようなカーブに移るのだと考えてみましょう。

円の隙間を埋め尽くしているカーブの束には、いろんな種類があります。

わかりやすいのは、半径を少しずつ大きくしていった円弧で隙間を埋め尽くすものでしょう。

(中央の線が対応するのは「半径無限大の円弧」ということになってしまいます。

 これだと具合が悪いので、特別ルールで中央の線は、そのまま中央の線に対応する、ということにしましょう。)

図の上で、三角形の辺上にある点Pが、パラメーターtによって1から0までの範囲で動くとき、

円弧の半径は、外側を囲んでいる円の半径rから無限大まで動くものとします。

このような対応付けによって、「三角形の中の直線 => 隙間を埋める円弧」は1対1に対応します。

三角形の中から直線を1本取り出せば、それとペアになる円弧が必ず1本だけ見つかるし、

逆に、円弧を1本取り出せば、ペアになっている直線が必ず1本だけ見つかるわけです。

ただ、これだけでは円の隙間と三角形を完全に変形したことにはなりません。

円の隙間には1レベル小さな円がはまっていて、一方、三角形の隙間には1レベル小さな三角形があります。

この小さな円と、小さな三角形がぴったり一致していないと、きれいに変形できたとは言えないでしょう。

そのためには、直線上のどの点が、円弧の上のどの点に対応するかというルールを決めなければなりません。

このルールを正確に数式で表すのは、とてもたいへんです。(私は断念しましたよ。)

ただ、直線は小さな三角形の1辺を必ず1回だけ横切るし、また、円弧は1レベル小さな円を1回だけ通過しています。

(必ず1回だけ小さな円に入って、1回だけ小さな円から出てくる。)

なので、三角形を円弧に変形するルールは必ずや存在する、ということだけは分かるでしょう。


以上で、円の隙間の問題は、三角形の隙間の問題に置き換えられることが分かりました。

改めて、いまここに三角形で埋め尽くされた平面があったとします。

平面上の一点を指定したとき、その点がどの三角形に入っているのか、言い当てる方法はあるのでしょうか。

ここでさらに問題を簡単にするために、正三角形の1つの角を広げて、直角三角形に変形しましょう。

この変形は角度を変えるだけなので、問題なく連続的に行えるでしょう。

f:id:rikunora:20081129230703p:image

ここまで来れば、平面上の1点がどの三角形に入るのか、言い当てる方法が想像できますよね。

目的の三角形を探すのは、次のような手順で行います。

簡単のため、レベル1の三角形の幅を1、高さも1とします。

平面上の点の位置を(X,Y)座標で表せば、X,Yそれぞれの整数部分が、レベル1の三角形の「行の位置、列の位置」になっています。

X,Y座標の小数点以下を、2進数に書き直します。

書き直した2進数と、三角形の位置関係は、下の図のようになっています。

f:id:rikunora:20081129230704p:image

2進数で表したとき、整数部分が「レベル1」、小数点第1位が「レベル2」、小数点第2位が「レベル3」・・・

となっているんです。

小数点以下を順にたどっていって・・・

・X,Y両方が共に(1,1)になっている桁があれば、もとの点は、そのレベルの三角形に含まれていることになります。

・(0,1)、(1,0)、(0,0)の場合は、それぞれ図のB,C,Dに相当します。

 この場合は、三角形のレベルを上げて、次の桁を見ることになります。


さて、この調子で小数点以下を調べていって、どこかに(1,1)が出現すれば、探索はそこでおしまい。

めでたく点を含んでいる三角形が見つかったことになります。

問題は、2進数表示で小数点以下が無限に続いていて、しかも、いつまでたっても(1,1)が出現しなかった場合です。

たとえば、

 X=1.010101010101010101・・・

 Y=0.101010101010101010・・・

といったとき、三角形の探索はいつまでたっても終了せず、無限ループに陥ってしまいます。

「互いに異なる値をとりつつ無限に続く二進小数の組。」

実は、こいうった点こそが「最後まで隙間に残る点」になっているんです。

だから、やっぱり隙間に残る点は存在しているわけで、隙間は完全に消えて無くなっているわけではないのです。


でも、こうして隙間に残った点は、全く孤立したバラバラな点であって、「つながっている隣の点」がありません。

もう一度、隙間に残った

 X=1.010101010101010101・・・

 Y=0.101010101010101010・・・

という点を見てください。

この無限に続く1と0の列の、どこでもいいから1カ所だけ書き換えたとしましょう。

すると、たちまちそこが(1,1)の組になりますから、どこかの三角形に入ることになります。

つまり、隙間に残った点を「ほんのちょっぴりでも動かすと」、隙間から外れてしまうのです。

 ※この部分に重大な欠陥あり。(1,0)の組を(0,0)に書き直したら?

 ※ 下のコメント参照. (2009/11/13)

 ※ 欠陥を訂正する記事を追加しました >> id:rikunora:20091119

隙間の点は、全く動かすことができない。

なので、隙間の点は「つながっていない」んです。

点と点がつながっていないので、そこに「大きさ」、「面積」を考えることができません。

これが、隙間は「ほとんど」残っていない、という「ほとんど」の意味です。


確かにバラバラな点は残っている。

それでも「大きさ」「面積」はゼロ。

ここで言う「大きさ」「面積」のことは、数学用語で「測度」と呼ばれています。

なんだか頭の痛くなりそうな話ですが、面積概念の基礎には、こんな摩訶不思議な世界があったんですね。


※ もちろん、この問題はとってもデリケートで、厳密を求めるならば、分厚い数学書を紐解かないといけません。

※ 上の例についても、こんな反論ができそうです。

※ 「(1,0)の組を、どこか1カ所ひっくり返して(0,1)にすれば、つながっている。

※  なので、隙間にある点と点は、斜め方向につながっているのだ。」

※ 確かに、ひょっとすると隙間の点は斜め方向につながっていて、隙間の「長さ」だけは考えられそうです。

※ でも「面積」はゼロってことで間違いないですね。


0000 2009/11/11 19:05 >この無限に続く1と0の列の、どこでもいいから1カ所だけ書き換えたとしましょう。
>すると、たちまちそこが(1,1)の組になりますから、

X=1.010101010101010101・・・ Y=0.101010101010101010・・・を
X=1.010101010101010101・・・ Y=0.101010101000101010・・・に書き換えても
(1,1)の組はできませんよ

rikunorarikunora 2009/11/13 11:41 その通りではないですか!
図で見ても、例えば(B)にあったものを(D)にもってきても近傍は同じ形をしています。
1と0をひっくり返しても、必ずしもどこかの三角形に含まれる訳では無いですね。
このままだとうまく説明がまとまらないので、もう少し考え直します。
ご指摘ありがとうございます。

hirotahirota 2011/04/21 17:49 円を接するように並べた時の充填率は、同じ大きさの円が正三角形配置のときが最小で、面積比を計算すると約0.9069となる。(わざわざ計算しなくても、最小値が0以上と分かれば良いんだけど)
つまり、任意の配置でも充填率は0.9より大きい。
最初の円配置から始めて、全部の隙間に対して1つづつ最大の接する円を置けば隙間面積は1/10以下になる。
その操作を繰り返せば隙間面積は0に収束する。

hirotahirota 2011/04/21 17:55 あ、いけね!
1/10以下になるってのはマチガイ。
まあ、雰囲気はそういうことで。

hirotahirota 2011/04/22 23:31 マチガイと言うのは、
円の隙間に円を詰めた時に、始めにあった外の円と内に詰めた円との間の隙間に充填率を適用すると、それは外の円の面積を含んだものになってしまうと言う事です。
始めの隙間に対する充填率を評価するには外の円との隙間は別扱いにしなければなりません。
円を詰めていくと外の円との隙間はいくらでも小さくなりますから、それを始めの隙間の40%以下になるまで詰めれば、中に詰まった円の間の隙間は10%以下ですから合計は50%以下。
つまり、この操作で隙間は半分以下になり、繰り返せば0に収束します。

rikunorarikunora 2011/04/27 13:34 返事遅くなりました。
さて、コメントで50%以下、とありますが、考え方としてはその通りだと思います。
1より小さいある定数(たとえば50%以下など)で上から押さえられることができれば、0に収束することが言えます。
問題は円を詰めてゆくとそのつど隙間の形が変わってゆくので、
「どんな形の隙間であっても確実に50%以下になる」を示すことにあると思っています。
よく考えてみれば、別に1回円を詰めただけで(1レベル上げただけで)50%以下にする必要は無かったですね。
「始めの隙間の40%以下になるまで詰めれば」で十分でした。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証