Feladat: 16.15.
n≥4 idős hölgy mindegyike tud egy pletykát,
azonban csak telefonon tudnak beszélni egymással. Mutassuk
meg, hogy
2n-4 hívással megoldható, hogy mindenki
ismerje mindegyik pletykát.
Megoldás: 16.15
n=4 esetén a hölgyeket megszámozva a
következő hívások megfelelők: 1-2, 3-4, 1-3,
2-4. (Érdemes meggondolni, hogy 3 hívás miért nem
elég.) Az indukciós lépésben eggyel
növeljük a hölgyek és kettővel a
hívások számát. Az új hölgy telefonál
valakinek, azután a régi hölgyek egymást közt
lebonyolítják a megszokott rendben a hívásokat,
végül az új hölgy újra felhív valakit.