puzzle 板


LINE

※ 引述《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://webptt.com/m.aspx?n=bbs/puzzle/M.1701373503.A.17C.html
1F:推 DreamYeh: 推 也發表一下你八顆電池解法吧~ 12/01 08:45
一開始的想法: 兩兩分成四組 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 的另一顆也一定是好的,所以會成功 其實就相當於本文中 △ △ ─ 的解法
2F:推 Django: 推 我的八顆解法是 ABC兩兩各試一次(3次) DEF兩兩各試一次 12/02 02:18
3F:→ Django: (3次) 如果都失敗 代表剩下兩顆都是好的 必成功(第七次) 12/02 02:18
4F:→ arthurduh1: 用圖來看會發現只是順序上的差異 12/02 03:59
5F:→ arthurduh1: 所有 N 都只有這唯一的圖符合條件 12/02 04:00
訂正個錯誤,沒考慮到邊可能重複算 ※ 編輯: arthurduh1 (140.109.73.249 臺灣), 12/06/2023 21:54:19







like.gif 您可能會有興趣的文章
icon.png[問題/行為] 貓晚上進房間會不會有憋尿問題
icon.pngRe: [閒聊] 選了錯誤的女孩成為魔法少女 XDDDDDDDDDD
icon.png[正妹] 瑞典 一張
icon.png[心得] EMS高領長版毛衣.墨小樓MC1002
icon.png[分享] 丹龍隔熱紙GE55+33+22
icon.png[問題] 清洗洗衣機
icon.png[尋物] 窗台下的空間
icon.png[閒聊] 双極の女神1 木魔爵
icon.png[售車] 新竹 1997 march 1297cc 白色 四門
icon.png[討論] 能從照片感受到攝影者心情嗎
icon.png[狂賀] 賀賀賀賀 賀!島村卯月!總選舉NO.1
icon.png[難過] 羨慕白皮膚的女生
icon.png閱讀文章
icon.png[黑特]
icon.png[問題] SBK S1安裝於安全帽位置
icon.png[分享] 舊woo100絕版開箱!!
icon.pngRe: [無言] 關於小包衛生紙
icon.png[開箱] E5-2683V3 RX480Strix 快睿C1 簡單測試
icon.png[心得] 蒼の海賊龍 地獄 執行者16PT
icon.png[售車] 1999年Virage iO 1.8EXi
icon.png[心得] 挑戰33 LV10 獅子座pt solo
icon.png[閒聊] 手把手教你不被桶之新手主購教學
icon.png[分享] Civic Type R 量產版官方照無預警流出
icon.png[售車] Golf 4 2.0 銀色 自排
icon.png[出售] Graco提籃汽座(有底座)2000元誠可議
icon.png[問題] 請問補牙材質掉了還能再補嗎?(台中半年內
icon.png[問題] 44th 單曲 生寫竟然都給重複的啊啊!
icon.png[心得] 華南紅卡/icash 核卡
icon.png[問題] 拔牙矯正這樣正常嗎
icon.png[贈送] 老莫高業 初業 102年版
icon.png[情報] 三大行動支付 本季掀戰火
icon.png[寶寶] 博客來Amos水蠟筆5/1特價五折
icon.pngRe: [心得] 新鮮人一些面試分享
icon.png[心得] 蒼の海賊龍 地獄 麒麟25PT
icon.pngRe: [閒聊] (君の名は。雷慎入) 君名二創漫畫翻譯
icon.pngRe: [閒聊] OGN中場影片:失蹤人口局 (英文字幕)
icon.png[問題] 台灣大哥大4G訊號差
icon.png[出售] [全國]全新千尋侘草LED燈, 水草

請輸入看板名稱,例如:Gossiping站內搜尋

TOP