歡迎來到 財團法人台北市九章數學教育基金會
首頁 新聞區 討論區 檔案下載
重要公告

2018 澳洲AMC數學能力檢定


2018年國際中小學數學能力檢測(IMAS)


第21屆小學數學世界邀請賽(PMWC 2018,香港)與2018國際小學數學競賽(BIMC 2018,保加利亞Burgas市)


2018青少年數學國際城市邀請賽(BIMC 2018,保加利亞Burgas市))

歷史公告

澳洲AMC數學能力檢定

2017 澳洲AMC

2016 澳洲AMC


國際中小學數學能力檢測(IMAS)

IMAS 2017

IMAS 2016


小學數學競賽

小學數學世界邀請賽與國際小學數學競賽

PMWC 2018與BIMC 2018

PMWC 2017與InIMC 2017

國際小學數學及自然科學奧林匹亞(IMSO)

IMSO 2018

IMSO 2017


中學數學競賽

青少年數學國際城市邀請賽

BIMC 2018

InIMC 2017

國際青少年數學奧林匹亞(ITMO )

ITMO 2017

ITMO 2015

國際青少年數學家會議(IYMC )

IYMC 2016


欲查詢其餘歷史公告,可利用首頁右側之關鍵字搜尋功能
目前並未有最新新聞!
主選單
· 回首頁
· 新聞區
· 討論區
· 檔案下載
· 網站連結
· 電子相薄
· 夥伴網站
· 精華文章
/  討論區主頁10
   /  讀書討論區
      /  "Road Coloring Problem." 道路著色謎題 以色列數學家破解(轉貼)
限會員
發布者內容列
tpesamguo
Quite a regular



註冊日: 2005-09-03
發表數: 48


 "Road Coloring Problem." 道路著色謎題 以色列數學家破解(轉貼)

〔編譯胡立宗/美聯社耶路撒冷二十日電〕「道路著色問題」(Road Coloring Problem)一九七○年代提出,此後近四十年,釵h數學家都試著找出解答,但都無它茠臐C一位「高齡」六十三歲的以色列數學家卻在去年底得出解答,儘管釵h人訝異於他的成就,但他自己仍然低調表示,這只是個「數學家的本務」。

近40年來 大熱門數學謎題

道路著色問題是由班雅明.懷斯及羅伊.阿德勒提出,原意是找出地圖指引及電腦自動除錯程式的設計方式,但沒想到不但懷斯自己花了八年都無法解答,接下來三十年間一百多位數學家也束手無策。

這個難題的假設是,在出發點(圓點)及道路(直線)的數量都固定的情況下,應該有辦法以不同顏色標示道路,讓人不管從哪一個點出發,都能到達固定的點。這在真實生活中的情況就像是,不管朋友住在哪裡,只要知道你家的位置,繞再遠都有辦法到你家。

以圖為範本(見下圖,取自維基百科),如果按照「藍—紅—紅、藍—紅—紅、藍—紅—紅」的方式行走,不管從哪個點出發都能到黃色的點;如果是「藍—藍—紅、藍—藍—紅、藍—藍—紅」,則一定能到綠點

自蘇聯返以 一度屈就守衛

這個看似簡單的問題,最後碰到阿夫拉罕.塔克特曼(見上圖,取自網路)才被解開。塔克特曼原居蘇聯,當時就已經是個小有名氣的數學家。蘇聯瓦解後,他回歸以色列,卻因工作難找只好當個守衛,幾經波折才重拾教鞭,於一九九五年到巴伊蘭大學任教。

塔克特曼說,他花了一年才想通問題,去年拿著鉛筆塗寫八頁才寫完解答;結論在去年年底獲得確認後,終於證明他的成就。但塔克特曼說他是完成了數學家該做的事,很幸運能被認可,他不會因此而被沖昏頭。

(圖形請點下面wiki維基百科就可以看到道路走法)

http://www.libertytimes.com.tw/2008/new/mar/22/today-int3.htm


道路著色謎題圖形請參照取自維基百科點選(英文全文):
In graph theory the road coloring theorem, until recently known as the road coloring conjecture, deals with synchronized instructions. The issue involves whether by using such instructions, one can reach or locate an object or destination from any other point within a network (which might be a representation of city streets or a maze).[1] In the real world, this phenomenon would be as if you called a friend to ask for directions to his house, and he gave you a set of directions that worked no matter where you started from. This theorem also has implications in symbolic dynamics.

The theorem was first conjectured in 1970 by Benjamin Weiss and Roy Adler.[2] It was proved by Avraham Trahtman in September 2007[3].

Example and intuition

The image to the right shows a directed graph on eight vertices in which each vertex has out-degree 2. (Each vertex in this case also has in-degree 2, but that is not necessary for a synchronizing coloring to exist.) The edges of this graph have been colored red and blue to create a synchronizing coloring.

For example, consider the vertex marked in yellow. No matter where in the graph you start, if you traverse all nine edges in the walk "blue-red-red—blue-red-red—blue-red-red", you will end up at the yellow vertex. Similarly, if you traverse all nine edges in the walk "blue-blue-red—blue-blue-red—blue-blue-red", you will always end up at the vertex marked in green, no matter where you started.

The road coloring theorem states that for a certain category of directed graphs, it is always possible to create such a coloring.


http://en.wikipedia.org/wiki/Road_coloring_problem



After 38 years, Israeli solves math code[Road Coloring Problem]


JERUSALEM - A mathematical puzzle that baffled the top minds in the esoteric field of symbolic dynamics for nearly four decades has been cracked — by a 63-year-old immigrant who once had to work as a security guard.

Avraham Trahtman, a mathematician who also toiled as a laborer after moving to Israel from Russia, succeeded where dozens failed, solving the elusive "Road Coloring Problem."

The conjecture essentially assumed it's possible to create a "universal map" that can direct people to arrive at a certain destination, at the same time, regardless of starting point. Experts say the proposition could have real-life applications in mapping and computer science.

The "Road Coloring Problem" was first posed in 1970 by Benjamin Weiss, an Israeli-American mathematician, and a colleague, Roy Adler, who worked at IBM at the time.

For eight years, Weiss tried to prove his theory. Over the next 30 years, some 100 other scientists attempted as well. All failed, until Trahtman came along and, in eight short pages, jotted the solution down in pencil last year.

"The solution is not that complicated. It's hard, but it is not that complicated," Trahtman said in heavily accented Hebrew. "Some people think they need to be complicated. I think they need to be nice and simple."

Weiss said it gave him great joy to see someone solve his problem.

Stuart Margolis, a mathematician who recruited Trahtman to teach at Bar Ilan University near Tel Aviv, called the solution one of the "beautiful results." But he said what makes the result especially remarkable is Trahtman's age and background.

"Math is usually a younger person's game, like music and the arts," Margolis said. "Usually you do your better work in your mid 20s and early 30s. He certainly came up with a good one at age 63."

Adding to the excitement is Trahtman's personal triumph in finally finding work as a mathematician after immigrating from Russia. "The first time I met him he was wearing a night watchman's uniform," Margolis said.

Originally from Yekaterinburg, Russia, Trahtman was an accomplished mathematician when he came to Israel in 1992, at age 48. But like many immigrants in the wave that followed the breakup of the Soviet Union, he struggled to find work in the Jewish state and was forced into stints working maintenance and security before landing a teaching position at Bar Ilan in 1995.

The soft-spoken Trahtman declined to talk about his odyssey, calling that the "old days." He said he felt "lucky" to be recognized for his solution, and played down the achievement as a "matter for mathematicians," saying it hasn't changed him a bit.

The puzzle tackled by Trahtman wasn't the longest-standing open problem to be solved recently. In 1994, British mathematician Andrew Wiles solved Fermat's last theorem, which had been open for more than 300 years.

Trahtman's solution is available on the Internet and is to be published soon in the Israel Journal of Mathematics.

Joel Friedman, a math professor at the University of British Columbia, said probably everyone in the field of symbolic dynamics had tried to solve the problem at some point, including himself. He said people in the related disciplines of graph theory, discrete math and theoretical computer science also tried.

"The solution to this problem has definitely generated excitement in the mathematical community," he said in an e-mail.

Margolis said the solution could have many applications.

"Say you've lost an e-mail and you want to get it back — it would be guaranteed," he said. "Let's say you are lost in a town you have never been in before and you have to get to a friend's house and there are no street signs — the directions will work no matter what."

http://freerepublic.com/focus/f-news/1989209/posts


 2008-03-22 09:36個人資料
孫文先
Moderator



註冊日: 2002-07-30
發表數: 1094


 Re: "Road Coloring Problem." 道路著色謎題 以色列數學家破解(轉貼)

我認為附圖有錯


_________________
孫文先 敬上

 2008-03-23 11:33個人資料傳送 Email 給 孫文先
tpesamguo
Quite a regular



註冊日: 2005-09-03
發表數: 48


 Re: "Road Coloring Problem." 道路著色謎題 以色列數學家破解(轉貼)

引文:

孫文先 寫道:
我認為附圖有錯




孫老師,

我仔細走過一遍,沒錯啊! 老師可以說說您的走法嗎?

這走法是說:
如果您隨便選一個點,照著"藍-紅-紅"箭頭走法,無論哪一個點走都可以到達"黃色點".

如果您隨便選一個點,照著"藍-藍-紅"箭頭走法,無論哪一個點走都可以到達"綠色點".

所以圖形應該沒錯啊! 老師,可否指點我們您的看法呢?

下面四個是談到四色圖法及有關UPS走對送貨路線是可以節省成本,這在九章數學俱樂部及我自己看過一些數學邏輯書籍都有提過Bivariate Splines and the Four Color Map Problem走法,可提供給大家想一想:


“UPS Figures Out the ‘Right Way’ to Save Money, Time and Gas”
http://abcnews.go.com/print?id=3005890

It’s quite an interesting theorem / problem. Here are few brief descriptions, with some original info in each one:

http://www.math.gatech.edu/~thomas/FC/fourcolor.html

http://mathworld.wolfram.com/Four-ColorTheorem.html

And the one that likely crosses the bridge from Four Color Map Problem to Road Coloring Problem - Multivariate Splines:

http://www.math.utah.edu/~pa/talks/S13/4CMP.html

Wikipedia also has a decent description of theorem and practical implications for topography and topology:

http://en.wikipedia.org/wiki/Four-color_theorem

謝謝老師ㄛ!


學生 敬上.


 2008-03-23 12:26個人資料
孫文先
Moderator



註冊日: 2002-07-30
發表數: 1094


 Re: "Road Coloring Problem." 道路著色謎題 以色列數學家破解(轉貼)

最下面及最上面的點如何達成?


_________________
孫文先 敬上

 2008-03-23 15:22個人資料傳送 Email 給 孫文先


九章數學出版社、九章數學基金會版權所有
本網頁各鍊結標題及鍊結內容歸原權利人所有
Copyright 2000 ~2004九章數學出版社、九章數學基金會
本網站內所有文字及資料版權均屬九章所有,未經書面同意之商業用途必究
This web site was made with XOOPS, a web portal system written in PHP.
XOOPS is a free software released under the GNU/GPL license.

TW XOOPS Official WebsiteFreeBSD Official WebsiteApache Official Website

Powered by XOOPS 1.3.10 © 2002 The XOOPS Project