作者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/cn.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