Vrati se na zadatke

Državno natjecanje 2017., 2. razred SŠ, A varijanta, 5. Zadatak

U jednom gradu je MM ulica i NN trgova, pri čemu su MM i NN prirodni brojevi takvi da je M>NM>N. Svaka ulica povezuje dva trga i ne prolazi kroz druge trgove. Građani žele promijeniti izgled grada. Ove godine svaka će ulica biti po prvi put obojena crveno ili plavo. Dogovoreno je da se svake godine odabere jedan trg, te svim ulicama koje vode do tog trga istovremeno promijeni boja iz plave u crvenu i obratno.

Dokaži da građani mogu odabrati boje ulica tako da se nikad u budućnosti ne može dogoditi da sve ulice budu iste boje.

Rješenje

Izvor

Ministarstvo znanosti i obrazovanja Republike Hrvatske · Agencija za odgoj i obrazovanje · Hrvatsko matematičko društvo

Napomena o izvoru

  • U prvoj službenoj napomeni izraz 'možemo podijeli' gramatički je pogrešan; ispravljen je u 'možemo podijeliti'.
  • U drugom službenom rješenju iz pretpostavke M>N za cijele brojeve pogrešno je navedeno M+1≥N; ispravljeno je u M≥N+1, što daje potreban zaključak da graf ima barem dva ciklusa.
  • U završnoj napomeni izraz 'ako je postoji takav par trgova' ispravljen je u 'ako postoji takav par trgova'.
  • U završnoj napomeni riječ 'drugo' u izrazu 'jednu od ulica ... crveno, a drugo plavo' ispravljena je u 'drugu' radi slaganja s imenicom ulica.
  • 2017-SS-drzavno-A-1234-rj.pdf, str. 12. Službeni zapis: „vrhove Tⱼ i Tⱼ₊₁ povezuje brid uⱼ.”. Ispravak: vrhove Tⱼ i Tⱼ₊₁ povezuje brid uⱼ₊₁.
  • Moguća pogreška u službenom rješenju (preneseno bez izmjene): U drugom rješenju tvrdi se da unija dvaju neparnih ciklusa bez njihova zajedničkog brida čini jedan parni ciklus. Primjerice, ciklusi A–B–C–A i A–B–D–C–E–A dijele samo brid AB, a nakon uklanjanja AB vrh C i dalje ima četiri brida. Za zaključak je dovoljno da izvorna unija sadrži parni ciklus, a tvrdnju zadatka dokazuje i prvo rješenje.

Prijavi grešku

Moguće su pogreške u prijepisu, formulama, temama, slikama ili rješenjima. Hvala što nam pomažeš poboljšati stranicu.