15番目の平面充填五角形が発見される 29
ストーリー by headless
発見 部門より
発見 部門より
15番目の平面充填五角形が、米ワシントン大学ボセル校の数学者らにより発見された(redditのスレッド、
Forbesの記事、
xkcdのスレッド)。
数学者らは、すべての平面充填五角形を特定できるというアルゴリズムを開発し、コンピュータープログラムに実装。このプログラムのデバッグおよび最適化を実行中に15番目の平面充填五角形が発見されたとのこと。論文は準備中のようだ。
vlue 曰く、
数学者らは、すべての平面充填五角形を特定できるというアルゴリズムを開発し、コンピュータープログラムに実装。このプログラムのデバッグおよび最適化を実行中に15番目の平面充填五角形が発見されたとのこと。論文は準備中のようだ。
vlue 曰く、
リンク先で図形を確認できるが、中々変な形をしている。14番目が発見されたのは1985年であり、30年ぶりの快挙となる。
反転はありなのね (スコア:5, 参考になる)
リンクが複数あってちょっと探してしまったので、ものぐささんのために図形への直リン置いときますね。
各辺の長さや並べ方など基本的な情報はこれでわかります(PNG) [imgur.com]
うじゃうじゃ
Re: (スコア:0)
Re: (スコア:0)
洗われた米のようだ
Re: (スコア:0)
https://en.wikipedia.org/wiki/Pentagon_tiling [wikipedia.org]
にのってる画像がこれまでにみつかったやつなのかな
ありがちな会話 (スコア:3)
それぞれの種類に変形の余地 (スコア:3, 参考になる)
全くぴったりこの形のみ、ってわけではないんだね。
タレコミで14番目 [mathpuzzle.com]としてリンクされてるページを見て、
▲
■
をくっつけた、一番すぐに思いつく平面充填五角形が無いぞ? とちょっと考えたんだけど、
これは、「Type 1」と書かれている、角D+角Eが180度になる種類の、D=E=90度な特殊バージョンという事か。
一見、そうは見えない形に歪めて図示されているのは、上記の家形(?)に限る、という先入観を与えないため、
色つきの図とその下のそれぞれのTypeの特性説明の図でまた形が食い違っているのも分かりにくいけど、
これも、具体的な形には変形の余地がある、と示すため敢えて?
辺の長さの比率も自由に弄ることが出来る余地があるし。
「15番目」という種類の別は、「五角形ABCDEがあり(五角形0と呼ぶとする)、nこの隣接五角形1～nとすると、
0の辺ABは、隣接1のBCと、隣接2のCDと接しており…」というような形で定義されるのかな?
だとすると、それを取っかかりに列挙するアルゴリズムを書けそうな気もするけど、ちゃんと作らないと発散しそうだなぁ。
Re:それぞれの種類に変形の余地 (スコア:1)
あーオレも一番に思いついて何故無いんかと疑問だったが、そういうことね。
the.ACount
すべての平面充填五角形を特定できるというアルゴリズム (スコア:2)
まだ実装か実行が完了してないのか、それとも、もう網羅したのか気になります。
１５個しかないと証明されちゃったわけではないということなら
そのプログラムが完成動作したらどんどん見つかるんですかね。
それとも、無限に実行時間がかかるようなアルゴリズムなのでしょうか。
Re:すべての平面充填五角形を特定できるというアルゴリズム (スコア:2, 興味深い)
発表のアブストラクトには「an automated approach to finding all pentagons that admit i-block transitive tilings」と書いてあるので、とりあえずi=3で試してみたらさっそく1つ新しいのが見つかったよ、ってことなんじゃないかな。
Re:すべての平面充填五角形を特定できるというアルゴリズム (スコア:1)
Re: (スコア:0)
無限に実行時間がかかるなら定義上アルゴリズムではありえないと思いますが。アルゴリズムとは必ず停止することが保証された手続きです。
Re: (スコア:0)
じゃあ、円周率を計算するロジックはアルゴリズムじゃなくてなんて言うんですかね
Re:すべての平面充填五角形を特定できるというアルゴリズム (スコア:1)
ソースは Wikipedia(笑)
https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%... [wikipedia.org]
だけれども、クヌースに従うなら「computational method」らしい。
(さて、ここでアルゴリズムが停止するかどうかを判定しなければならないのだが、判定する前にはアルゴリズムとは呼べないという問題が...)
円周率の計算を n桁目で止めるなら手続きが停止する、とか、"i-block transitive tilings" の列挙(i = 2, 3, ...)を
n で止めれば停止するとか、そういう条件があればアルゴリズムですよね。
(計算量の上界を n に対して定義できるっていえばご満足かしら?)
平面充填五角形が有限個であることが証明されていないのなら、nが無限大のときに「停止しないかもしれない」
アルゴリズムは存在し得るでしょう。
Re: (スコア:0)
> アルゴリズムは最終的に必ず停止しなければならないとする定義もある。
そのwikipediaさんに「も」って書いてあるじゃねーか。
Re: (スコア:0)
それこそ[要出典]以外の何物でもない。
Re: (スコア:0)
> nが無限大のときに
チューリングマシンの空でない入力テープは有限でなければならないから、無限大というのは有効な入力ではないよ。無限に使う可能性があるのはあくまでも作業領域。無限の長さの入力テープが許されるなら、その計算能力は神託機械と同値になる(無限の入力を神託として使える)。
Re:すべての平面充填五角形を特定できるというアルゴリズム (スコア:1)
＞神託機械
Exadataが頭によぎるのでホントあの会社やめて欲しい。
Re: (スコア:0)
> (計算量の上界を n に対して定義できるっていえばご満足かしら?)
それを言わなければ満足できたんだけど。再帰的だが原始再帰的でない関数の出力を計算するアルゴリズムは存在する(必ず有限時間で停止する手続きを書ける)が、具体的にいつ停止するか予想することはできない(計算量の上界が存在しない)。
証明を一言でいうと、もし予想ができたら、それをもとに停止問題が解けてしまう。
Re: (スコア:0)
いや上界は定義できる。計算不可能なだけで。計算量の上界はBB(n)以下だが、BB(n)は計算不可能というだけ。
Re: (スコア:0)
「計算可枚挙」の定義に出てくるSの元を枚挙する手続きのことを何て呼ぶのかも知りたい。ていうかウィキペの定義 [wikipedia.org]では
って思いっきり書かれてるじゃねーか(どっちの定義も「アルゴリズム」が停止しない可能性があることを前提にしている)。
最初のリンク怪しさ抜群 (スコア:0)
> My wife just informed me that her best friends parents just discovered ...
そっから先を読む気が失せる。
Re:あーこれね (スコア:1)
ネタで落ちず、スコアが落ちるとは、これいかに。
Re:たかが15番目で自慢しなさんな (スコア:1)
ダウト。
君の言っている無限個は、#2861102の定義でいうところの変形の余地に
すべて含まれる。
多分、君の思いついたのは、2種類だけなんじゃないかな。
Re: (スコア:0)
ただの台形だろヴオケ
Re: (スコア:0)
平面充填四角形をもれなく列挙できたら認めてやろう。
Re: (スコア:0)
無限をもれなくだと！？
スラドをぶっ壊すつもりか？
Re: (スコア:0)
チャックノリス呼んでくる。