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

40年近く答えの出なかった数学の難問が解かれる 79

ストーリー by nabeshin
実用していくには 部門より

capra 曰く、

本家記事より。イスラエルのロシア系移民Avraham Trakhtman氏が40年近く解答が出なかった数学の難問に答えを出したそうです(論文PDF)。Benjamin Weiss氏とRoy Adler氏によって1970年に最初に提示されたRoad Coloring problemと呼ばれるこの問題は、与えられた有限数の道がある場合、その道を色分けにより記号化し、どこを始点にしようともある目的地点に到達できる方法があると仮定したもので、「実生活に例えるとすれば、友人の家への行き方を尋ねた時、自分がどこにいようとその友人の家に到達できる方法を教えてもらうということにあたる」ものだそうです(en.wikipedia.orgより)。今回導き出された答えは情報科学などの分野で有益に応用される可能性があるとのことです。
63歳のTrakhtman氏はこの命題への答えをたった8ページの論文にまとめ、こう述べているそうです。「答えはそんなに複雑ではない。難しいが、それほど複雑ではない。解答とは難しくなるものだと考える人もいるが、私はすっきりシンプルであるべきだと思う。」1992年に48歳でロシアからイスラエルに移民した彼は3年間ほど警備等の仕事を経て大学での職を得たそうですが、数学では20代半ばから30代にかけて活躍する人が多く、60歳を超えてこのような結果を出すのは珍しいことだそうです。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • 有向グラフ=一方通行? (スコア:2, おもしろおかしい)

    by elderwand (34630) on 2008年03月26日 19時01分 (#1319796) 日記
    有向グラフということなので、「一方通行ばかりの街でも、必ず目的地にたどりつける」定理ということでしょうか?

    「一方通行の街路はカラー舗装にしておくと意外と便利」ということかも。

  • 日本国内版:

    1.とりあえず手近なJRの駅に行け
    2.東京駅までの切符を買って列車に乗れ
    3.東京駅についたら……

    海外版:
    1.とりあえず手近な空港へ行け。
  • by gonta (11642) on 2008年03月26日 18時40分 (#1319783) 日記
    SGIの創設者、ジム・クラークが数学始めたのが30くらいで、そのまま大学教授になったのが40くらいじゃなかったかな?年とったらアウト(特に学問分野)というのが、通用しないんですね。

    日本じゃどうかな?秋山仁先生も結構年齢いってからの教授就任だと思ったが。

    3年ほど、警備員の仕事から大学に・・・自宅警備員の人たちにも望みがあるということか。
    --
    -- gonta --
    "May Macintosh be with you"
    • by float32 (22455) on 2008年03月26日 18時52分 (#1319792) 日記
      Curriculum Vitae [biu.ac.il]みると1977年から、ウラル工科大(?)って
      たぶんソ連の地方大で「assistant professor」(助教授かな?)していたのでもともと共産圏でアカデミックな人だったと思われます。

      >1969-1984 From assistant to assistant professor, Department ofComputational Mathematics, Ural Technical University.
      ってあるので、職をもったのは1969年からかな?

      ソ連崩壊でイスラエルに移住することになったユダヤ人の一人でしょう。
      移住早々でアカデミックな職位をとれずに、数年は警備員をしていただけではないかと。

      >3年ほど、警備員の仕事から大学に・・・自宅警備員の人たちにも望みがあるということか。

      この人の特殊事情ではないかと。
      親コメント
      • ウラル工科大 (スコア:2, 参考になる)

        by Anonymous Coward on 2008年03月26日 22時47分 (#1319927)
        なんか聞いたことあるな、と思いくぐってみました。
        http://ja.wikipedia.org/wiki/%E3%82%A6%E3%83%A9%E3%83%AB%E5%B7%A5%E7%A7%91%E5%A4%A7%E5%AD%A6
        エリツィンとルイシコフの母校か。
        名門校のようですね。

        親コメント
    • Re:30過ぎのリバイバル (スコア:1, すばらしい洞察)

      by Anonymous Coward on 2008年03月26日 18時49分 (#1319789)
      教授就任は活躍とは言わないでしょ、世界中に何千人と居るんだから
      歴史に残るような数学的発見は、何れも若い人達によってされてるよねって話

      とは言え、歴史に残る(昔発見された)モノの場合は、当時の平均寿命どうなのよとか
      今ならフィールズ賞(受賞は40歳までにその功績が認められた者)取った人は、その後も業績上げてるよねとか

      まぁ、研究結果と権威が関係のない分野なので、比較的若い人が注目されるという事はあるだろうね
      # 数学的な正しさに、声のデカさは関係無い。
      親コメント
      • 数学的な正しさに、声のデカさは関係無い。

        現代的な数学集合論の基礎を作ったカントールが書いた論文は、当時有力な数学雑誌の編集者をしていたクローネッカーによってことごとく没にされました。どうしてクローネッカーが編集者をしていたかというと、さまざまな業績をあげたおかげで、声がでかかったからです。採用されなかった理由は「これは数学ではない。」内容が破綻しているとかじゃないんです。クローネッカーの信じる数学のあるべき姿とカントールの出したアイデアがあまりにも違っていたせいです。仕方なくマイナーな数学雑誌に論文を投稿することに。あれやこれやあってカントール、全然出世できず、現在評価される業績と比べると、かなり不遇の人生を過ごしました。

        今の数学界はそういうことがないと信じたいなぁ。<当方数学科卒業して随分になるけど。

        --
        vyama 「バグ取れワンワン」
        親コメント
    • >秋山仁先生も結構年齢いってからの教授就任だと思ったが。

      秋山先生はポストがなかったから、就職が遅かっただけです。
      才能の開花が遅かったわけじゃない。ずっと数学をやってました。
      常勤の仕事に就くまでh、駿台予備校で数学講師などをして糊口をしのいでました。
      親コメント
    • by Anonymous Coward
      佐藤幹夫とか。
  • 任意のループの色順およびその繰り返しがユニークになる色分け方法が存在するということの証明...なのかな?
    • by s02222 (20350) on 2008年03月26日 19時29分 (#1319812)
      道路の繋がり方が以下の条件を満たしている場合、各道に上手く色を塗っておくと、「A地点に行きたいなら、交差点毎に、青、赤、赤、青、青、赤、の順に道を選べ。お前がどこに居てもAに辿り着く」と言うようなけったいなやり方のでの、全ての地点に対する経路案内をそれぞれ造れる。

      ・全ての道が一方通行
      ・全ての地点から同じ本数の道が出ている(一方通行に違反せずその場所から出て行ける道。入ってこれる道は適当)
      ・道の繋がり方がaperiodic [wikipedia.org]という性質を満たす

      ぐらいでしょうか。

      ちなみに、必要となる色数と地点から出てる道の本数は同じそうです。案内された人は迷わずに済みますね(経路案内になるのか、そういう道順があるよ、と言う存在を言っているのかだけがちらっと気になったので読んでみた)。
      親コメント
    • 私もWikipedia [wikipedia.org]をざっと見ただけですが、

      前提条件:

      • 有限な有向グラフ
      • すべての頂点について、出次数(out-degree: 頂点から出る辺の数) kが等しい
      • 強連結(どの頂点からどの頂点へも行ける)
      • 非周期的(aperiodic: グラフ中のすべての閉路について、それらの経路長の最大公約数が1)
      準備:
      • k色の「色」を選ぶ。
      • すべての頂点について、そこから出る辺k本をそれぞれ異なる色で「塗る」。塗り方は任意。
      すると、どのように塗った場合でも、すべての頂点Vに対して、以下の条件を満たす「色のパターン」W(V)がそれぞれ定義できる:
      • グラフ中のどの頂点から始めても、W(V)に従って経路を辿ると、必ずVに辿り着く。
      #確かにオートマトンへの応用が効きそうだ
      親コメント
      • by Anonymous Coward on 2008年03月27日 14時19分 (#1320385)
        > #確かにオートマトンへの応用が効きそうだ

        昔、オートマトン理論を少しかじったものですが、実はこの問題の限定された場合をタネにした手品(っぽいもの)があります。

        色分け済みのグラフ(実際は地図とか部屋の見取り図とか、親しみのもてそうな図)を観客に配って、 「あなたがどこにいても、私は自分のもとに呼び寄せることができます。」ってやるやつ。
        複数の客がみな任意に選んだ違う部屋からスタートするのに、「赤いドアの方に行ってください」「青いドアの方に」って指示された通りに動くと、最後には全員が同じ部屋にたどりつくのを見せられると、けっこう「おおぉーっ」って反応が得られますよ。

        最近、似たようなネタを Mr. マリックがやってたけど、これはグラフが殆どスター状になっててよく見てみると仕掛けが読み取れちゃうやつでした。

        この問題の面白さは、ゴール地点を変えても任意の頂点からそこへたどりつく色順が存在することなんで、グラフの形をじっと眺めてもなかなか仕掛けは読み取れない。「今度は、私の居場所を変えてみますよ。それでも呼び寄せられます。」ってもう一度やってみせると、さらにインパクトありです。
        さらにこれは自分の居場所だけで経路が決まるので、客の居場所の初期値を見ないで誘導してみせると迫力あるかも。

        親コメント
      • あ、ウソでした orz

        「どのように塗った場合でも」じゃないです。「以下の性質を満たす塗り方が存在する」ですね。

        親コメント
      • by Anonymous Coward
        > すべての頂点について、出次数(out-degree: 頂点から出る辺の数) kが等しい
        は何かダミーの枝みたいなので何とかなるかもしれないけど、

        > 非周期的(aperiodic: グラフ中のすべての閉路について、それらの経路長の最大公約数が1)
        を満たせるような実用的な応用ってあるような気がしない。
      • by Anonymous Coward
        オイラーグラフの応用みたいな感じか?
        前提部がオイラー路で準備部がグラフ彩色

        #思いついただけで、確認もとってないのでAC
  • by Anonymous Coward on 2008年03月26日 19時48分 (#1319822)
    大学の研究では巡回セールスマンをニューラルネットとカオスで解くってのを
    やってたけど、実は何も分からないまま卒業した俺には内容が理解できません!

    だれかわかりやすいページ plz
  • 「きっとくるー、きっとくるー」
    貞子は君のところに到着し得ることが数学的に証明された、ということだよ。

    # ただし、貞子が迷子にならない証明は、まだない。
    --
    fjの教祖様
  • by Anonymous Coward on 2008年03月26日 19時36分 (#1319815)
    私の人生で望む目標に今からでもたどり着けるのかを
typodupeerror

人生の大半の問題はスルー力で解決する -- スルー力研究専門家

読み込み中...