Egy társaságban 7 fiú jött össze. Tudjuk róluk, hogy bármelyik fiúnak a többi között legalább 3 testvére van. Mutasd meg, hogy ekkor mind a heten testvérek?!

problémaredukció sztem jól alkalmazható itt:

páratlan x emberről kell belátni hogy ha mindegyiknek legalább (x-1)/2 tesója van a köztük, akkor mindenki testvér

legyen tehát 3 ember, ahol mindenkinek legalább 1 tesója van köztük.

a b és c

a-nak b vagy c a tesója

a két eset:

a-nak b a tesója (ekkor b-nek a, de c-nek legalább egy tesójának kell lennie, szal abc testvérek)

vagy a-nak c (ekkor c-nek a, de bnek is legalább egy tesójának kell lennie - abc testvérek)

szal az egyetlen lehetőség hogy mindenki tesó.