[中譯] Puzzleup 2021 (8) POINTS AND COLOR LINES

作者: LPH66 (-6.2598534e+18f)   2021-10-20 20:13:50
題目網址: https://www.puzzleup.com/2021/
https://www.puzzleup.com/2021/puzzle/?8
答題時限: 10月21日7PM-比賽結束(約11月9日)
加分時限: 10月21日7PM-10月26日6:59PM
答對可得基本分100分。答案可上傳5次,每改1次答案從基本分扣20分。 
比賽期間內可隨時上傳答案,加分時限內答對第n天加(6-n)分       
另依題目的難易有額外加分(如有80%的人這題答錯,答對者加80分)  
◆POINTS AND COLOR LINES
There are X points on a plain paper such that no three of them are collinear.
Using four different colors, you will draw lines connecting each point with
every other point.
Conditions:
-No triangle formed by these connections (and having these points as corners)
would be monochromic.
-At no point can all four colors be found.
What is the maximum possible value for X?
在一張紙平面上有任三點不共線的點 X 個。
你使用四種顏色將每個點都畫線連到所有其他點,滿足以下條件:
- 任一個如此形成的 (以這些點為頂點的) 三角形都不是三邊全同色。
- 對每一個點, 所有的連出邊不可四色都有。
試問 X 的最大值為何?
====
兩色和三色的問題都是著名問題了, 不過四色...有種這題最後會送分的預感
作者: buffalobill (水牛比爾)   2021-10-20 20:34:00
嘗試使用拉姆齊定理,似乎沒有效果...大概想通為何會送分了,假設你透過鴿籠什麼的推理出答案是100的話,你得丟出一個K100的四色線圖……光是證明答案不會大於100還不夠
作者: arthurduh1 (arthurduh1)   2021-10-22 17:59:00
還沒有時間想,不過這樣就差很多了不然查到的上下界差距近年來都還沒壓到小於 10

Links booklink

Contact Us: admin [ a t ] ucptt.com