N zsák aranyrúd 2

Az első zsákból 1, a másodikból 2, a harmadikból 4, a negyedikből 8, .... az n-edikből 2^(n-1) érmét vegyünk ki, és mérjük le az együttes súlyukat. Az 'elméleti érték' ebben az esetben 1+2+4+... = 2^n -1 gramm. Ennél valamivel kevesebbet fogunk mérni. A különbség egyértelműen felírható a 2 bizonyos hatványainak összegeként, és ha ezt megtesszük, azt is tudjuk, melyek a hamis zsákok.

Ha csak egy zsákunk van, akkor ugye ismert a megoldás. Mindegyik zsákból eggyel több aranyrudat kell kivennünk. Na de ha több hamis zsákunk is lehet, akkor ez nem lehetséges megoldás, mert ha az 5. zsák a hamis, akkor ugye 5 grammal mutat kevesebbet a mérleg, de az az 5 gramm kijöhetne az első és a negyedik, esetleg a második es a harmadik zsákból. Ezért úgy kell kihelyeznünk az érméket zsákonként, hogy összegük ne adhasson másik zsákbol kivett érmek összegét. Ezek a számok a 2 hatványai lesznek.
Pl. 5 zsák eseten:
1.= 1 érme
2.= 2 érme
3.= 4 érme
4.= 8 érme
5.= 16 érme
És így tovább. Ebből meg tudjuk állapítani, hogy melyik zsák(ok) hamisak.