※ 引述《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://webptt.com/m.aspx?n=bbs/puzzle/M.1701696319.A.59B.html