Feladat: táncosok partnerei

Egy társaságban 5 lány és 5 fiú táncolt. Utána kilencen pontosan megmondták, hogy hány partnerrel táncoltak. Számuk 5; 5; 5; 4; 4; 3; 3; 3; 3 volt. A táncolók egyike nem tudott pontos számot mondani, vagy 3, vagy 4 partnerre emlékezett. Megállapítható-e a tizedik ember partnereinek száma?

Megoldás: táncosok partnerei

A feladatban leírtakat egy gráffal szemléltethetnénk. A gráf pontjai a társaságban lévő emberek, és a gráf élei azt mutatják, hogy két ember táncolt egymással. Ebben a gráfban egy pont fokszáma a megfelelő ember táncpartnereinek száma. A 10 pontú gráfban 10 fokszám van. Ezek közül 9 pontosan adott, a tizedikre két lehetőség van (vagy 3, vagy 4). Hogyan dönthetjük el, hogy melyik a pontos fokszám?

Az előző tétel szerint a 10 fokszámösszeg páros. A pontosan ismert 9 fokszám összege páratlan. Ebből az következik, hogy a hiányzó fokszámnak páratlannak kell lennie.

A tizedik ember táncpartnereinek száma: 3.