Re: [問題] 將正整數著色

[LPH66 (-6.2598534e+18f)]

如果題目改問 a 2a 3a 的話

是確實存在一種塗色法對任何正整數 a, a 2a 3a 不都同色

(這裡甚至用不到 3a, a 跟 2a 就足夠了)

這個塗色法是: 將正整數做質因數分解

若其 2 的次方數是奇數則塗紅色, 是偶數 (包括沒有因數 2 即所有奇數) 塗藍色

這種塗色法裡, 對所有正整數 a, a 跟 2a 保證不同色

---
nobrother 的機率證明只有證明了

「對於"幾乎所有"的塗色法都找得到 a 2a 3a 全同色」

這裡的幾乎所有是機率名詞:

https://zh.wikipedia.org/wiki/%E5%B9%BE%E4%B9%8E%E6%89%80%E6%9C%89

要注意到這個幾乎所有不代表全部, 因此不能做為存在性的否證

---
回到原題, 我自己也寫了支程式來跑原題了

程式給我的答案是只要考慮 2~18 的顏色即足夠證明原題

但條列下來的話中間的可能剩餘組數會高達兩百多組, 這顯然不能手寫...

--
 ◢ ˊ_▂▃▄▂_ˋ. ◣　　　　　 　　　　▅▅　▅▅　ι●╮　　 █▄▄▄▄▄   
▍./◤_▂▃▄▂_◥ \'▊ 　　ＨＡＲＵＨＩ █████　＜■┘  　 ▄▄▄▄▄▄▄ 
▎⊿ ◤◤◥█◥◥█Δ   　　ＩＳＭ　 　　By-gamejye　￠|\  　　▌▌▌▌▌▄▌▌
▏ζ(▏●‵◥′●▊)Ψ ▏　　 　　　 　　　　█　　　 ⊿Δ 　　▄▄▄  ▄▄▄▄
█/|▊ 〃  、  〃▋ |\ ▎　　　　　 　 　ハルヒ主義　　　  　　█▄▄▄█▄▄  
◥◥|◣   ‵′  ◢/'◢◢S.O.S 世界を大いに盛り上げるための涼宮ハルヒの団　　　 

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.195.39.85
※ 文章網址: https://www.ptt.cc/bbs/puzzle/M.1445449585.A.896.html
推 kirimaru73: 我補充一下 nobrother證明的結果可以這樣表示：
→ kirimaru73: 找一個不知道你要做啥的路人甲 請他替正整數隨機著色
→ kirimaru73: 著色結果中存在a 2a 3a同色              的機率 -> 1
→ kirimaru73: 這是對的 但原題目要面對的是一個全力妨礙你的上色者
推 nobrother: 了解了
→ kirimaru73: 而你要證明他不可能妨礙成功 而這就是問題所在
推 nobrother: 我以為k=(8/9)^n，當n可為無限大，k必等於0
→ wxtab019: 只是你的8/9 是隨機出來的 如果你自己去取那個1/9呢?
→ wxtab019: 就像說樂透頭獎機率是幾千萬分之一
→ wxtab019: 不過如果你一開始就可以自己選中獎號碼 那就可以變成1了
推 AlexCYW: 假如有個題目是a和a+1不能同色 用同樣的方法也是 (2/3)^n
→ AlexCYW: 但是只要用間隔著色就是反例了
→ LPH66: nobrother 推文講的 k->0 即是那個"幾乎所有"的概念
→ LPH66: 但那永遠是機率, 不是存在性證明
推 kirimaru73: 例如 幾乎所有正妹都會拒絕告白 成功率->0
→ kirimaru73: 但這不能作為一定沒有希望的證明
推 DreamYeh: 樓上別這樣啊啊啊
推 newacc: XDDDDDDDDDD