[中译] 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