Feladat: 1.6.
* Egy erdőben 12 törpe él piros vagy kék házikóban. Minden év
i-edik hónapjában az
i-edik törpe felkeresi összes barátját, hogy eldöntse, átfesti-e házikóját. Akkor és csak akkor fogja átfesteni (pirosról kékre vagy fordítva), ha a barátai többsége éppen más színű házban lakik, mint ő. Bizonyítsuk be, hogy néhány év után már semelyik törpe sem fogja átfesteni a házát. A barátságok kölcsönösek és az évek során nem változnak. (AD haladó, 1990, tagozatos döntő.)
Megoldás: 1.6
A barátságokat ábrázoljuk gráffal, amelynek pontjai a törpék, élei a barátságok. Minden pontot olyan színűre festettnek képzelünk, amilyen színű házban az illető törpe éppen lakik. Nézzük, mi történik egy-egy törpe akciója után azoknak az éleknek a számával, amelyek két végpontja különböző színű volt. Ha a törpe átfesti a házát, ez azért van, mert így az ilyen élek száma csökken. Mivel az élek száma nem lehet negatív, egy idő után nem csökkenhet, vagyis egy idő után egyetlen törpe sem fogja átfesteni a házikóját.