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, おもしろおかしい)
「一方通行の街路はカラー舗装にしておくと意外と便利」ということかも。
Re:有向グラフ=一方通行? (スコア:1)
友人の家への行き方を尋ねた時、自分がどこにいようとその友人の家に到達できる方法 (スコア:1, おもしろおかしい)
1.とりあえず手近なJRの駅に行け
2.東京駅までの切符を買って列車に乗れ
3.東京駅についたら……
海外版:
1.とりあえず手近な空港へ行け。
Re:友人の家への行き方を尋ねた時、自分がどこにいようとその友人の家に到達できる方法 (スコア:5, おもしろおかしい)
・埼玉県の地図を持ち歩く
Re: (スコア:0)
Re: (スコア:0)
・大西洋を泳いで渡る [gigazine.net]
Re:友人の家への行き方を尋ねた時、自分がどこにいようとその友人の家に到達できる方法 (スコア:1, おもしろおかしい)
と
とりあえず手近な空港への行き方を尋ねた時、自分がどこにいようととりあえず手近な空港に到達できる方法
もお願いします。
Re:友人の家への行き方を尋ねた時、自分がどこにいようとその友人の家に到達できる方法 (スコア:2, すばらしい洞察)
Re:友人の家への行き方を尋ねた時、自分がどこにいようとその友人の家に到達できる方法 (スコア:1)
タクシーへの乗り方を尋ねた時、自分がどこにいようとそのタクシーが到達できる方法
は、どうしましょう。
# 部屋の中まで乗り入れてもらっても困るしな。
Re:友人の家への行き方を尋ねた時、自分がどこにいようとその友人の家に到達できる方法 (スコア:1, おもしろおかしい)
Re:友人の家への行き方を尋ねた時、自分がどこにいようとその友人の家に到達できる方法 (スコア:1)
「私の家は日本橋だからどこで迷子になっても
帰ってくることができる!」
って豪語してたな。
Re:友人の家への行き方を尋ねた時、自分がどこにいようとその友人の家に到達できる方法 (スコア:1)
女の子なら一言、
「お兄ちゃん! 道に迷っちゃったの!」
って叫べばよろしい。
そうすりゃ大勢の自称お兄ちゃん達が一斉に振り返って・・・次の瞬間には何事も無かったかのように去っていく。
#困ってる人を助けたいとは思うけど、声掛けるだけで犯罪者にされちゃう [livedoor.jp]世の中だから下手に関われないんよねぇ・・・。
Re: (スコア:0)
Re: (スコア:0)
もしかして:拉致 (スコア:2, おもしろおかしい)
30過ぎのリバイバル (スコア:1)
日本じゃどうかな?秋山仁先生も結構年齢いってからの教授就任だと思ったが。
3年ほど、警備員の仕事から大学に・・・自宅警備員の人たちにも望みがあるということか。
-- gonta --
"May Macintosh be with you"
Re:30過ぎのリバイバル (スコア:3, 参考になる)
たぶんソ連の地方大で「assistant professor」(助教授かな?)していたのでもともと共産圏でアカデミックな人だったと思われます。
>1969-1984 From assistant to assistant professor, Department ofComputational Mathematics, Ural Technical University.
ってあるので、職をもったのは1969年からかな?
ソ連崩壊でイスラエルに移住することになったユダヤ人の一人でしょう。
移住早々でアカデミックな職位をとれずに、数年は警備員をしていただけではないかと。
>3年ほど、警備員の仕事から大学に・・・自宅警備員の人たちにも望みがあるということか。
この人の特殊事情ではないかと。
ウラル工科大 (スコア:2, 参考になる)
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, すばらしい洞察)
歴史に残るような数学的発見は、何れも若い人達によってされてるよねって話
とは言え、歴史に残る(昔発見された)モノの場合は、当時の平均寿命どうなのよとか
今ならフィールズ賞(受賞は40歳までにその功績が認められた者)取った人は、その後も業績上げてるよねとか
まぁ、研究結果と権威が関係のない分野なので、比較的若い人が注目されるという事はあるだろうね
# 数学的な正しさに、声のデカさは関係無い。
数学界にも政治はある (スコア:1)
現代的な数学集合論の基礎を作ったカントールが書いた論文は、当時有力な数学雑誌の編集者をしていたクローネッカーによってことごとく没にされました。どうしてクローネッカーが編集者をしていたかというと、さまざまな業績をあげたおかげで、声がでかかったからです。採用されなかった理由は「これは数学ではない。」内容が破綻しているとかじゃないんです。クローネッカーの信じる数学のあるべき姿とカントールの出したアイデアがあまりにも違っていたせいです。仕方なくマイナーな数学雑誌に論文を投稿することに。あれやこれやあってカントール、全然出世できず、現在評価される業績と比べると、かなり不遇の人生を過ごしました。
今の数学界はそういうことがないと信じたいなぁ。<当方数学科卒業して随分になるけど。
vyama 「バグ取れワンワン」
Re:30過ぎのリバイバル (スコア:1)
秋山先生はポストがなかったから、就職が遅かっただけです。
才能の開花が遅かったわけじゃない。ずっと数学をやってました。
常勤の仕事に就くまでh、駿台予備校で数学講師などをして糊口をしのいでました。
Re: (スコア:0)
Re:100mを10秒を切るタイムで走れますか? (スコア:1)
2、それを丸めて下におく。
3、紐をまたぐ。
(ワープ方式)
the.ACount
wikioediaの解説をざっと見たところでは (スコア:1)
Re:wikioediaの解説をざっと見たところでは (スコア:3, 参考になる)
・全ての道が一方通行
・全ての地点から同じ本数の道が出ている(一方通行に違反せずその場所から出て行ける道。入ってこれる道は適当)
・道の繋がり方がaperiodic [wikipedia.org]という性質を満たす
ぐらいでしょうか。
ちなみに、必要となる色数と地点から出てる道の本数は同じそうです。案内された人は迷わずに済みますね(経路案内になるのか、そういう道順があるよ、と言う存在を言っているのかだけがちらっと気になったので読んでみた)。
Re:wikipediaの解説をざっと見たところでは (スコア:1)
# 論理を追わずに言ってるので違うかも知らんけど。
Re:wikipediaの解説をざっと見たところでは (スコア:1)
あ、すみません。同じくよく読まず書きました。 既に解釈ツリーがあったのでツリーを増やさず便乗しようかと思っただけです。
Re:wikipediaの解説をざっと見たところでは (スコア:1)
そうかもしれないけど、私にはs02222氏のコメントがないと意味が分かりませんでしたのでs02222氏のコメントには大いに意味があると思います。
論理回路のリセットシーケンスの話に似ていると思いました(この話だと任意のステートにリセットできるような雰囲気)。
Best regards, でぃーすけ
Re:wikioediaの解説をざっと見たところでは (スコア:1, おもしろおかしい)
Re: (スコア:0)
#数学的ではないのでAC
Re:wikioediaの解説をざっと見たところでは (スコア:2, おもしろおかしい)
Re:wikioediaの解説をざっと見たところでは (スコア:2, 興味深い)
前提条件:
Re:wikioediaの解説をざっと見たところでは (スコア:2, 興味深い)
昔、オートマトン理論を少しかじったものですが、実はこの問題の限定された場合をタネにした手品(っぽいもの)があります。
色分け済みのグラフ(実際は地図とか部屋の見取り図とか、親しみのもてそうな図)を観客に配って、 「あなたがどこにいても、私は自分のもとに呼び寄せることができます。」ってやるやつ。
複数の客がみな任意に選んだ違う部屋からスタートするのに、「赤いドアの方に行ってください」「青いドアの方に」って指示された通りに動くと、最後には全員が同じ部屋にたどりつくのを見せられると、けっこう「おおぉーっ」って反応が得られますよ。
最近、似たようなネタを Mr. マリックがやってたけど、これはグラフが殆どスター状になっててよく見てみると仕掛けが読み取れちゃうやつでした。
この問題の面白さは、ゴール地点を変えても任意の頂点からそこへたどりつく色順が存在することなんで、グラフの形をじっと眺めてもなかなか仕掛けは読み取れない。「今度は、私の居場所を変えてみますよ。それでも呼び寄せられます。」ってもう一度やってみせると、さらにインパクトありです。
さらにこれは自分の居場所だけで経路が決まるので、客の居場所の初期値を見ないで誘導してみせると迫力あるかも。
Re:wikioediaの解説をざっと見たところでは (スコア:1)
「どのように塗った場合でも」じゃないです。「以下の性質を満たす塗り方が存在する」ですね。
Re: (スコア:0)
は何かダミーの枝みたいなので何とかなるかもしれないけど、
> 非周期的(aperiodic: グラフ中のすべての閉路について、それらの経路長の最大公約数が1)
を満たせるような実用的な応用ってあるような気がしない。
Re: (スコア:0)
前提部がオイラー路で準備部がグラフ彩色
#思いついただけで、確認もとってないのでAC
巡回セールスマンやってたけど (スコア:1, おもしろおかしい)
やってたけど、実は何も分からないまま卒業した俺には内容が理解できません!
だれかわかりやすいページ plz
ようするにだな… (スコア:1)
貞子は君のところに到着し得ることが数学的に証明された、ということだよ。
# ただし、貞子が迷子にならない証明は、まだない。
fjの教祖様
この先生に聞きたい (スコア:0)
ご期待ください(Re:この先生に聞きたい (スコア:0)
Re:ご期待ください(Re:この先生に聞きたい (スコア:2, すばらしい洞察)
Re: (スコア:0)
実際にその道をたどって目的地にたどり着ける
かどうかという問題は別のものでしょ(´・ω・`)
Re:すいません (スコア:2, おもしろおかしい)
Re:すいません (スコア:1, すばらしい洞察)
面白いと思って書いてるなら、一日経ってから読み返すといい。
Re: (スコア:0, 荒らし)
匿名の方がとか、低スコアから始めた方がとか言う妙な美意識はどっからくるんだろうね。
妖精哲学の三信
「だらしねぇ」という戒めの心、「歪みねぇ」という賛美の心、「仕方ない」という許容の心
Re: (スコア:0)
Re: (スコア:0)
よって今日もACだ。ID投稿でも0スタートできるならそうしてる。
カルマボーナスを使わないのが1スタートで、使って2スタートってのが、どう考えても変。やるなら、使わず0スタート使って1スタートだろうに。
Re:すいません (スコア:2, 参考になる)
Wikipedia [wikipedia.org]でもこういってますよ。
つまり、あなたは数論と初等教育における現状を語っていますが、それ以外のところでは別の感覚(定義が自然かどうか)があっていいわけです。
Re:すいません (スコア:2, 興味深い)
集合論で0を自然数に含める理由は「(有限)集合の要素数となり得る数」だから(空集合の要素数は0)。
数論で0を自然数に含めない理由は「素因数分解を持たない数」だから(素数をいくつ掛けても0にはならない)。
どちらも、その分野で主な興味の対象となる性質を備えているかいないかで0を自然数に含めるかどうかの切り分けを行っていて、その意味ではどちらの流儀も「自然」と言えるのだと思います。
ちなみに私も数学者ですが、0の扱いについて論文の冒頭に毎回注意書きを書くのが面倒なので、読者がどんな人かわからない自分の論文では「自然数」という言葉は使わず、0を含めない場合は「正の整数 (positive integer)」、0を含める場合は「非負整数 (nonnegative integer)」と書くようにしています。
#私自身は「0を自然数に含めるべきか否か」について確固たる信念を持っているわけではありませんので。
もっとも、相手の素性がわかる口頭での議論の際にはその限りではありませんが。
Re: (スコア:0, オフトピック)
オフトピックなコメントはたいてい面白くない。
軽くタレコミを読んで(中にはタイトルしか読まない奴もいる)、5秒で思いついたことを書いてたらキリがないわけで。
例えば、ある者は空目したことを書き込み、ある者は2chで流行ったAAを思いついて書き込み、ある者は単語に反応して書き込む……。生まれるのはスコア1〜-1のコメントの山。
だれしも数行のつまらないたわごとじゃなくて、興味深くて参考になるコメントを読みたいと思ってるんだから、
せめてオフトピックなコメントを投稿するときは、数時間後に読み返しても"最高に機知に溢れてるぜ!"と思うものにしようよ。