Zadatak: 2. lakša simulacija državnog natjecanja 2020. zadatak 5 (Sakrij tekst zadatka)
Kliknite ovdje kako biste prikazali rješenje.
Neka su težine igrača t1, t2, ..., t23. Neka su težine dobre ako je bez obzira na suca moguće napraviti dvije ekipe jednake težine. Neka je S suma težina svih igrača. 1. Ukoliko postoje dva igrača (ai i aj) s težinama različite parnosti, težine nisu dobre. Primjetimo da je jedan od brojeva S-ai i S-aj neparan, što znači da nije moguće podijeliti igrače u dva tima. 2. Primjetimo da ako su težine t1, t2, ... t23 dobre, onda je: ako su sve težine neparne - težine t1-1, t2-1, ...t23-1 također dobre. To vrijedi jer će u svakom timu se težine smanjiti za 11. ako su sve težine parne - težine t1/2, t2/2,...t23/2 također dobre. To vrijedi zato što će se težina svakog tima prepoloviti. Ovisno o parnosti težina, provodimo jedan od prethodna dva umanjenja težina. Kako težine nisu beskonačne, u jednom trenutku će barem jedan igrač imati težinu 1. Pretpostavimo da takvih igrača ima najviše 22. Nakon smanjivanja svih težina za 1, sve težine su parne, a barem jedna je 0. Nakon nekoliko mogućih uzastopnih dijeljenja s dva, igrači s pozitivnim težinama imaju neparne težine, dok je težina 0 parna. Te težine nisu dobre, pa time ni početne težine. Težine će biti dobre samo ako svi igrači u istom trenutku padnu na težinu 1, a to znači da su svi imali jednake početne težine.