MATEMANIJA

U računarskoj učionici ima [inlmath]15[/inlmath] računara i svaki računar povezan je sa još bar jednim računarom. Dokazati da u učionici postoje [inlmath]2[/inlmath] računara koja su povezana sa istim brojem drugih računara.

Nisam uopšte imao ideju kako bih mogao da krenem da dokazujem, tako da je svaka ideja dobrodošla.

U skupu od [inlmath]n[/inlmath] računara, svaki računar može biti povezan sa najviše [inlmath]n-1[/inlmath] računara.

Jasno. Da li bi bila greška da u narednom koraku primenim sledeći pristup:
Jedna od mogućih kombinacija sa kojima je jedan računar povezan sa drugima je (označavaću brojeve računara sa [inlmath]r_1[/inlmath], [inlmath]r_2[/inlmath], [inlmath]r_3[/inlmath] itd... do [inlmath]r_{15}[/inlmath])

[inlmath]r_1r_2[/inlmath], [inlmath]r_3r_4r_5[/inlmath], [inlmath]r_6r_7r_8r_9[/inlmath], [inlmath]r_{10}r_{11}r_{12}r_{13}r_{14}[/inlmath] i [inlmath]r_{15}[/inlmath]. I onda, kao tekstualni dokaz napišem npr. - Među povezanih [inlmath]14[/inlmath] računara, kada povežemo [inlmath]15.[/inlmath] računar, prema Dirihleovom principu dobijamo da će 2 računara biti povezana sa istim brojem računara.

Mislim da nije dobro navesti jedan od mogućih načina povezivanja, kao i da iz prethodne rečenice sledi direktno odgovor. Svakom računaru iz skupa [inlmath]\left\{1,2,...,n \right\}[/inlmath] pridruži jedan od brojeva računar [inlmath]\left\{1,2,...,n-1 \right\}[/inlmath].

A drugo, šta da u zadatku nije navedeno [inlmath]15[/inlmath] računara, nego [inlmath]150[/inlmath] računara? Ili da je rečeno [inlmath]n[/inlmath] računara, pri čemu nije određeno koliko je [inlmath]n[/inlmath]? Rešenje definitivno nije ispisivati sve moguće načine...

Slažem se, definitivno mi nije dobar pristup. Ali kada uradim to što mi je Fare savetovao, kako onda u tekstu da napišem taj dokaz? Jasno mi je kroz izraz kako to napisati, ali tekstualno nisam baš najsigurniji.