作者LPH66 (-6.2598534e+18f)
看板puzzle
標題Re: [問題] 將正整數著色
時間Thu Oct 22 01:46:22 2015
如果題目改問 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://webptt.com/m.aspx?n=bbs/puzzle/M.1445449585.A.896.html
1F：推 kirimaru73: 我補充一下 nobrother證明的結果可以這樣表示： 10/22 02:06
2F：→ kirimaru73: 找一個不知道你要做啥的路人甲 請他替正整數隨機著色 10/22 02:07
3F：→ kirimaru73: 著色結果中存在a 2a 3a同色 的機率 -> 1 10/22 02:07
4F：→ kirimaru73: 這是對的 但原題目要面對的是一個全力妨礙你的上色者 10/22 02:08
5F：推 nobrother: 了解了 10/22 02:08
6F：→ kirimaru73: 而你要證明他不可能妨礙成功 而這就是問題所在 10/22 02:08
7F：推 nobrother: 我以為k=(8/9)^n，當n可為無限大，k必等於0 10/22 02:10
8F：→ wxtab019: 只是你的8/9 是隨機出來的 如果你自己去取那個1/9呢? 10/22 06:05
9F：→ wxtab019: 就像說樂透頭獎機率是幾千萬分之一 10/22 06:06
10F：→ wxtab019: 不過如果你一開始就可以自己選中獎號碼 那就可以變成1了 10/22 06:06
11F：推 AlexCYW: 假如有個題目是a和a+1不能同色 用同樣的方法也是 (2/3)^n 10/22 10:37
12F：→ AlexCYW: 但是只要用間隔著色就是反例了 10/22 10:37
13F：→ LPH66: nobrother 推文講的 k->0 即是那個"幾乎所有"的概念 10/22 17:39
14F：→ LPH66: 但那永遠是機率, 不是存在性證明 10/22 17:40
15F：推 kirimaru73: 例如 幾乎所有正妹都會拒絕告白 成功率->0 10/22 17:53
16F：→ kirimaru73: 但這不能作為一定沒有希望的證明 10/22 17:53
17F：推 DreamYeh: 樓上別這樣啊啊啊 10/23 00:14
18F：推 newacc: XDDDDDDDDDD 10/24 01:01