IMO2016 趣題：Geoff 的青蛙

2016 年 IMO 的第 6 題（也就是第二天比賽的第 3 題）非常有趣，這恐怕算得上是近十年來 IMO 的所有題目中最有趣的題目之一。平面上有 n ≥ 2 條線段，每兩條線段都有一個交點，並且任意三條線段都不交於同一點。 Geoff 打算在每條線段的其中一個端點處放置一隻青蛙，並讓每隻青蛙都朝向它所在線段的另一個端點。然後， Geoff 將會拍 n – 1 次手。每次拍手時，每隻青蛙都立即向前跳到它所在線段的下一個交點處（青蛙們在跳躍過程中始終不會改變方向）。 Geoff 希望巧妙地安排初始時放置青蛙的方法，使得在整個過程中，任意兩隻青蛙都不會同時到達某個相同的交點。這個題目有兩個小問。

證明：當 n 為奇數時， Geoff 一定有辦法實現他的要求。

證明：當 n 為偶數時， Geoff 永遠無法實現他的要求。

下圖是 n = 5 時的其中一種可能的線段布局，以及其中一種滿足要求的青蛙放法。你可以試一試， n = 5 時的其他放法就不見得滿足要求了，而 n 為偶數時的任何一种放法都是不滿足要求的。

注意到，在上面這種滿足要求的青蛙放法中，任何兩隻青蛙都不在「相鄰」的端點上。這不是巧合。我們接下來說明，把兩隻青蛙放在「相鄰」的端點上，則這兩隻青蛙必然會相撞。這裡，我們可以為「相鄰」下一個更加明確的定義。將所有線段充分延長，並與一個充分大的圓相交。把每條線段的端點都改到這些交點處，於是所有線段的所有端點就變為了一個圓周上的 2n 個點。如果兩個端點之間的圓弧上沒有其他端點，我們就說這兩個端點是相鄰的。

現在，假設我們把兩隻青蛙放在了兩個相鄰的端點上，如上圖所示。藍色的線表示的就是這兩隻青蛙所走的路，其中實線部分表示這兩條路相交前的部分。由於兩個端點是相鄰的，因此這兩條藍線之間不再夾著其他線段。所有其他線段都是橫穿過這兩條藍線的，它們與兩條藍線的交點要麼都在虛線部分，要麼都在實線部分。這會使得兩條藍色實線上產生出相同數目的交點。於是，兩隻青蛙將會同時到達兩條藍線的交點處。

這就說明，把兩隻青蛙放在相鄰的端點上是必死的。在一個滿足要求的放法中，任何兩隻青蛙中間都要間隔至少 1 個端點。然而，我們一共有 n 只青蛙和 2n 個端點，因而這些青蛙必須得恰好每隔 1 個端點放一隻。考慮到這一點，我們立即就把第 2 小問解決了。當 n 為偶數時，對於任意一條線段，都有 n – 1 條線段穿過它，這意味著這條線段的兩個端點之間恰好隔著 n – 1 個端點（不管是算哪邊的弧），這是一個奇數。所以，如果每隔 1 個端點放一隻青蛙，那麼這條線段的其中一端放了青蛙，另外一端也會有隻青蛙。這是不符合要求的。

而當 n 為奇數時，每隔 1 個端點放一隻青蛙，就會正好讓每條線段上都有一隻青蛙。容易看出，此時任意兩隻青蛙之間都會隔著奇數個端點。接下來，我們證明，只要兩隻青蛙之間隔著奇數個端點，那麼這兩隻青蛙一定不會相撞。如上圖所示，我們還是用藍色的線表示這兩隻青蛙所走的路。其他的線段分成這樣三類：

從虛線處橫穿過這兩條藍線

從實線處橫穿過這兩條藍線

夾在這兩條藍線之間

根據剛才的討論，第一種類型的線段不會在兩條藍色實線上產生交點，第二種類型的線段會在兩條藍色實線上產生相同數目的交點。至於第三種類型的線段，每一條要麼與這邊的藍色實線相交，要麼與那邊的藍色實線相交。由於兩隻青蛙之間隔著奇數個端點，因此這種類型的線段有奇數條，在這邊的藍色實線產生的交點數與在那邊的藍色實線產生的交點數就必然是一奇一偶。綜合這三種類型的線段，我們最終得出，這些線段在兩條藍色實線上產生的交點數目是不同的，因為數目的奇偶性都不一樣。所以，兩隻青蛙不會相撞。

回想我們剛才所說的，當 n 為奇數時，間隔著放青蛙會使得每條線段上都各有一隻青蛙，並且任意兩隻青蛙之間都會隔著奇數個端點。這就將成為一種滿足要求的放法。於是，我們就完整地證明了第 1 小問的結論，整個問題也就解決了。

這道題背後有一個有趣的故事。現任 IMO 主席 Geoff Smith 賽前曾經說，他將會以一種特殊的形式與參賽選手互動。最終，謎底揭曉：他成為了 IMO 第 6 題的主人公。

本文由超級數學建模編輯整理

資料來源於http://www.matrix67.com/blog/archives/6851

轉載請在公眾號中，回復「轉載」

-----這裡是數學思維的聚集地------

「超級數學建模」（微信號supermodeling），每天學一點小知識，輕鬆了解各種思維，做個好玩的理性派。50萬數學精英都在關注！

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！