Re: [問題] 工具人悲歌-裝填電池問題
看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者arthurduh1 (arthurduh1)時間11月前 (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
推
12/01 08:45,
11月前
, 1F
12/01 08:45, 1F
一開始的想法:
兩兩分成四組 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 的另一顆也一定是好的,所以會成功
其實就相當於本文中 △ △ ─ 的解法
推
12/02 02:18,
11月前
, 2F
12/02 02:18, 2F
→
12/02 02:18,
11月前
, 3F
12/02 02:18, 3F
→
12/02 03:59,
11月前
, 4F
12/02 03:59, 4F
→
12/02 04:00,
11月前
, 5F
12/02 04:00, 5F
訂正個錯誤,沒考慮到邊可能重複算
※ 編輯: arthurduh1 (140.109.73.249 臺灣), 12/06/2023 21:54:19
討論串 (同標題文章)
本文引述了以下文章的的內容:
完整討論串 (本文為第 2 之 3 篇):
puzzle 近期熱門文章
PTT遊戲區 即時熱門文章
33
117
81
372
9
18