Re: [問題] IMO 2013 in Colombia Day 2

看板IMO_Taiwan作者cmrafsts (我~好~弱~)時間11年前 (2013/07/27 10:02)推噓5(5推 0噓 18→)

留言23則, 4人參與討論串2/2 (看更多)

※ 引述《FAlin (FA（バルシェ應援）)》之銘言： : 4. Let ABC be an acute triangle with orthocenter H, and let W be apoint on : the side BC, between B and C. The points M and N are the feet of the : altitudes drawn from B and C, respectively. ω_1 is the circumcircle of : triangle BWN, and X is a point such that WX is a diameter of ω_1. : Similarly, ω_2 is the circumcircle of triangle CWM, and Y is a point : such that WY is a diameter of ω_2. show that the points X, Y, and H are : collinear. : 5. Let Q>0 be the set of all rational numbers greater than zero. Let : f: Q>0 → R be a function satisfying the following conditions: : (i) f(x)f(y) ≧ f(xy) for all x,y ∈ Q>0, : (ii) f(x+y) ≧ f(x) + f(y) for all x,y ∈ Q>0 : (iii) There exists a rational number a>1 such that f(a) = a : Show that f(x) = x for all x∈Q>0. : 6. Let n≧3 be an integer, and consider a circle with n+1 equally spaced : points marked on it. Consider all labellings of these points with the : numbers 0,1,..., n such that each label is used exactly once; two such : labellings are considered to be the same if one can be obtained from : the other by a rotation of the circle. A labelling is called beautiful : if, for any four labels a<b<c<d with a+d=b+c, the chord joining the : points labelled a and d does not intersect the chord joining the points : labelled b and c. : Let M be the number of beautiful labellings and let N be the number of : ordered pairs (x,y) of positive integers such that x+y≦n and : gcd(x,y)=1. : Prove that M = N+1. -----------------------------第六題防雷------------------------------------- 首先把N+1解釋成ΣΦ(i) i=1,2,...,n，並把n=3.4.5.6.7的情況畫出來觀察，我們對n歸納。因為我懶所以把beautiful labelling寫成BL well known：n的BL去除m+1~n並重新調整位置會變m的BL 我宣稱以下幾件事會成立： (1)0~n的BL中相加為n的弦全部平行，如果n=2a則aa弦變為在a處的切線。 (2)每個0~n的BL可以在某處插進n+1變成0~n+1的BL。 (3)將0~n的BL拆成以0開頭的直線排列(直線BL)，以n結尾的恰Φ(n)個。 (4)在如此的直線排列中若n+1不插在尾則有至多一種插入n+1的方法。以上幾點配合歸納中提到的東西可以證明這題。根據精闢的觀察n=3.4.5.6.7時以上都會成立，此為奠基。 (1)n=2k+1時因n=2k-1是對的，將2k+1的BL去除0,2k+1時由歸納假設此時所有相加為 2k+1的弦會平行，現在插回0,2k+1，如果使此弦不與其它弦平行則會相交。 n=2k+2時做法同上，只需多討論一種狀況：設去除0,2k+2後k+1兩側的點分別為 m,2k+2-m，0,2k+2插進m,k+1中間的狀況。但這樣k+1---m, 0---m+k+1兩弦會相交。 (2)要證明0~n的BL可以在某處插進n+1。現在把一個n的BL裡的0去除，由(1)所有相加為n+1的弦就以某條線線對稱。設以CC對稱設原本的0在位置A，A對CC的線對稱A'可以放n+1使上面的1~n+1是BL，最後只需考慮相加為n+1的弦是否相交，因為只需考慮0,n+1同時存在是否會變非BL。但是現在相加為n+1的弦都平行 (3)假設是0,a1,a2,...,a(k-1),k 如果有i<j<l使ai+al=aj模k，則ai+al-aj=0,k其中之一，取0---aj, ai---al 或aj---k, ai---al就相交。現若a2=\=2a1則a2後方有a2-a1，故a2=2a1，同理可得ai=ia1 這樣則要求(a_1,k)=1。若真如此，它顯然是個BL。 (4)加重命題，如果一個n的直線BL可以用兩種方法插入n+1變成n+1的直線BL，一定是插在0後面或最後面。此等價於原本環形的BL若能以兩種方法插入，必是插在 0的兩側。我們取一個n+1的直線BL，等價於從一個n的直線BL插入n+1，將最前面的0除去並把所有數減1後這個插入的動作變成從一個n-1的環形BL插入n，但我們已經決定了哪邊要插回0，這樣組合起來的個數和n的直線BL一樣多。由歸納假設至多插一處，除非插在0(原本的1)的兩側，注意如果原本1在0後面或最尾端n可以插在第1,2或最後一個位置，注意如果1在第a個位置則可以放在第a-1,a個位置。但這樣全部反運算對應回n+1的直線BL後有一種會讓0---n+1和1---n相交。故至多一種位置。特別的第一種狀況只能放第1個位置。 ----------------------------------------------------------------------- 由(2),(4)，只有一種插法的直線BL那種插法就會讓n的直線BL對應成n+1的直線BL，有兩種插法的一種在0後面一種在最尾端，由(3)可以得到兩種插法會對應成n+1直線BL的條件等價：(a1,n+1)=1或(n+1-a1,n+1)=1，所以兩種都是。 ----------------------------------------------------------------------- 現在有n的BL個數=n-1的BL個數+Φ(n)，by induction and we are done. ----------------------------------------------------------------------- 我在考場時寫出了(3)(4)並得出M<=N+1，此時原命題deduced to(1)，但(1)是官方解的lemma，最後因為有個俄羅斯隊員和我寫的一樣而拿到5，所以我拿5 (1)其實超強，說不定(1)可以直接推出(3)(4) (1)的確超強...有種這題只是要做(1)的感覺...求不用(1)的作法雖然我的(3),(4)加上直接構造可以完成證明，而且對懶得觀察出(1)的人似乎是唯一好想的證法，但太不協調，求協調的不用(1)的歸納證明其實這題可以純粹當數論做...這是可以當數論的C7... 官方解有個占兩分的lemma說0兩側的數必互質，不知有啥用但確實可由我的歸納順便得出。可以看出不管多長，以0開頭k結尾的直線BL恰Φ(k)個，我不知道能否直接證明。拿分狀況去掉星號只有兩個美國隊兩個加拿大隊個7，Jeck Lim被星號，合理推斷是他第二面滿分。應該是只比2006和2009的P6高分。 --------------------------------底部防雷----------------------------------- -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 200.69.102.144 ※ 編輯: cmrafsts 來自: 200.69.102.144 (07/27 10:04)

推

Dawsen

07/27 10:51, , 1^F

07/27 10:51, 1^F

→

Dawsen

07/27 10:52, , 2^F

07/27 10:52, 2^F

→

Dawsen

07/27 10:53, , 3^F

07/27 10:53, 3^F