Kombinatorika-zadatak

Ovaj zadatak nikako ne mogu da riješim,,, Mene podsjeća na Dirihleov princip, ali nikako ne mogu da skontam.. :/ Da li neko ima ideju? Hvala puno..

Zadatak:
Na šahovskom turniru učestvuje šahista. Dokazati da na kraju turnira zbir osvojenih poena prvih učesnika ne može biti veći od zbira poena preostalih učesnika.

Potpis

Follow your dreams, they know the way...

Da probam ovako:

Šahovski turnir od 4n takmičara se igra tako što svako igra sa svakim po jedanput. Za pobedu se dobija jedan poen, za izgubljen meč 0 poena, a za remi oba igrača dobiju po pola poena.

Iz ove postavke sledi da se turnir igra u 4n-1 kola, a u svakom kolu se odigrava 2n mečeva.

Ukupan broj poena koji mogu ostvariti svi igrači zajedno je 2n(4n-1).

Uzmimo da je, u najgorem slučaju, svaki od prvih n takmičara pobedio ostalih 3n takmičara. Pobeda/poraz/remi između prvih n takmičara nije bitan, ali pretpostavimo (zbog jednostavnijeg računa) da je prvi pobedio sve ostale, drugi sve osim prvog itd.

Tada je prvi takmičar osvojio 4n-1 bodova, drugi 4n-2 itd. dok je n-ti osvojio 4n-1-n=3n-1 bodova.

Ukupan broj bodova koji su osvojili takmičari rangirani od 1 do n je n(4n-1+3n-2-1)/2=n(7n-2)/2

Tada treba dokazati da je n(7n-2)/2 <= 2n(4n-1) - n(7n-2)

Kada se ovo sredi dobije se: n(n-1) >= 0

Ovo je tačno za svako n iz skupa prirodnih brojeva.

Hvala puno, samo ja ovo kad sredim(poslednju nejednakost), dobijem .. :/

Potpis

Follow your dreams, they know the way...

OK, napravio sam dve greške u prepisivanju, ali krajnji rezultat mi je (skoro) tačan (a tvoj nije)

Prvo, n(4n-1+3n-2-1)/2=n(7n-2)/2 nije tačno nego treba n(4n-1+3n-1)/2=n(7n-2)/2 (-2 je višak) u prvoj verziji

Drugo, n(7n-2)/2 <= 2n(4n-1) - n(7n-2) nije tačno, treba n(7n-2)/2 <= 2n(4n-1) - n(7n-2)/2

Kada se ovo sredi, dobije se
2n(4n-1)-n(7n-2)>=0
8n^2-2n-7n^2+2n>=0
n^2>=0

Oki, hvala puno.. :)
A, da, samo da pitam za ovo koliko je n-ti takmičar osvojio poena, ovde piše 4n-1-n, da nije možda 4n-n, meni nešto tako logično, ako je prvi osvojio 4n-1, drugi 4n-2, onda n-ti 4n-n? Ili ja nisam skontala kako treba... :)

Potpis

Follow your dreams, they know the way...

Oki, hvala puno.. :)
A, da, samo da pitam za ovo koliko je n-ti takmičar osvojio poena, ovde piše 4n-1-n, da nije možda 4n-n, meni nešto tako logično, ako je prvi osvojio 4n-1, drugi 4n-2, onda n-ti 4n-n? Ili ja nisam skontala kako treba... :)

Potpis

Follow your dreams, they know the way...