HMO 2017 - Izborni test za IMO - Zadatak 2


Kvaliteta:
  Avg: 0,0
Težina:
  Avg: 6,0
Dodao/la: arhiva
17. listopada 2023.
LaTeX PDF

U nekom arhipelagu nalazi se 2017 otoka nazvanih 1, 2, \dotsc, 2017. Dvije agencije, Crveni zmaj i Plavo oko, dogovaraju se oko rasporeda brodskih linija između pojedinih otoka. Za svaki par otoka, točno jedna agencija će organizirati brodsku liniju i to samo u smjeru od otoka nazvanog manjim brojem do otoka nazvanog većim brojem.

Raspored brodskih linija je dobar ako ne postoje dva otoka s oznakama A<B takva da je s otoka A na otok B moguće doći koristeći samo brodove Crvenog zmaja, a također i koristeći samo brodove Plavog oka.

Odredi ukupan broj dobrih rasporeda brodskih linija.

Izvor: Hrvatska matematička olimpijada 2017.