如何評價 2016 香港 IMO 的第六題？

01-22

難度、題目設計等方面。
原題如下：

我說還是另請高明吧，我也不是謙虛，你說我一個程序員，怎麼就來做IMO了呢

我可以先證一半：

對於任意一個跳法，每個交點都會被兩隻青蛙各經過一次，把兩個時刻相加，如果相加的結果是奇數，稱作奇交點；如果相加的結果是偶數，叫做偶交點。奇交點的兩個時刻一定一奇一偶，因此兩隻青蛙不能同時到達奇交點。

考慮任意三條線段相交形成的三角形：

設三個交點之間分別相隔k1, k2, k3條線段，也就是相隔k1-1, k2-1, k3-1個交點。當沒有其他線段與這個三角形相交的時候，k1=k2=k3=1。其他任意一條線段，要麼與三角形的兩條邊相交，要麼與三條邊都不相交（交點在三條邊的延長線上），而不可能只與一條邊相交、或者與三條邊都相交。因此k1 + k2 + k3永遠是奇數。

由於 $c + (b + k_2) + (c + k_1) + (a + k_3) + a + b = 2a + 2b + 2c + (k_1 + k_2 + k_3)$

為奇數，所以三個交點中必須有一個或者三個奇交點【1】。

當n為奇數時，任意取一種跳法，並任意選擇一條線段。依次考慮這條線段上的每個交點，每個交點都與另一條線段相對應；如果這個交點為偶交點，則讓這條線段上的青蛙改從另一頭起跳，則另一條線段上的青蛙到達這個點的時間會從t變為n-t，奇偶性互換，因此這個交點會從偶交點變為奇交點。對所有其他n-1個線段做這樣的操作，這樣這條線段上所有的交點都是奇交點。

考慮任意另外一個交點，這個交點對應的兩條線段與我們選定線段的交點都為奇交點，由於性質【1】，則任意的另外一個交點也是奇交點，所以所有的交點都是奇交點。因此所有的青蛙都不可能同時到達同一個交點，這個解答符合條件。

當n是偶數時，我們首先證明至少有一個偶交點：

由於奇交點中兩個時刻一定一奇一偶，如果所有的交點都是奇交點，則所有到達時刻中奇數偶數應相同。然而當n是偶數時，我們有n * n / 2個奇數時刻，卻只有n * (n-2) / 2個偶數時刻，不一樣多，因此一定存在至少一個偶交點。

考慮這個偶交點對應的兩條線段l1, l2，對任意其他一條線段，這條線段與l1,l2的兩個交點一定是一個奇交點和一個偶交點。因此偶交點至少有n-1個。

對於n=2的情況，顯然不存在滿足題意的跳法；

當n &> 2時，如果這n-1個偶交點都位於同一條線段上，則這n-1個偶交點的時刻中，奇數只比偶數多2個，而總和中奇數比偶數多n個，因此這n-1個偶交點不能位於同一條線段上。去掉我們最早選中的一個偶交點，其他的n-2個，設其中有k個位於一條線段，而n - k - 2個位於另一條線段，則考慮其中一條線段上奇交點和偶交點的組合，共有k(n-k-2)個，每個都對應一個不同的偶交點。

由於

$k(n-k-2) ge n-3$

所以偶交點至少有2n - 4個。

（接下來還沒想好怎麼證）

======================================================

@狗開服的答案是正確的，只是描述不夠嚴謹，把證明過程寫的更清晰一些。原來這麼簡單……

任意作一條新的直線使直線與原來的所有線段都不平行，並標記一個正方向，作為x軸；任取x軸上一個點作為原點，並將x的正方向逆時針旋轉90°，作為y軸方向，建立一個直角坐標系。規定沿y軸方向為從下到上，沿相反方向為從上到下。

其他線段與x軸正方向成的角在(0, 2π)之間，並且兩兩不相等。將所有的線段按與x軸正方向成的角排序，並依次編號為1,2,3,...n。每個線段的兩個端點y坐標不同，我們規定y坐標比較大的為上端點，比較小的為下端點；青蛙從下端點跳到上端點為「往上」，相反為「往下」。

考慮第k條線段和第k+1條線段：

所有其他線段與這兩條線段只可能同時相交於交點上方，或者同時相交於交點下方，否則若像圖中紅線一樣相交，則圖中∠2為三角形外角，得到∠2 &> ∠1，紅線與x軸正方向成的角應當在兩條線段之間，則排序時應當排在k與k+1之間，矛盾。

因此，兩條線段從上端點到交點應當有相同數量的其他線段的交點，因此如果兩隻青蛙同時從上往下跳，則會在交點相遇；相反，如果同時從下往上跳，也會相遇。因此線段k與k+1的跳法必須上下相反。

考慮線段n與線段1，有類似的結論，但此時其他線段的交點總是恰好一個在交點上方，一個在交點下方，如果青蛙跳法上下相反則會相遇；因此線段n與線段1的跳法必須上下相同。

當n是偶數時，1與2跳法相反，2與3相反，依次類推，1應與n跳法相反，這與線段n與線段1跳法相同矛盾。因此n為偶數時不存在這樣的跳法。

n為奇數時，使用前面的方法可以證明，符合奇數線段向上、偶數線段向下的跳法，所有交點都是奇交點，因此不會相遇。

補充了一些思路上的說明。

========================================分割線===========================

本來想用歸納做第一問的，發現非常困難。估計要直接構造放蛤的方法。

@靈劍給了一種構造方法，我們不妨按照這種方法把構造的圖畫出來。（或者你也可以自己試著畫一畫看看，結論都是一樣的。）

這裡取 $n=5$ 。畫出來的圖如下，一種顏色的字代表一种放法：

這個規律就比較明顯了。我們猜想：如果取一個閉曲線把端點連起來（如圖中紅線），相鄰的點總不能同時放蛤。

這個猜想是對的，不難發現相鄰的點到對應線段的交點的步數總是一樣的。這個結論對 $n$ 為偶也是成立的。證明略。

這就是說，在 $n$ 條線段 $2n$ 個頂點上，實際上可能的放蛤法只有兩種。

這樣的話，如果從整體考慮放蛤的方法，問題就比較明朗了。

先看看第二問，這裡用 $n=4$ 的情況說明問題：

那麼這下考慮第一問就更容易了，因為放蛤法只有兩種，所以猜測任意一種都是可以的。這裡取 $n=5$ ，觀察 $P_1P_5$ 這個線段：

其中主要的原理在於，（在外圍的閉曲線上） $P_1P_5$ 中間隔了奇數個 $P$ ，這會導致兩個蛤蛤到 $K$ 點的步數奇偶互異。

題解的話到處都有，也就不在這裡說了。 @狗開服的解法思路和普遍流傳的解法基本是一樣的。一個更好的描述是，作一個圓使得所有交點都在其內部，再用線段的延長線與圓的交點代替線段的端點。

從結果來看，還是相當好的一道題。

（圖來自貼吧，不過可以在官網上直接找到。P6是每個國家6名選手這道題的分數總和，滿分7×6=42）

雖然題解看起來很簡單，但畢竟還是「定向思維」類型，所以得分率低一些也是正常的。

就題目本身來說，也有很多方法發現這一規律。基本上只要注意到「圓上放蛤的點不能相鄰」就已經算是把題目做完了，而作圓本身並不是很困難的事情：嘗試n=5,7的情況，規律基本是很明顯的。與其它的題目相比，這大大降低了題目的難度。講道理的話，說這道題是聯賽二試難度也一點都不過分（逃）。

所以從某種意義上講，把4和6的位置換一下可以提高分數的說法是有道理的。這道題目的難度一方面體現在巧妙的思路，另一方面也體現在它的位置上。類似的情況也有第29屆CMO的6題，在坑選手方面基本屬於同一類型。

不過，一道題的命運啊，當然要靠它的難度，但是也要考慮到歷史的行程。西方哪個組合題我沒做過？IMO2011的那個風車，比這些題不知道高到哪裡去了，我跟它談笑風生！說起來，組合題本身就是數學競賽里最有趣的部分，與其去關注得分率，不如欣賞一下題解，體會一下數學的美妙呀。

歪樓。IMO副主席Geoff Smith把自己的名字Geoff放入了捷克的供題中。

-----------------分割線--------------------

一下轉自百度貼吧：（手機編輯不便）

Notice how the name is different in different languages. Some examples:

Dutch: Amalia

German: Lisa

Hungarian: Jeromos

Icelandic: Gutti

Italian: Ludo

Polish: Fredek

Russian: Ivan

Spanish: Mafalda

Swedish: Jana

English, French, ... : Geoff

中國：傑夫

捷克：pepa

謝邀。

第一問思路不難，直接構造即可，就是把構造過程說清楚比較麻煩，先定義第每兩條線段的交點，然後在每一個交點上面安排兩個不同的時間點，設總共有2k+1條線段，2k個時間點,同一位置兩個時間點的下標之和應為2k+1。

第二問。設有2k條線段。

定義「類中點」。每條線段上的其中一個交點把這條線段分成線段數相等的兩部分，稱這個點為類中點。

下證必定存在兩個類中點重合(從而青蛙一定相遇)。假設2k個類中點互不重合。

簡單思路說一下，

單條線段被劃分成n段，取兩相交線段，交點距離各自其中一端點最近，但都以另外一端為起點，兩線段分別被或分成a段和b段。

在此兩線段上距離交點最遠端點上各放一青蛙。若a=b則青蛙相碰，若a!=b則不碰。

n為偶數時，a=b=n，所以無論如何，青蛙都會相碰。

n為奇數時，a+b=2n-3, a=n-2, b=n-1，所以通過這種安置方法能滿足。

先證明如果相鄰兩個端點放置了青蛙的話，命題就不成立，因為相鄰兩個端點所在的兩條線段在交點前，其他線段與他們的交點數量必然相同（這個就比較容易證明了）

如果放置青蛙的兩個端點中間還存在一個端點的話，命題就成立，因為之前的交點數量相差1

所以需要證明的就是2n個點，存在互不相鄰的n個點，且這n個點不是同一線段的兩個端點，這個命題在n為奇數時候成立，n為偶數時候不成立。

歐拉的那個哥尼斯堡橋那個，結論也是奇偶有關的。我想這個問題是差不多的。

我覺得第一問不難，直接構造。第二問還是有一定難度的，如果只從常規思路入手十有八九做不出來，很考察學生的思維靈活程度。