作者cmrafsts (我~好~弱~)
看板IMO_Taiwan
標題Re: [問題] IMO 2013 in Colombia Day 2
時間Sat Jul 27 10:02:17 2013
※ 引述《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)
1F:推 Dawsen:wow... 厲害... 原來歸納法行得通! 07/27 10:51
2F:→ Dawsen:我後來是用 "以0開頭k結尾的直線BL恰Φ(k)個"直接構造 07/27 10:52
3F:→ Dawsen:不過可以把k當成第二個 可以證明假設0緊接的下一個是k的話 07/27 10:53
4F:→ Dawsen:1. 所有相差是k的一定得按照順序排 而且a, a+k中間不能有 07/27 10:54
5F:→ Dawsen:間隔,否則考慮第一個不滿足條件的元素可以導致矛盾 07/27 10:55
6F:→ Dawsen:2. 接下來就是mod k剩餘系的排列問題。 第一個已經是餘0 07/27 10:55
7F:→ Dawsen:假設下一個是餘x的話,可以證明之後餘a的一定得在餘a+x之前 07/27 10:56
8F:→ Dawsen:出現,所以(x,k)=1, 而且一種這種排列都是唯一,且是BL 07/27 10:57
9F:→ Dawsen:多的1是k=1的情形。 07/27 10:58
10F:→ Dawsen:BTW, 把k當成第二個 意思是把0當第一個 07/27 10:58
11F:推 Dawsen:對了..(1)我有疑問。重新調位置之後,還會平行嗎? 如果會 07/27 11:07
12F:→ Dawsen:平行,好像就不用證了。如果不平行, 0,2k+1也有可能相鄰 07/27 11:08
13F:→ Dawsen:還是說你只是寫sketch, 進一步分析可發現不為BL? 07/27 11:09
14F:推 Dawsen:(3)的ai+al-aj也有可能會=kd for some integer d? 07/27 11:47
15F:→ cmrafsts:這是要模k後的結果阿,所以小於2k 07/27 13:50
16F:→ cmrafsts:我不太理解學長對(1)的疑問,不過我上面寫的應該不 07/27 13:56
17F:→ cmrafsts:足以完成(1)的證明。2k+1時我們直接考慮0---2k+1 07/27 13:56
18F:→ cmrafsts:不,這樣好像證不出(1),雖然要可以證出但我在凌晨證不出 07/27 14:01
19F:→ cmrafsts:請學長們先看看怎麼證...簡哥唬爛我說這樣能證... 07/27 14:01
※ 編輯: cmrafsts 來自: 200.69.102.144 (07/27 14:06)
20F:推 hahaj6u4503:我也打算用歸納法,(1)太強了沒觀察到!! 07/27 16:43
21F:→ cmrafsts:喔有了,反正只要再管0n相鄰,拖(3)救援WWW 07/28 01:21
22F:推 adaadaadaben:偷偷問一下樓主是?XD 07/29 07:34
23F:→ cmrafsts:TWN1,台灣最低分 我知道樓上是誰喔~~~ 07/31 08:11