パスワードを忘れた? アカウント作成
12351367 story
数学

15番目の平面充填五角形が発見される 29

ストーリー by headless
発見 部門より
15番目の平面充填五角形が、米ワシントン大学ボセル校の数学者らにより発見された(redditのスレッドForbesの記事xkcdのスレッド)。

数学者らは、すべての平面充填五角形を特定できるというアルゴリズムを開発し、コンピュータープログラムに実装。このプログラムのデバッグおよび最適化を実行中に15番目の平面充填五角形が発見されたとのこと。論文は準備中のようだ。

vlue 曰く、

リンク先で図形を確認できるが、中々変な形をしている。14番目が発見されたのは1985年であり、30年ぶりの快挙となる。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • by albireo (7374) on 2015年08月08日 15時43分 (#2861026) 日記

    リンクが複数あってちょっと探してしまったので、ものぐささんのために図形への直リン置いときますね。
    各辺の長さや並べ方など基本的な情報はこれでわかります(PNG) [imgur.com]

    --
    うじゃうじゃ
  • 「いつまでデバッグに手間取っているんだ!」 「この作業がだいじなんですよ!!」
  • by Anonymous Coward on 2015年08月08日 19時24分 (#2861102)

    全くぴったりこの形のみ、ってわけではないんだね。
    タレコミで14番目 [mathpuzzle.com]としてリンクされてるページを見て、


    をくっつけた、一番すぐに思いつく平面充填五角形が無いぞ? とちょっと考えたんだけど、
    これは、「Type 1」と書かれている、角D+角Eが180度になる種類の、D=E=90度な特殊バージョンという事か。

    一見、そうは見えない形に歪めて図示されているのは、上記の家形(?)に限る、という先入観を与えないため、
    色つきの図とその下のそれぞれのTypeの特性説明の図でまた形が食い違っているのも分かりにくいけど、
    これも、具体的な形には変形の余地がある、と示すため敢えて?

    辺の長さの比率も自由に弄ることが出来る余地があるし。

    「15番目」という種類の別は、「五角形ABCDEがあり(五角形0と呼ぶとする)、nこの隣接五角形1~nとすると、
    0の辺ABは、隣接1のBCと、隣接2のCDと接しており…」というような形で定義されるのかな?
    だとすると、それを取っかかりに列挙するアルゴリズムを書けそうな気もするけど、ちゃんと作らないと発散しそうだなぁ。

  • まだ実装か実行が完了してないのか、それとも、もう網羅したのか気になります。
    15個しかないと証明されちゃったわけではないということなら
    そのプログラムが完成動作したらどんどん見つかるんですかね。
    それとも、無限に実行時間がかかるようなアルゴリズムなのでしょうか。

    • by Anonymous Coward on 2015年08月08日 23時30分 (#2861215)

      発表のアブストラクトには「an automated approach to finding all pentagons that admit i-block transitive tilings」と書いてあるので、とりあえずi=3で試してみたらさっそく1つ新しいのが見つかったよ、ってことなんじゃないかな。

      親コメント
    • 今回の図形は波型の集合が周期で、それ自体は3個の集合の周期で構成されているように見えます。 周期を大きくすれば、もっとパターンがありそうですが、平面充填五角形が有限であることの証明もしくは反証はされてるのか私は知りません。
      親コメント
    • by Anonymous Coward

      無限に実行時間がかかるなら定義上アルゴリズムではありえないと思いますが。アルゴリズムとは必ず停止することが保証された手続きです。

      • by Anonymous Coward

        じゃあ、円周率を計算するロジックはアルゴリズムじゃなくてなんて言うんですかね

        • ソースは 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が無限大のときに「停止しないかもしれない」
          アルゴリズムは存在し得るでしょう。

          親コメント
          • by Anonymous Coward

            > アルゴリズムは最終的に必ず停止しなければならないとする定義もある。

            そのwikipediaさんに「も」って書いてあるじゃねーか。

            • by Anonymous Coward

              それこそ[要出典]以外の何物でもない。

          • by Anonymous Coward

            > nが無限大のときに

            チューリングマシンの空でない入力テープは有限でなければならないから、無限大というのは有効な入力ではないよ。無限に使う可能性があるのはあくまでも作業領域。無限の長さの入力テープが許されるなら、その計算能力は神託機械と同値になる(無限の入力を神託として使える)。

          • by Anonymous Coward

            > (計算量の上界を n に対して定義できるっていえばご満足かしら?)

            それを言わなければ満足できたんだけど。再帰的だが原始再帰的でない関数の出力を計算するアルゴリズムは存在する(必ず有限時間で停止する手続きを書ける)が、具体的にいつ停止するか予想することはできない(計算量の上界が存在しない)。
            証明を一言でいうと、もし予想ができたら、それをもとに停止問題が解けてしまう。

            • by Anonymous Coward

              いや上界は定義できる。計算不可能なだけで。計算量の上界はBB(n)以下だが、BB(n)は計算不可能というだけ。

        • by Anonymous Coward

          「計算可枚挙」の定義に出てくるSの元を枚挙する手続きのことを何て呼ぶのかも知りたい。ていうかウィキペの定義 [wikipedia.org]では

          ・あるアルゴリズムに入力となる数を与えたとき、そのアルゴリズムが停止する必要十分条件が、その数が S の元であることである。
          あるいは、これと同値だが、
          ・S の元を枚挙するアルゴリズムが存在する。つまり、その出力は S の元のリスト s1, s2, s3, ... である。このアルゴリズムは必要ならば無限に動作する。

          って思いっきり書かれてるじゃねーか(どっちの定義も「アルゴリズム」が停止しない可能性があることを前提にしている)。

  • by Anonymous Coward on 2015年08月10日 6時55分 (#2861632)

    > My wife just informed me that her best friends parents just discovered ...

    そっから先を読む気が失せる。

typodupeerror

弘法筆を選ばず、アレゲはキーボードを選ぶ -- アレゲ研究家

読み込み中...