HMO 2020 - Izborni test za IMO - Zadatak 2


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

Splet je konačan skup pravaca u općem položaju (tj. svaka dva pravca se sijeku, ali nikoja tri ne prolaze istom točkom). Pravci spleta dijele ravninu na područja čije su stranice dužine ili polupravci. Labirint je splet u kojem je svaki pravac obojan, poput zida, s jedne strane crvenom, a s druge strane plavom bojom. Dva područja sa zajedničkim vrhom koja u toj točki imaju i crvene i plave stranice nazivamo povezanima. Po labirintu se kreću mravi koji mogu prijeći iz područja u kojem se nalaze samo u područje koje je s njim povezano. Za splet S definiramo k(S) kao najveći broj mrava koje je moguće razmjestiti po svakom labirintu na S tako da se nikoja dva mrava ne mogu sastati krećući se po labirintu.

Za n\in \mathbb{N}, odredi sve moguće vrijednosti k(S) pri čemu je S splet od n pravaca.

Izvor: Hrvatska matematička olimpijada 2020.