[心得] 非自消盤面最高首消combo數的最小值

看板ToS作者 (QQ)時間9年前 (2015/03/15 14:07), 9年前編輯推噓90(93推 3噓 33→)
留言129則, 80人參與, 最新討論串1/2 (看更多)
ptt還我稿費啊!!! 期望值打那麼辛苦被你吃了!!! ( ‵□′)───C＜─___-)||| --------------------------發洩完畢---------------------------------------- 《問題》任給一個非自消盤面，其最高首消數至少幾combo呢？ 《答案》至少４combo，若剛好４combo則此盤面恰好是同色珠20個、其他5色珠各2個。 因此若非上述盤面，則至少５combo。 解釋：1.非自消盤面：盤面沒有３連珠。 2.最高首消combo數：只算首消且取最大可能，不算疊珠。 3.舉例：15暗、3水、3火、6木、3光 ●●●●●● ●●●●●● ●●●●●● 最高首消 ●●●●●● ●●●●●● → ●●●●●● ●●●●●● ●●●●●● ●●●●●● ●●●●●● 非自消盤面 最高首消10combo 《發現經過》：（以下所稱"盤面"皆為非自消盤面、最多6色珠、格式：橫6 X 縱5） 首先 aardvark 在...被ptt吃掉的那篇推文提出：盤面最多可容納多少個同色珠？ 之後 wlkb0000 給出了一個20個同色珠的盤面 http://tinyurl.com/lclq5yx （題外話：這盤面幫助很大，不僅提供了 aardvark 的問題的最大值猜測，而且在本定理 也提供了最小值的猜測。），因此去猜測不可能存在21個以上（含）同色珠的盤面， 也順利證完。 再來回到原本問題，我很久之前就自問過了，但是情況太複雜了，就沒有繼續想。但經由 aardvark 的問題解決後，以及 wlkb0000 這個盤面，讓原本問題燃起希望，讓我猜測 這個最高首消最小值就是4（能證出真的存在某盤面的最高首消combo剛好就是4最好， 即是下方第2點的情況），只要把其他10個雜色珠各做2個。因此證明只剩兩個步驟： 1.不存在最高首消0,1,2,3combo的盤面。 2.20個同色珠，其他10雜色珠，同色珠最高切成首消4combo。 （不管雜色珠combo，因為5色皆2個不會提供額外combo。） 起初我先想第2點，覺得第1點比較難，而昨晚 wlkb0000 說第1點已有idea，因此我專攻 第2點，但試了很多分析，包括：思考隔離combo的關鍵、先放20個同色珠、先放其他10個 雜色珠、每1combo的珠量與排法、與18個同色珠盤面做比較、差1個雜色珠的combo數影響 、差1個同色珠的combo數影響.....族繁不及備載，失敗！ 後來我轉向第1點，果然蠻好證的，但還是要以第2點為已知....所以問題還是回到第2點。 之後睡前被我找到一個關鍵：逆向操作，以15個同色珠為比較對象，成功！ 最後加碼證出，最高首消數為4combo的盤面只有這個情況：20個同色珠，10個雜色 珠各2個。也就是說，只要盤面不是20,2,2,2,2,2這個情況，一定最高首消5 combo以上（含）。 不免俗的...特別強調一下 ============================================================================= === 下一頁開始可能導致任何不適感，慎入！=== ============================================================================= ============================================================================= === 下一頁開始可能導致任何不適感，慎入！=== ============================================================================= ============================================================================= === 下一頁開始可能導致任何不適感，慎入！=== ============================================================================= 【定義】 1.以下所指"盤面"皆為非自消盤面。 2.以下所寫A,B,C,D,E,F分別代表6色珠以及其個數。 3.以下所寫X不一定同色。 　　　　 4.以下所寫"以上"、"以下"皆代表"含"。 【定理】（A-W-Z六色盤面首消定理） 任一非自消盤面的最高首消combo數最少有4combo。 且剛好4combo的時候 若且為若 珠量分佈為：20個同色珠、其他5色珠各2個。 誠如之前所說，需要先證明一些引理才能證明這個定理。 【引理１】15個同色珠，其他15雜色珠，同色珠最高切成首消5combo， 且達5combo時排法只有兩種： （以A為15同色珠、X為其他雜色珠，X間不一定同色） （一）AAAXXX （二）XXXAAA XXXAAA AAAXXX AAAXXX XXXAAA XXXAAA AAAXXX AAAXXX XXXAAA 證明：若6combo以上則此同色珠數量為18個以上，矛盾。 因此最多5combo以上，而由（一）、（二）印證了5combo的存在性。 至於只有這兩種排法的證明再此不贅述，先排除縱向的方式比較好證，之後窮舉。 【引理２】（即為 aardvark 的問題與證明。） 盤面每色珠數量為20個以下（等價於：盤面任5色珠數量總和10個以上） 證明：等價敘述顯而易見，僅證明前者。 假設存在某色珠A，數量為21個以上， 觀察盤面： 111222 333444 555666 777888 999VVV 則111中必存在1個色珠不為A，否則會構成自消盤面，同理其他9組都含1個色珠 不為A，因此至少含有10個色珠不為A，即A色珠數量為20個以下，矛盾。 【引理３】盤面20個同色珠，同色珠最高切成首消4combo。 證明：假設其最高首消combo數為5以上（令20個同色珠為A） 則A色珠分布情形為： 3 3 3 3 3 5 其中：1."3"代表至少3個為1combo消除 2."5"代表：(a)可能些許自體形成消除 (b)可能些許分給"3"一起消除 (c)可能些許沒被消除 再來即是顯而易見的關鍵：將此5個珠子用B色珠代替，A色珠首消combo數不變。 因此形成了：15個A色珠且A色珠首消5combo的A色珠不自消盤面。 接著利用【引理１】，只有（一）、（二）兩種可能，只討論（一），（二）同理 　　　 　　　由（一）的形式：AAAXXX XXXAAA AAAXXX XXXAAA AAAXXX 　　　　 得知只要把"那5個以B色珠代替"的珠子還原回去A，即可得到原來盤面，但換回去 的過程不可減少A色珠首消combo數。 由上圖紅色的X註明是換了會減少A色珠首消combo數的位置，得知僅剩4位置可容納 5個A色珠，矛盾。 以上3個引理證明完畢，接著可以證明本定理。 【定理證明】假設存在某盤面其最高首消combo數為n ┌───┐ │Step I│ └───┘ (1) n=0：則A,B,C,D,E,F≦2，矛盾。 (2) n=1：不失一般性，假設此1combo正是A，則A≧3 且B,C,D,E,F≦2（若否，不失一般性假設B≧3，可排成：AAABBB XXXXXX XXXXXX XXXXXX XXXXXX 至少2combo，矛盾。） 　　　　 因此B+C+D+E+F≦10，得知A≧20，再由【引理２】知道A=20，再由【引理３】 　　　　 知道至少4combo，矛盾。 （但是從B,C,D,E,F≦2其實可得此盤面正是A=20,B=C=D=E=F=2，因此剛好4combo ，因為雜色珠不會貢獻combo。）　　 (2) n=2： (a) 2combo同色：不失一般性，假設此2combo正是A，則A≧6 且B,C,D,E,F≦2 （若否，不失一般性假設B≧3，可排成： AAAXXX 其中X必有非A色珠塞入，因為【引理２】確保A以外的色珠 BBBXXX 為10個以上，目前用了X+B=4，因此至少3combo，矛盾。 AAAXXX XXXXXX XXXXXX ） 因此B+C+D+E+F≦10，得知A≧20，再由【引理２】知道A=20， 再由【引理３】知道至少4combo，矛盾。 (b) 2combo異色：不失一般性，假設此2combo正是A,B，則A,B≧3 且C,D,E,F≦2 （若否，不失一般性假設C≧3，可排成：AAABBB CCCXXX XXXXXX XXXXXX XXXXXX 　　　　　　　　　　 　至少3combo，矛盾。） 因此C+D+E+F≦8，但A,B≦5（若否，則回到(a)，矛盾。） 因此A+B+C+D+E+F≦18，矛盾。　　　　　 (2) n=3： (a) 3combo同色：不失一般性，假設此3combo正是A，則A≧9 且B,C,D,E,F≦2 （若否，不失一般性假設B≧3，可排成： AAAXXX 其中X必有非A色珠塞入，因為【引理２】確保A以外的色珠 BBBXXX 為10個以上，目前用了X+B=8，因此至少4combo，矛盾。 AAAXXX XXXXXX AAAXXX ） 因此B+C+D+E+F≦10，得知A≧20，再由【引理２】知道A=20， 再由【引理３】知道至少4combo，矛盾。 (b) 2同色1異色：不失一般性，假設此2combo正是A，1combo正是B，則A≧6，B≧3 且C,D,E,F≦2 （若否，不失一般性假設C≧3，可排成： AAAXXX 其中X必有非A色珠塞入，因為【引理２】確保A以外的色珠 BBBXXX 為10個以上，目前用了X+B+C=8，因此至少4combo，矛盾。 AAAXXX CCCXXX XXXXXX ） 因此C+D+E+F≦8，但A≦8（若否，則回到(a)，矛盾。） 因此得B≧14≧9，回到(a)，矛盾。 (c) 3combo異色：不失一般性，假設此3combo正是A,B,C，則A,B,C≧3 且D,E,F≦2 （若否，不失一般性假設D≧3，可排成：AAAXXX BBBXXX CCCXXX DDDXXX XXXXXX 至少4combo，矛盾。） 因此D+E+F≦6，但A,B,C≦5（若否，則回到(b)，矛盾。） 因此A+B+C+D+E+F≦21，矛盾。 ┌────┐ │Step II │ └────┘ 從以上討論加上【引理３】可知，任一非自消盤面的最高首消combo數最少有4combo，且 確實存在盤面剛好是4combo。接著證明最後一個部分： 剛好4combo的時候 若且為若 珠量分佈為：20個同色珠、10個雜色珠各2個。 (1) <=：即為【引理３】 (2) =>： (a) 4combo同色：不失一般性，假設此4combo正是A，則A≧12 且B,C,D,E,F≦2 （若否，不失一般性假設B≧3，可排成： AAAXXX 其中X必有非A色珠塞入，因為【引理２】確保A以外的色珠 BBBAAA 為10個以上，目前用了X+B=9，因此至少5combo，矛盾。 AAAXXX XXXXXX AAAXXX ） 因此B+C+D+E+F≦10，得知A≧20，再由【引理２】知道A=20， 但是從B,C,D,E,F≦2其實可得此盤面正是A=20,B=C=D=E=F=2。 (b) 3同色1異色：不失一般性，假設此3combo正是A，1combo正是B，則A≧9，B≧3 且C,D,E,F≦2 （若否，不失一般性假設C≧3，可排成： AAAXXX 其中X必有非A色珠塞入，因為【引理２】確保A以外的色珠 BBBXXX 為10個以上，目前用了X+B+C=8，因此至少5combo，矛盾。 AAAXXX CCCXXX AAAXXX ） 因此C+D+E+F≦8，但A≦11（若否，則回到(a)，矛盾。） 因此得B≧11≧6，可排成：AAAXXX BBBAAA AAAXXX BBBXXX XXXXXX 其中X必有非A色珠塞入，因為【引理２】確保A以外的色珠為10個 以上，目前用了X+B=8，因此至少5combo，矛盾。 (c) 2同色2同色：不失一般性，假設此2combo各是A,B，則A,B≧6 且C,D,E,F≦2 （若否，不失一般性假設C≧3，可排成：AAAXXX BBBCCC AAAXXX BBBXXX XXXXXX 至少5combo，矛盾。） 因此C+D+E+F≦8，但A,B≦8（若否，則回到(b)，矛盾。） 因此A+B+C+D+E+F≦24，矛盾。 (d) 2同色2異色：不失一般性，假設此2combo是A，1combo各是B,C，則A≧6，B,C≧3 且D,E,F≦2 （若否，不失一般性假設D≧3，可排成：AAAXXX BBBDDD AAAXXX CCCXXX XXXXXX 至少5combo，矛盾。） 因此D+E+F≦6，但A≦8（若否，則回到(b)，矛盾。） 且B,C≦5（若否，則回到(c)，矛盾。） 因此A+B+C+D+E+F≦24，矛盾。 (e) 4combo異色：不失一般性，假設此4combo正是A,B,C,D，則A,B,C,D≧3 且E,F≦2 （若否，不失一般性假設E≧3，可排成：AAAXXX BBBXXX CCCXXX DDDXXX EEEXXX 至少5combo，矛盾。） 因此E+F≦4，但A,B,C,D≦5（若否，則回到(d)，矛盾。） 因此A+B+C+D+E+F≦24，矛盾。 綜合以上討論，只有(a)情況會發生。 ┌───┐ │Q.E.D │ └───┘ 個人有感： 其實證出這個還蠻開心的，如果你只是看了這個定理的結果或是證明覺得OK，其實應該 沒啥興奮感。我好久前就是遇到想到這個問題，但是不知道從何下手，摸不著頭緒，覺得 從哪邊討論都很累，後來是由於a大問的問題還有磨神那個盤面才有方向。只是中途又 卡在"20個同色珠，其他10雜色珠，同色珠最高切成首消4combo。"這關鍵又灰心了一陣子 試過很多方法都無法討論完善，正想著放棄的時候，讓我想到填回去的方法，整個就出來 了。 雖然寫定理/證明的順序是先引理再定理，但是思考邏輯完全是反過來的，看是需要什麼 樣的條件才去想有沒有這樣的引理。 不過很靠運氣的是...如果沒有a大問的問題還有磨神那個盤面真的就無法了...而且從這 定理會發現，很多矛盾都是導向20,2,2,2,2,2這分佈，而且這分佈又是唯一會導致4combo 這有點奇妙啊！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.231.118.71 ※ 文章網址: https://www.ptt.cc/bbs/ToS/M.1426399643.A.48F.html
推
03/15 14:09, , 1F
我走錯板了嗎XD
03/15 14:09, 1F
推
03/15 14:10, , 2F
推認真
03/15 14:10, 2F
推
03/15 14:10, , 3F
快推 不然別人會以為我看不懂
03/15 14:10, 3F
推
03/15 14:10, , 4F
快推以免...........算了，我承認我看不懂......
03/15 14:10, 4F
推
03/15 14:12, , 5F
承認看不懂+1
03/15 14:12, 5F
推
03/15 14:12, , 6F
這是中文嗎?
03/15 14:12, 6F
推
03/15 14:12, , 7F
...機械系有點無法= =
03/15 14:12, 7F
推
03/15 14:13, , 8F
我數學不好
03/15 14:13, 8F
推
03/15 14:14, , 9F
看不懂.....有懶人包嗎
03/15 14:14, 9F
?? 懶人包就是第一頁呀 非自消盤面（沒有３連珠）至少都能首消4C 而且會發生4C的只有一種情況，就是珠子分部20,2,2,2,2,2 是不是"非自消盤面"太敖口?? ※ 編輯: znmkhxrw (61.231.118.71), 03/15/2015 14:17:11
推
03/15 14:17, , 10F
哩洗勒供瞎小...................
03/15 14:17, 10F
推
03/15 14:18, , 11F
好喔
03/15 14:18, 11F
推
03/15 14:19, , 12F
嗯嗯嗯 跟我想的一樣
03/15 14:19, 12F
推
03/15 14:19, , 13F
可以講中文嗎
03/15 14:19, 13F
推
03/15 14:21, , 14F
快推不然別人會以為我看不懂 樓下也快推
03/15 14:21, 14F
跪求中文懶人包...
推
03/15 14:22, , 15F
哈哈哈哈 盤面極衰化嗎
03/15 14:22, 15F
※ 編輯: znmkhxrw (61.231.118.71), 03/15/2015 14:23:35
→
03/15 14:23, , 16F
一言以蔽之 盤面再怎麼鳥 轉不出4C都是操作者的問題(咦
03/15 14:23, 16F
我就是怕只打"盤面"，到時候一堆人問全版同色之類的這種... 我已經用"非自消"來表示：非轉屬、非龍刻的這種沒有３連珠的盤面
推
03/15 14:23, , 17F
完了 又走錯版了
03/15 14:23, 17F
※ 編輯: znmkhxrw (61.231.118.71), 03/15/2015 14:24:56
推
03/15 14:23, , 18F
重點是?
03/15 14:23, 18F
→
03/15 14:24, , 19F
所謂的專業就是要讓一般小魯都能聽得懂才叫專.... (毆
03/15 14:24, 19F
推
03/15 14:25, , 20F
懶人包就是沒禁珠的話 任意盤面不開轉珠最少都會有4C
03/15 14:25, 20F
有無禁珠沒差~前提已經含最多6色珠，只是"非自消"改成白話的不開轉珠/龍刻 好像比較像... 可是我下面有解釋說"不自消"就是盤面上沒有3連珠... 前面一堆不懂的可以提一下哪邊嗎???
推
03/15 14:26, , 21F
ヽ( ・∀・)ノ 樓下你懂嗎
03/15 14:26, 21F
推
03/15 14:27, , 22F
我不懂ヾ(*′∀‵*)ﾉ
03/15 14:27, 22F
推
03/15 14:27, , 23F
我end了XD
03/15 14:27, 23F
我精華都在第一頁啊QQ ※ 編輯: znmkhxrw (61.231.118.71), 03/15/2015 14:30:04
推
03/15 14:28, , 24F
證明看不懂QWQ
03/15 14:28, 24F
推
03/15 14:30, , 25F
懶人包:ptt還我稿費
03/15 14:30, 25F
推
03/15 14:30, , 26F
感到嚴重的不適感
03/15 14:30, 26F
推
03/15 14:30, , 27F
看不懂+1
03/15 14:30, 27F
推
03/15 14:34, , 28F
水火木光暗各ㄧ顆，其他是心珠，這算非自消盤面嗎
03/15 14:34, 28F
不是阿 這樣心珠有25顆，一定有3連心
→
03/15 14:35, , 29F
只大概看得懂首消基本4C 然後證明看不懂 好多AABB...
03/15 14:35, 29F
定義那邊有寫AB是啥米碗糕 ※ 編輯: znmkhxrw (61.231.118.71), 03/15/2015 14:36:32
推
03/15 14:37, , 30F
認真給推, 看完了, 應該無誤
03/15 14:37, 30F
還有 64 則推文
還有 20 段內文
→
03/15 16:36, , 95F
只是這狀況發生在大量同一屬珠的時候
03/15 16:36, 95F
推
03/15 16:45, , 96F
姬式盾就算圍城也消不掉 0C正解 XD
03/15 16:45, 96F
推
03/15 16:45, , 97F
一堆人連懶人包都看不懂，太超過了吧...
03/15 16:45, 97F
推
03/15 16:59, , 98F
推推~
03/15 16:59, 98F
推
03/15 17:32, , 99F
end給推
03/15 17:32, 99F
推
03/15 17:38, , 100F
頭好痛@@
03/15 17:38, 100F
推
03/15 17:45, , 101F
無感end，但上色打得辛苦給推
03/15 17:45, 101F
推
03/15 17:47, , 102F
我的答案跟小當家的一樣
03/15 17:47, 102F
小當家是誰?
推
03/15 18:02, , 103F
快推不然別人會以為我連懶人包都看不懂...
03/15 18:02, 103F
推
03/15 18:02, , 104F
跟我想的一樣
03/15 18:02, 104F
推
03/15 18:14, , 105F
我連標題都看不懂
03/15 18:14, 105F
推
03/15 18:46, , 106F
論文推
03/15 18:46, 106F
推
03/15 19:00, , 107F
Q博今天又發paper惹
03/15 19:00, 107F
(．＿．?)
推
03/15 19:44, , 108F
推詳盡...^^
03/15 19:44, 108F
謝謝你一開始的問題XDDDD
→
03/15 19:47, , 109F
我需要翻譯蒟蒻！！！！
03/15 19:47, 109F
我都習慣吃米糕
推
03/15 19:52, , 110F
還我晚餐，吐光光。。。
03/15 19:52, 110F
推
03/15 20:04, , 111F
連問題都看不懂的人應該很多..簡單來說:盤面給你的珠子
03/15 20:04, 111F
→
03/15 20:07, , 112F
讓你再怎樣轉珠 排珠都沒辦法作出更多的首消COMBO
03/15 20:07, 112F
嗆我中文不好嗆夠了沒 ( ‵□′)───C＜─___-)||| ※ 編輯: znmkhxrw (61.231.118.71), 03/15/2015 20:29:43
推
03/15 20:37, , 113F
請講人話
03/15 20:37, 113F
→
03/15 20:39, , 114F
我覺得iamsocool下的題目還是不夠精準XDDD
03/15 20:39, 114F
→
03/15 20:41, , 115F
任何自然盤面都有首消COMBO"上限"，找出此上限的最小值
03/15 20:41, 115F
→
03/15 20:42, , 116F
所以本文先找自然盤面(最多20顆同色)，再求他的上限
03/15 20:42, 116F
→
03/15 20:43, , 117F
然後再證明此上限(4c)為最小值
03/15 20:43, 117F
推
03/15 22:57, , 118F
這兒是數學版嗎？
03/15 22:57, 118F
噓
03/15 23:22, , 119F
媽 我在這~~~
03/15 23:22, 119F
推
03/15 23:32, , 120F
推演過程給數學系的看 , 懶人包結論才是給版眾看的
03/15 23:32, 120F
推
03/15 23:34, , 121F
用心推演給推
03/15 23:34, 121F
推
03/16 00:30, , 122F
看不懂只好推了～
03/16 00:30, 122F
推
03/16 05:28, , 123F
完全看不懂啊....
03/16 05:28, 123F
噓
03/16 08:59, , 124F
連問題都問不清楚
03/16 08:59, 124F
推
03/16 10:44, , 125F
正常盤面下，如果空轉後所有盤面符石都還是空轉前的位
03/16 10:44, 125F
→
03/16 10:45, , 126F
置，並不會消到珠子，這個就是非自消盤面嗎?
03/16 10:45, 126F
推
03/16 12:28, , 127F
樓上 是
03/16 12:28, 127F
推
03/16 15:10, , 128F
雖然不懂但是推認真XD
03/16 15:10, 128F
推
03/17 18:18, , 129F
我....我看不懂(淚奔
03/17 18:18, 129F
‣ 更多 znmkhxrw 的文章
文章代碼(AID): #1L1I6RIF (ToS)
‣ 更多 znmkhxrw 的文章
文章代碼(AID): #1L1I6RIF (ToS)