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

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者DreamYeh (天使)時間1年前 (2023/12/04 21:25)推噓1(1推 0噓 5→)

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

※ 引述《DreamYeh (天使)》之銘言： : 你要測試電池是否好的，只有一個辦法，就是把電池裝 : 入手電筒內（一次要裝兩顆），開啟手電筒，只有兩顆 : 電池都是好的才能使手電筒亮。 : 然而在黑暗之中，把電池裝入手電筒、並打開是很耗時 : 的。你評估一下正妹的怒氣值..... : 你只能裝七次，裝電池（並打開手電筒）到第七次，都 : 沒成功，女生就會失去耐心地賞你一巴掌離去。 : 請問你要採取什麼策略？（想到七次就想看有沒有六次 : 解或證明無法更簡單） : 挑戰題：2N個電池、N個是好的，則你需要最少幾次？給一下這一題的預設答案：將八顆電池，以三個為一組分組，假設為 A B C，其中AB有三顆電池，C有兩顆。挑Ａ這一組，三顆電池，任選兩顆輪流測試，如此共會測試三次。共三次。若都沒有亮，挑Ｂ這一組，同樣三顆電池，任選兩顆輪流測試，如此共會測試三次。共六次。若仍然都沒有亮，則挑Ｃ這一組，也就是第七次測試，必亮。解析：當Ａ這一組怎麼樣都沒亮時，則可能Ａ這一組包含兩個、或三個壞電池。如果Ａ包含三個壞電池，Ｂ最多含一個壞電池，則Ｂ這一組三顆彼此測試，必定能亮。如果Ａ、Ｂ都進行「三顆輪流測試」，都是不亮，必定是能是Ａ、Ｂ都含有兩個壞電池。。此時，Ｃ只能是兩個好電池，測Ｃ組必亮。挑戰題：若有2N個電池，內有N個好電池，則最佳策略為N+3次可測得。方法是四顆電池，則需測滿四取二的所有組合六顆電池或以上。則 1.三個為一組為A、三個為一組為B，其餘兩個兩個為一組 2.A組內任選兩個進行交互測試，若亮則結束測試。如此三次組內測完 3.B組內任選兩個進行交互測試，若亮則結束測試。如此三次組內測完 4.第三組開始，兩個為一組進行測試，若亮則結束測試，不亮則繼續下一組 5.如此測試到亮為止 6顆電池，最多測 3 + 3 = 6次 8顆電池，最多測 3+3+1 = 7次 10顆電池，最多測 3+3+2 = 8次 ......以此類推證明：由於聽眾是國中生，因此盡可能不用圖論，雖然其實也是講圖論那一套.... case 1.六顆電池情況無論用什麼策略，我們嘗試將「彼此之間不互相測試的集合」進行分組。例如策略為：先測試其中兩顆電池（標為AB）再將剩下四顆電池彼此拿來測試一次（CDEF）後面測試AB都不參與CDEF這組別測試，則將 AB列為第一組 CDEF列為第二組那這樣，是否允許有第三組呢？答案是不允許的。因為假如有三組（至少含一個），彼此互相不進行測試。則好的電池若剛好是三組內各有一顆，根據定義，不可能測到，此策略失敗。那如果只有一組，組內所有電池都彼此參與測試呢？則該組含有六顆電池，最少的測試策略為 A-B-C-D-E （即A、B相測試，B、C相測試....、F可跟BCDE接）無論F跟誰接都一樣，這樣至少有五次測試。但這種情況，若A、C、E剛好為好的電池，則此策略將不能測到若需考慮，則必定需要增加測試狀況，也就是六次以上（雖然我們其實知道只有一組、六次測試也是不行，但不需用到此）那如果有兩組呢？考慮一組至少有兩個電池，那可能為 4 - 2 或 3-3 在4-2這一種分組狀況，若四個電池那包，有兩顆以上電池未彼此測試（圖形上畫四顆為成長方形、另兩顆彼此相連）則挑選該兩顆，與兩顆一組的電池選一顆，假如這三顆都是好的電池，此種策略無法挑出該狀況最後，如果是三個-三個分兩組測試。同樣，若其中有一組，有兩顆以上電池未彼此測試（圖形上畫三顆排成一列）則選該兩顆、另外一組任選一顆，可發現此策略依舊會無法挑選出。因此只有分兩組、每組三顆電池每一組都是「三顆之間彼此測試」，才能保證所有情況都能測出 case 2.6+2顆電池情況證明六顆電池，必須測六次後，後面反而好證明了。當我們加入「一好一壞的兩顆電池」則非常顯然，無論什麼策略，該兩顆電池都必須參與測試，也就是少也要多測一次，因此 6顆電池，最多測 3 + 3 = 6次 8顆電池，最多測 3+3+1 = 7次後面就用數學歸納法，就能完成證明了＝＝＝＝說明：打起來很複雜，實際上畫圖說明能使對方更好理解。若有能幫助人理解的更好方式，歡迎打出至於實際把妹........ 機會只有一次，請不要把用過電池與一般電池混淆！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.115.158.137 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/puzzle/M.1701696319.A.59B.html