sponsored links

2021年美國數學奧林匹克競賽中的圖論問題——到底難在哪裡?

普拉納國家公園由幾條在交叉路口交匯的小徑組成。。每條小路的兩個端點都在兩個不同的路口,而每個路口正好是三條小路的端點。小路只在路口相交。最後,沒有小路在相同的兩個路口開始和結束。下面是一個可能的公園佈局的例子,其中有六個路口和九條小路。

2021年美國數學奧林匹克競賽中的圖論問題——到底難在哪裡?

一個遊客在公園裡的行走情況如下:她從一個路口開始,沿著一條小路行走。在第一條小路的盡頭,她進入了一個路口並向左轉。在下一個路口,她向右轉,以此類推,在每個路口交替進行左轉和右轉。她這樣做,直到她回到她開始的那個路口。在公園所有可能的佈局中,她在行走過程中進入任何路口的最大可能次數是多少?

這個問題的陳述非常冗長,但是我們有簡單圖(Simple Graph)工具可以幫助理解(預設為平面圖)

簡單圖是指任意兩個頂點之間沒有超過一條邊,也沒有邊的起點和終點在同一個頂點的圖。換句話說,一個簡單的圖是一個沒有迴圈和多條邊的圖。

下面這個簡單圖中,每個頂點的度數為3(頂點的度數是指和該節點相關聯的邊的條數)。 讓我們看看根據題目要求的方式散步時,在每個頂點左右交替進行會發生什麼。

我在每條路徑上用字母 "L "和 "R "來表示散步者是左轉還是右轉。題目要求的是:進入任何路口的最大可能次數。在上面顯示的第一條路徑中,這個數字是1。

再選擇幾條路徑,我們發現有可能進入一個路口兩次。

為了考慮其他可能的行走方式,以更有規律的方向重新繪製圖形是有幫助的,這樣我們就可以看到對稱性。

一旦我們認識到這種對稱性,我們就可以看到,在這個公園裡沒有太多的 "不同 "路徑。透過不斷嘗試,我們發現不可能進入任何路口兩次以上。

但這個問題不僅僅是問所提供的公園的例子,而是問 "公園所有可能的佈局"。

我認為有兩個問題值得考慮。

  1. 對公園的可能佈局是否有限制,以幫助我們找到最大值?
  2. 為什麼會有一個最大值,也就是說,為什麼不可能在一個無限迴圈中不斷地進入同一個路口?

可能的公園佈局

從考慮最簡單的情況開始。給出的例子有6個路口(頂點),但是否有可能出現頂點更少的公園?我發現2個頂點是不可能的,因為 "沒有小路在同一個路口開始和結束",也就是說,這個圖形是 "簡單 "的。

我試著畫一個有3個路口的公園,但沒有成功,我意識到沒有奇數個路口是可行的。因為對於n個路口,邊的總數是3n÷2,(與每個頂點相連的3條邊,除以2以避免重複計算)。如果n是奇數,這個總數就不是一個整數。

有一個可能有4個路口的公園,但不可能多次進入一個路口。

2021年美國數學奧林匹克競賽中的圖論問題——到底難在哪裡?

例子中給出的是一個有6個路口的公園,我沒有找到具有6個路口的不同情況,所以我轉到了8個路口。

這個圖形是我熟悉的立方體的平面嵌入。它讓我意識到,所有符合給定條件的公園都可以表示為多面體。這是一個切入點。8個路口的公園不允許任何路口進入一次以上。

對於10個路口,遵循類似的結構,有一個內部和外部的五邊形。並嘗試了一些不同的走法,我發現有可能進入一個路口3次!

一個路口進入3次的例子

2021年美國數學奧林匹克競賽中的圖論問題——到底難在哪裡?

想出這個結構後,我覺得3可能是最大的可能。

另外,這時我已經意識到,可能的公園有無限的變化,為了解決問題,我不能輕易地進行分類。

  • 可能的公園佈局情況

因此,我決定從我之前提出的關於無限迴圈的可能性的問題出發,重新審視這個問題。

排除無限迴圈的可能性

根據題意,散步者回到起點時將會停止。那麼,有沒有可能進入一個不包括起點的無限迴圈?這個無限迴圈會是什麼樣子呢?

在不失一般性的前提下,我們假設散步者進入了假設的無限迴圈,並向右轉。

2021年美國數學奧林匹克競賽中的圖論問題——到底難在哪裡?

這意味著他必須以左轉來結束這個迴圈,然後再右轉來重複這個迴圈。但由於她是從另一個方向來的,右轉會使她離開迴圈,如上面的動畫所示。

因此,我們已經表明,無論任何路口的最大入口數是多少,它至少是有限的!這就是我們的觀察。

關鍵觀察是,路徑是確定性的

一個重要的觀察結果是,一旦我們知道散步者是在某條小路(邊)上向左轉還是向右轉,接下來的每條小路就只有一種可能的選擇。同樣地,前一條小路也只有一種可能的選擇,以此類推。所以她的整個路徑是完全確定的。

我們也已經表明,不可能進入一個無限的迴圈,因為她回到起點後就停止了。所以不可能在一條特定的小路上左轉兩次,也不可能在一條特定的小路上右轉兩次。

這就把最大的可能上界減少到了6個(向左或向右轉入3條小路的每個路口)。

但它實際上有可能實現嗎?

當她進入一個路口左轉時,她必須右轉離開(反之亦然)。所以我應該在圖中加入出口。它將有6個箭頭進入,和6個箭頭出來。

總之,有些地方不對。為了走完所有這些路徑,她必須從她已經走過的路回來,但方向是相反的。

在下圖中,只包括了4個箭頭。橙色的箭頭表示她左轉進入路口,右轉出來,藍色的箭頭表示她後面需要走的相反方向。

為什麼這是不可能的?

正如我們之前所說,一旦我們知道路線和方向(左或右),整個路徑就完全確定了。特別是,一旦我們知道她沿著橙色箭頭左轉進入路口,我們就知道她的整個路徑形成了一個迴圈,從起點開始,在某個時間返回那裡。

為了沿著藍色箭頭行走,她需要走這個完全相同的迴圈,但方向相反。這是不可能的。一旦開始走這條路,就真的沒有回頭路了!這限制了可能的最大數量。

這個限制將一個路口的最大可能進入次數限制為3次。下面顯示了兩種可能性,根據進入-退出順序用顏色編碼。

我們已經展示了一個實現最大3次的公園的例子(上面的五邊形稜形結構)。

所以在公園所有可能的佈局中,3是她在行走過程中進入任何路口的最大可能次數。

圖論真了不起

圖論是離散數學的一個迷人的領域,有很多實際應用。特別是自從世界網路和社交媒體的出現。

分類: 教育
時間: 2021-10-12

相關文章

全國特等獎!華水學子在“水利類大學生奧林匹克競賽”中閃閃發光!

全國特等獎!華水學子在“水利類大學生奧林匹克競賽”中閃閃發光!
全文共915字,35圖 閱讀時間約為6分鐘~ 水利水電開發建設中 魚類洄游怎麼辦 維持河流生態系統物種多樣性怎麼辦 彆著急 我們水利學院學生團隊解決了這問題 讓我們一起來看看 華水學生的無比酷炫的設計 ...

IMF預測2021年美國GDP為22.94萬億美元!那中國、印度、日本呢?

IMF預測2021年美國GDP為22.94萬億美元!那中國、印度、日本呢?
下為IMF(國際貨幣基金組織)在今年10月份公佈的新版<世界經濟展望>報告截圖!在報告中,IMF將2021年全球經濟增長預期目標小幅下調至5.9%,但對明年的經濟發展預估保持不變,依然是增 ...

2021年金童獎提名球員中,身價前20的球員:阿...

2021年金童獎提名球員中,身價前20的球員:阿...
2021年金童獎提名球員中,身價前20的球員: 阿森納三位青年才俊入圍,成為該榜單入圍最多的俱樂部: 薩卡身價6500萬歐元排名第二! 馬丁內利2200萬歐元身價排名第15! 薩利巴1800萬歐元排名 ...

2021年全國中學生物理競賽賽區一等獎名額全部出爐!共計1800人

2021年全國中學生物理競賽賽區一等獎名額全部出爐!共計1800人
2021年全國中學生物理競賽賽區一等獎名額分配通知釋出,各省地區競賽省一人數確定!自主選拔線上整理相關內容,供參考. 2021物理競賽各省名額分佈 2021年省一名額共1800個,與2020年相比增加 ...

警惕美國發起“生物戰”!中俄聯手出擊,要求聯合國調查美國

警惕美國發起“生物戰”!中俄聯手出擊,要求聯合國調查美國
據報道,近日,中國與俄羅斯聯手出擊,要求聯合國調查美國的生物戰實力. 所謂"生物戰",就是指利用生物武器發起攻擊的戰爭.而生物武器其實就是指細菌,病毒等生物製劑,這些生物製劑如果被 ...

江西工程學院在“傑創杯”2021年江西省大學生電子專題設計競賽中摘金攬銀抱銅
近日,由江西省教育廳主辦的"傑創杯"2021年全省大學生電子專題設計競賽在江西製造職業技術學院舉行.全省共30多所本科院校近1400人參加.本次比賽,江西工程學院派出63名選手參加 ...

一出手就擊中美國六寸,中俄開始去美元化,越來越多國家紛紛效仿

一出手就擊中美國六寸,中俄開始去美元化,越來越多國家紛紛效仿
美國現在的經濟正在處於緊張時刻,而這都是之前美國霸權主義所導致的後果.眾所周知,美國因為對國際石油的把控權,讓美國在國際上保持著主導地位.但是隨著美國越來越多的搞事情,不少國家紛紛對美國表示不滿.其中 ...

賈躍亭:割美國韭菜,還中國債

賈躍亭:割美國韭菜,還中國債
出品 | 虎嗅汽車組 作者 | 梓楠法師 即使法拉第未來(下稱:FF)在上市後宣稱旗下車型將按計劃交付,但FF所給出的故事無法說服所有人. 日前,美國做空機構J Capital Research(下稱 ...

美國又使壞?中企上億專案被攪黃!迫於壓力多國不敢表態

美國又使壞?中企上億專案被攪黃!迫於壓力多國不敢表態
最近國際方面發生了一件讓國人氣憤不已的事!據報道,中國企業華為參與競標的,"東密克羅尼西亞光纜專案"被叫停了,而且整個專案擱淺,沒有任何競標商中標.據目前對外公開的訊息稱,此次中國 ...

外媒:法國指責澳大利亞和美國在“嚴重危機”中“說謊”
參考訊息網9月19日報道據法新社巴黎訊息,法國當地時間18日指責澳大利亞和美國在安全協議危機中說謊,該協議讓堪培拉廢棄了購買法國潛艇的合約轉而購買美國潛艇. 報道稱,法國外交部長讓-伊夫·勒德里昂對法 ...

494:103!歐洲議會壓倒性透過決議,主動喊話美國結盟對抗俄中

494:103!歐洲議會壓倒性透過決議,主動喊話美國結盟對抗俄中
從最近幾年時間裡歐美國家採取的行動來看,中國一直都是他們的重點目標.此前,美國為了保證自己的國際地位以及影響力,始終想要透過各種方式來遏制中國,甚至不惜損害兩國關係,出臺多種單邊主義政策.在這一影響下 ...

2021年美國槍支暴力案件數再創新高 不能保障人民生命談啥人權

2021年美國槍支暴力案件數再創新高 不能保障人民生命談啥人權
除非接下來的3個多月出現奇蹟,否則2021年必定成為美國槍支暴力最嚴重的一年.根據統計資料顯示截止到9月15日,美國共有14516人死於槍支暴力,比2020年同期多了1300人.大規模槍擊事件也在呈現 ...

地球班特別班會:美國主動解釋,中美是競爭不是對抗,有何目的?

地球班特別班會:美國主動解釋,中美是競爭不是對抗,有何目的?
地球是一個特殊的班級,每個國家都是這個班級裡的同學. 最近,由於中美關係持續緊張,在被國際社會寄予厚望的氣候問題上,都沒能達成合作,引發了聯合國的擔憂,聯合國秘書長為此發表言論,說"中美關係 ...

2021辛丑年不平靜的中秋夜
影片載入中... 妖風起, 雷電閃, 為什麼偏偏在今晚? 2021辛丑年中秋夜, 無明月, 有風雨, 老天爺要驅趕新冠病毒嗎? 但願瘟神走, 但願還閩南一方淨土, 但願明早醒來一片安寧祥和, 一切如常 ...

甘肅民族師範學院學子在第十三屆“挑戰杯”甘肅省大學生課外學術科技作品競賽中獲佳績
近日,由共青團甘肅省委.甘肅省教育廳.甘肅省科學技術協會和甘肅省學生聯合會主辦,西北民族大學承辦的第十三屆"挑戰杯"甘肅省課外學術科技作品競賽和紅色專項活動落下帷幕.甘肅民族師範學 ...

羨慕嫉妒恨?無法忍受看著中國超越,五角大樓高官辭職後受訪:美已在AI競賽中輸給中國

羨慕嫉妒恨?無法忍受看著中國超越,五角大樓高官辭職後受訪:美已在AI競賽中輸給中國
來源:環球網 [環球網報道 記者 張曉雅]"前五角大樓軟體主管表示,美國已在人工智慧(AI)領域輸給中國."英國<金融時報>當地時間10日以此為題,刊載對剛剛離職的五角 ...

CGTN專訪前美國國務院官員:中美應打造真正具有前瞻性的合作願景
10月11日,聯合國<生物多樣性公約>第十五次締約方大會(COP15)在雲南昆明開幕.全球生物多樣性及國際合作成為全人類共同關心的重要議題.中央廣播電視總檯CGTN主持人田薇就此對美國國務 ...

遠東一中再次展現實力,斬獲中國化學奧林匹克競賽一等獎

遠東一中再次展現實力,斬獲中國化學奧林匹克競賽一等獎
2021年10月13日,中國化學會發布了2021年第35屆中國化學奧林匹克(初賽)一等獎學生名單,遠東一中高三年級6班常治林同學榮獲一等獎.這算是第一次除五大名校外上榜的公辦學校吧,恭喜遠東一中[撒花 ...

華北電力大學控計學子在全國大學生資訊保安競賽中喜獲佳績

華北電力大學控計學子在全國大學生資訊保安競賽中喜獲佳績
8月28日至31日,由教育部高等學校網路空間安全專業教學指導委員會主辦,山東大學承辦的第十四屆全國大學生資訊保安競賽作品賽決賽在線上舉行,華北電力大學控制與計算機工程學院的兩組作品<文心雕蟲:面 ...