7回以内で電池テスト問題を解決する方法

要約

この記事では、電池テスト問題を解決し、7回以内に動作するペアを見つける方法について説明します。問題は、しわがれたシャツを修正するための巨大なアイロンに良い電池を2つ見つけるために8つの電池をテストすることです。すべての可能な組み合わせをテストすることは時間がかかるため、すべての可能な組み合わせをテストしない方法を探求します。

分割制覇：電池テスト問題

問題は、8つの電池の中から2つの良い電池を見つけて巨大なアイロンを動かすことです。アイロンには2つの巨大な電池が必要で、4つは動作し、4つは死んでいます。すべての可能な組み合わせをテストすることは時間がかかるため、7回以内に動作するペアを見つけるためのより速い方法が必要です。

解決策：電池を小さなサブセットに分割する

すべての可能な組み合わせをテストする代わりに、電池を小さなサブセットに分割して、可能な結果を絞り込むことができます。合計4つの良い電池があるため、6つの電池の山の中には少なくとも2つの良い電池が含まれています。山から3つの電池を取り出し、すべての可能な組み合わせをテストして両方の電池が動作するかどうかを確認できます。3つの組み合わせがすべて失敗した場合、このグループには1つの良い電池またはまったくないことがわかります。これらの3つを取り分け、別の3つの電池について同じプロセスを繰り返すことができます。再びすべての組み合わせが失敗した場合、このセットには1つの良い電池以上含まれていない可能性があります。これにより、テストされていない2つの電池が残ります。合計4つの良い電池があり、これまでに2つしかカウントされていないため、これらの残りの2つの電池はどちらも良い電池である必要があります。