作者buffalobill (水牛比爾)
看板puzzle
標題Re: [問題] 將正整數著色
時間Mon Oct 19 15:39:22 2015
※ 引述《ddtddt (得)》之銘言：
: 將所有正整數任意著色 紅 黃 藍
: 證明
: 存在 a b c 是正整數
: 使得 a+b a+c b+c a+b+c 都是同一個顏色。
這題超難
我想了好久
只能先證出2色
假設有存在一個著色法使得a,b,c不存在，則此著色法具有以下事實：
P1. 2與3不同色
若2與3同色，則(a,b,c)=(1,1,1)為解
P2. 4與6不同色
若4與6同色，則(a,b,c)=(2,2,2)為解
綜合P1與P2可得知下列兩種情形之一必為真
P3a.[2,6]同為一色[3,4]為另一色
P3b.[2,4]同為一色[3,6]同為一色
假設P3a為真，考慮5的顏色
5必不與[2,6]同色，因為(a,b,c)=(1,1,4)可構成[2,5,6]
5必不與[3,4]同色，因為(a,b,c)=(1,2,2)可構成[3,4,5]
故P3a為假
再來假設P3b為真，考慮5的顏色
5必不與[2,4]同色，因為(a,b,c)=(1,1,3)可構成[2,4,5]
故5必與[3,6]同色
P3. [2,4]同色 [3,5,6]為另一色
7的情形的話一樣有兩種
P4a. [2,4]同色，[3,5,6,7]為另一色
P4b. [2,4,7]同色，[3,5,6]為另一色
但是(a,b,c)=(1,2,4)可構成[3,5,6,7]故p4a為假
P4. [2,4,7]同色，[3,5,6]為另一色
最後考慮到8
P5a. [2,4,7,8]同色，[3,5,6]為另一色
P5b. [2,4,7]同色，[3,5,6,8]為另一色
[2,4,7,8]中的[2,7,8]可為(a,b,c)=(1,1,6)構成，故P5a為偽
[2,5,6,8]中的[5,6,8]可為(a,b,c)=(2,3,3)構成，故P5b為偽
所以
P5. 不論8與[2,4,7]或[3,5,6]同色，都存在a,b,c滿足條件。
三色的話這種證明法太搞肛了
可能要寫程式來算了XD
應該要有很優雅的證明才對說
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.251.148.94
※ 文章網址: https://webptt.com/m.aspx?n=bbs/puzzle/M.1445240364.A.E4A.html
1F：推 kirimaru73: 二色證好後 可以推出若三色方法存在 每色皆有無限多個 10/19 18:16
2F：→ buffalobill: 寫好一個程式來計算範圍內有幾種著色法了 10/19 21:53
3F：→ buffalobill: 果然N大於某數之後著色法的數量就變成0了 10/19 21:53
4F：→ buffalobill: 不過這種證明方法算是邪魔歪道吧 10/19 21:54
5F：→ kirimaru73: 歷史上最頂尖的那幾個數學家應該有辦法手寫完成 10/19 22:13
6F：→ kirimaru73: 這也是證明方法啊 一堆數學難題還不是由電腦輔助完成 10/19 22:13
7F：→ kirimaru73: 只是光看題目確實會以為有很簡單的秒殺方式 10/19 22:14
8F：→ buffalobill: 感覺像本要畫輔助線的幾何題結果用電腦三角函數硬算 10/19 22:48