Re: [問題] 將正整數著色
看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者buffalobill (水牛比爾)時間9年前 (2015/10/19 15:39)推噓1(1推 0噓 7→)留言8則, 2人參與討論串2/5 (看更多)
※ 引述《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://www.ptt.cc/bbs/puzzle/M.1445240364.A.E4A.html
推
10/19 18:16, , 1F
10/19 18:16, 1F
→
10/19 21:53, , 2F
10/19 21:53, 2F
→
10/19 21:53, , 3F
10/19 21:53, 3F
→
10/19 21:54, , 4F
10/19 21:54, 4F
→
10/19 22:13, , 5F
10/19 22:13, 5F
→
10/19 22:13, , 6F
10/19 22:13, 6F
→
10/19 22:14, , 7F
10/19 22:14, 7F
→
10/19 22:48, , 8F
10/19 22:48, 8F
討論串 (同標題文章)
puzzle 近期熱門文章
PTT遊戲區 即時熱門文章
49
90
28
41
11
13