Egy furfangos feladat megoldásában kérném segítségeteket! Egy 50 fős társaságban mindenkinek legfeljebb három haragosa van a többiek közül. A haragosság kölcsönös. A társaság kirándulni megy két 30 fős busszal?

A 'legfeljebb három haragos'-ba akár az is belefér, hogy senkinek nincs haragosa, nyilván ez a legegyszerűbb eset.

De lehetséges az is, hogy 25 embernek ugyanaz a legfeljebb három haragosa közül legalább kettő. Tehát, számokkal jelölve az embereket, 1.-25. közül mindenkinek haragosa pl. 26. és 27.; 26.-50. közül pedig mindenkinek haragosa mondjuk 1. és 2. Ebben az esetben 1.-25. megy az egyik busszal, 26.-50. pedig a másikkal.

Mivel csak az volt a kérdés, hogy szétoszthatók-e, ezért a válasz az, hogy vannak olyan esetek, amikor igen.

1. Nyilvánvalóan az nem megoldás, hogy vannak ilyen esetek, mert akkor mondhatnánk azt a triviális példát is, amikor senki sem haragosa senkinek.

2. Ez gráfelméleti probléma:

Adott egy 50 csúcspontú G(U,V,f) egyszerű gráf, melynek minden csúcsának fokszáma legfeljebb 3. A kérdés, hogy felbontható-e G két (G1(U1,V1,f1) és G2(U2,V2,f2) egyszerű gráf direkt összegére, ahol bármely i=1,2-re ha v=f(u1,u2) és u1,u2 eleme Ui, akkor fi(u1,u2) eleme Vi.

Mivel sok esetben a gráfelméleti problémák bizonyíthatóak teljes indukcióval, jó ötletnek ebből kiindulni.

Szerintem:

"legfeljebb 3 haragosa van" -nyilvánvaló, hogyha csak 0, vagy 1 akkor triviálisan megoldható, ezért úgy gondolom:

"Szétoszthatók-e az emberek MINDEN ESETBEN két részre úgy...?"

A harag-kapcsolatok max: 50*49*48*47 / 4! féle

a két buszon max.: (30*29/2) * (20*19/2) vagy inkább (25*24/2)^2 féle lehet

Kérdés: ez utóbbi van-e annyi mint előbbi?

Ha jól gondolkodom - de nem biztos.

Induljunk ki eloszor abbol hogy a ket busznak nincs 30fos kapacitasa.

Vegyuk az embereket egyenkent. Az elsot tesszuk az egyik buszba. A masodiktol kezdve a kovetkezot csinaljuk: mivel max 3 haragosa van, ezek a meglevok kozul a buszokban ugy helyezkedhetnek el, hogy 3-0 vagy 2-1, vagy 1-2 vagy 0-3. Tehat mindig lesz olyan busz, amelyikben legfeljebb egy haragosa van - ide tesszuk be ot.

Igy mindegyik embert be tudtuk tenni valamelyik buszba. Most mar csak azt kene belatni, hogy nem lesz a 30. ember utan problema olyan hogy be kellene tenni abba a buszba ahova mar nem fer.

Ebben meg nem vagyok biztos, hogy kellene, de talan a kolcsonosseget fel lehet itt is hasznalni: tegyuk fel hogy van mar 30 ember a buszban, es egyet se lehet athelyezni. Mindenkinek legfeljebb egy haragosa van a buszban, tehat a masik buszban legfeljebb ketto. Ez nem lehet ugyanaz a 30bol mindenkinek, mivel a haragossag kolcsonos: tehat legfeljebb ket embernek lehet ugyanaz a ket haragosa a masik buszban, igy viszont a masik buszban lennie kell mar egy csomo embernek, na es ha errol a csomorol be lehet latni hogy legalabb 20, akkor kesz a bizonyitas, hiszen akkor mar nem lehet tobb elhelyezendo ember.