Tudnátok segíteni? Matek, logikai.

Nincs benne a feladat szövegében, hogy mindenki mindenkivel fogott kezet. Szóval máshogy kell gondolkodni.

Viszont az igaz, hogy páros ember foghatott csak páratlanszor kezet. Bizonyítás teljes indukcióval:

P halmazban vannak azok, akik páros számszor fogtak kezet, N-ben azok, akik páratlanszor.

Egyesével nézzük sorban a kézfogásokat. n=0 esetén még senki nem fogott senkivel sem kezet, tehát P-ben van mind a 10 ember, N üres. Eddig tényleg páros számú páratlan kézfogás van (N elemeinek száma 0, és a 0 páros szám).

Tegyük fel, hogy n=k-ra is igaz: páros számú páratlan kézfogás van, N elemeinek száma páros.

n=k+1-re: 2 tetszőleges ember kezet fog. A következő esetek lehetnek:

- mindkettő eddig a P halmazban volt. A kézfogás után mindkettő az U-ba kerül, tehát 2-vel nő az U halmaz elemszáma, továbbra is páros marad.

- mindkettő eddig az U halmazban volt. Mindkettő átkerül P-be, tehát 2-vel csökken U elemszáma, továbbra is páros marad.

- egyik P-ben, másik U-ban volt. Az első átkerül P-ből U-ba, a második meg U-ból P-be, tehát változatlan marad az U-ban lévő emberek száma.

Vagyis n=k+1-re is beláttuk, kész.

Kicsit máshogyan, talán egyszerűbben:

Ábrázoljuk a feladatot egy 10 csúcsú gráffal. A csúcsok jelzik az embereket, az élek a kézfogásokat. Egy csúcs fokszáma ekkor annyi, ahány emberrel fogott kezet az illető.

A fokszámok összege a gráfban az élek számának kétszerese, azaz mindig páros szám!

A páros fokszámú csúcsok darabszáma most lényegtelen, összeadva mindenféleképpen páros marad. A páratlan fokszámú csúcsokból viszont nem lehet páratlan darabszámú, mivel akkor a fokszámok összege páratlan lenne.

Ez azt jelenti, hogy olyan ember aki páratlan számszor fogott kezet csak páros számú lehet.