Re: [問題] 工具人悲歌-裝填電池問題

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者arthurduh1 (arthurduh1)時間4月前 (2023/12/01 03:45)推噓2(2推 0噓 3→)

留言5則, 3人參與討論串2/3 (看更多)

※ 引述《DreamYeh (天使)》之銘言： : 你和心儀已久的正妹女生去登山，經過一個黑暗的隧道， : 忽然照明熄滅了，正妹害怕尖叫。 : 你趕緊有男子氣概地說：「別怕！我有準備手電筒！」 : 結果一拿出手電筒，卻發現電池沒電，正妹嘆一口氣。 : 你不慌不忙說：「別怕！我有準備備用電池！還準備了 : 四顆！」 : 慌忙拆開手電筒後，你手電筒裡那兩顆電池卻混入了你 : 備用的電池堆中。你趕緊整理一下，發現背包裡居然有 : 八顆電池，正妹又嘆一口氣。 : 你只得趕緊回想，你確定新買了四顆電池是好的，另外 : 兩顆是手電筒掉出的，還有兩顆....啊！是之前留下的 : 電池，大概也沒電了....想這麼多幹嘛於事無補。 : 你要測試電池是否好的，只有一個辦法，就是把電池裝 : 入手電筒內（一次要裝兩顆），開啟手電筒，只有兩顆 : 電池都是好的才能使手電筒亮。 : 然而在黑暗之中，把電池裝入手電筒、並打開是很耗時 : 的。你評估一下正妹的怒氣值..... : 你只能裝七次，裝電池（並打開手電筒）到第七次，都 : 沒成功，女生就會失去耐心地賞你一巴掌離去。 : 請問你要採取什麼策略？（想到七次就想看有沒有六次 : 解或證明無法更簡單） : 挑戰題：2N個電池、N個是好的，則你需要最少幾次？因為只有失敗與成功兩種結果我們相當於是按照某一套固定的配對法試過一遍，甚至先後次序也沒差（嘗試結果不會影響策略，因為成功之前一定全部都是失敗）問題可抽象化成：建構一個 2N 個頂點的圖，邊越少越好，使得其 independent number α < N 頂點就代表電池每條邊的頂點則是對應我們要拿去嘗試的電池配對這樣的策略如果試不出來，代表可以找到 N 個頂點（好電池）使其兩兩不相鄰，也就是 independent set 而 independent number α < N，就表示任取 N 個頂點必定會有其中兩者相鄰這樣的話就比較好想了例如 N = 4 時可以採用這樣的圖 △　△　─ 還可推廣到 △　△　─　─　…　─ 也就是 2N 顆電池，可以用 N+3 次挑出兩顆好的因為要兩個三角形，所以 N = 2 時不成立實際上也能發現 N = 2 時需要全試過一遍，也就是 6 次證明為最佳： α 有下界 α≧(2v-e)/3，v 是頂點數，e 是邊數由於 N 會大於能成功挑選的圖的 α，也就大於至少為 (4N-e)/3 的整數便得到 e 至少要 N+3 了至於該下界的證明，我自己試著造了一個：採取貪婪法建造圖 G 的一個 independent set S(G) 每次挑選所剩的圖的頂點中 degree 最小一個 v，放進 S 中並且刪除 v、其鄰邊、其鄰邊相連的頂點與這些頂點的鄰邊令所剩的圖為 G'，根據對頂點個數的歸納法，我們假設其符合 |S(G')| ≧ ( 2 v(G') - e(G') )/3 令 deg v = d，有 v(G) - v(G') = d+1 (v 和其 d 個鄰居) 以及 e(G) - e(G') ≧ d+d(d-1)/2 (v 有 d 條鄰邊，v 的鄰居每個至少再添 d-1 條，但這 d-1 條可能跟另一個鄰居重複) 綜上三式 |S(G)| = |S(G')| + 1 ≧ ( 2 v(G') - e(G') )/3 + 1 ≧ ( 2 (v(G)-d-1) - e(G) + d+d(d-1)/2 )/3 + 1 ＝ ( 2 v(G) - e(G) + (d^2 - 3d + 2)/2 )/3 ≧ ( 2 v(G) - e(G) )/3 歸納法過關由於可以造出頂點數 ≧ ( 2 v(G) - e(G) )/3 的 independent set S(G) 故其上界 α(G) ≧ ( 2 v(G) - e(G) )/3 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.109.73.249 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/puzzle/M.1701373503.A.17C.html

推

DreamYeh

12/01 08:45, 4月前 , 1^F

12/01 08:45, 1^F

一開始的想法：兩兩分成四組 A, B, C, D A, B, C 各裝一次 [3 次] 若都不亮，則 Case 1: 四組都恰含一顆好的電池 Case 2: A, B, C 其中一組全壞，其他兩組都恰含一顆好的電池，D 全是好的接著拿 A 中兩顆去跟 D 的其中一顆一一配對 [2 次] 若都不亮 Case 1: D 選到的是壞的 Case 2: A 全是壞的最後拿 B 中兩顆去跟 D 中另一顆一一配對 [2 次] B 中至少有一顆好的，D 的另一顆也一定是好的，所以會成功其實就相當於本文中 △　△　─ 的解法