3. ELMO zadatak 5


Kvaliteta:
  Avg: 0,0
Težina:
  Avg: 0,0
Dodao/la: MNM
2. studenoga 2019.
LaTeX PDF

Neka je n\geqslant 4 prirodan broj. Promotrimo skup od n bakterija, takav da svaka bakterija osim jedne, koju ćemo zvati Kraljica, ima točno jednu majku (također bakteriju iz skupa). Kraljica nema niti jednu majku te je predak svim drugim bakterijama. Nijedna bakterija nije majka sama sebi. Kažemo da je bakterija U tetka bakterije V ako U nije majka od V i majka od U je majka majke od V. Odredi maksimalan broj parova bakterija (U,V) takvih da je U tetka od V.

(Napomena: Kažemo da je bakterija A predak bakterije B ako postoji niz bakterija x_1, x_2, \ldots x_k takav da x_1 = A, x_k = B te je x_{i} majka x_{i-1} za svaki i \in \{2, 3, \ldots k\})

(Ivan Novak)

Izvor: 3. Ekstremno loša matematička olimpijada