[es] - Kombinatorika-zadatak

uvelaruza

Član broj: 315832
Poruke: 71
31.223.132.*

+25 Profil

^{30.01.2014. u 09:21 - pre 124 meseci}

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.

Follow your dreams, they know the way...

Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3453

Jabber: djoka_l

+1462 Profil

Re: Kombinatorika-zadatak

^{30.01.2014. u 13:15 - pre 124 meseci}

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.

Odgovor na temu

uvelaruza

Član broj: 315832
Poruke: 71
*.teol.net.

+25 Profil

Re: Kombinatorika-zadatak

^{06.02.2014. u 09:20 - pre 124 meseci}

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

.. :/

Follow your dreams, they know the way...

Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3453

Jabber: djoka_l

+1462 Profil

Re: Kombinatorika-zadatak

^{06.02.2014. u 10:30 - pre 124 meseci}

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

Odgovor na temu

uvelaruza

Član broj: 315832
Poruke: 71
*.teol.net.

+25 Profil

Re: Kombinatorika-zadatak

^{06.02.2014. u 11:30 - pre 124 meseci}

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... :)

Follow your dreams, they know the way...

Odgovor na temu

uvelaruza

Član broj: 315832
Poruke: 71
*.teol.net.

+25 Profil

Re: Kombinatorika-zadatak

^{06.02.2014. u 11:38 - pre 124 meseci}

Citat:

djoka_l:
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

Follow your dreams, they know the way...

Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3453

Jabber: djoka_l

+1462 Profil

Re: Kombinatorika-zadatak

^{06.02.2014. u 13:29 - pre 124 meseci}

E, sada si ti u pravu, a ja sam greške ispravljao po sećanju.
N-ti takmičar je osvojio 3n bodova, pa je onda izraz n(7n-1)/2, te na kraju imamo n(n-1)>=0.

Odgovor na temu