U selu ima [inlmath]2014[/inlmath] stanovnika, od kojih se svi medjusobno ne poznaju. Da li je moguce da je raspored poznanstava takav da pop poznaje tacno [inlmath]500[/inlmath] stanovnika, [inlmath]213[/inlmath] stanovnika poznaje po jednog stanovnika, a ostali ne poznaju nikoga ili poznaju tacno dvoje?

Bas nemam nikakvu ideju - ne znam kako da pocnem zadatak. Razmisljao sam nesto o Dirihleovom principu ali ne znam da li moze da se primeni. Hvala

Evo pokusaja resenja zadatka bez grafova
Ako pop poznaje [inlmath]500[/inlmath] ljudi, za svakog od njih ima dve mogucnosti:
1) poznaju samo popa (1 osobu) - zelene elipse
2) poznaju popa i jos jednu osobu (2 osobe)

Ocigledno je da ne mogu sva [inlmath]500[/inlmath] coveka da poznaju samo popa, vec maksimalno njih [inlmath]213[/inlmath], dok ostali moraju da poznaju jos jednu osobu i da se taj lanac ne zavrsava vec da ide u krug (crvene veze sa slike). Te osobe treba rasporediti u lanac tako da lanac pocinje sa jedne osobe koja poznaje popa i zavrsava se kod druge osobe koja poznaje popa. Neka je broj osoba koje poznaju samo popa (jedna osoba) [inlmath]x[/inlmath]. Ostaje [inlmath]213-x[/inlmath] osoba koje poznaju samo jednu osobu (ne popa) i [inlmath]500-x[/inlmath] osoba koje znaju popa i jos jednu osobu. Razmotrimo mogucnosti:
1) [inlmath]x[/inlmath] je neparan;
2) [inlmath]x[/inlmath] je paran;

1) [inlmath]500-x[/inlmath] je takodje neparan broj. Ostaje nam neparan broj osoba koje moramo povezati medjusobno - jedna osoba ostaje nesparena.
2) [inlmath]213-x[/inlmath] je neparan broj. Osobe koje poznaju samo jednu osobu a ne popa su skupovi od dve osobe(ljubicaste elipse), zbog cega njihov broj mora biti paran.

Mozda je malo ali ne znamo svi grafove

Stefanowsky je napisao:ali ne znamo svi grafove

Pa ta skica koju si nacrtao upravo i jeste tipičan primer jednog grafa.

Ali, ovo tvoje detaljno objašnjenje će svakako biti razumljivije onima koji, što kažeš, nisu radili grafove.