Tübitak Lise 1. Aşama 2019 Soru 28

[Squidward]

Bir ağaç üzerinde bulunan $22$ yuvanın herhangi ikisi $r_1,r_2,\ldots,r_n$ renklerinden biri ile boyalı bir iple birleştirilmiştir. Bir salyangoz, her $k=1,2,\ldots,n$ için herhangi bir yuvadan herhangi başka bir yuvaya sadece $r_k$ rengine boyalı ipler üzerinde ilerleyerek varabiliyorsa, $n$ nin alabileceği en büyük değer nedir?

$\textbf{a)}\ 21 \qquad\textbf{b)}\ 20  \qquad\textbf{c)}\ 16 \qquad\textbf{d)}\ 12 \qquad\textbf{e)}\ 11$

[Uygar ÖZTÜRK]

Yanıt: $\boxed{E}$

$A = \binom{22}{2}$ elemanlı, ağaç üzerinde bulunan yuvalar arası yollar, kümesini; $n$ renk sayısı olmak üzere, $n$ alt kümeye ayıralım: $(r_1, r_2, r_3, \cdots, r_n)$. Bu kümelerden eleman sayısı en az olan veya olanlardan biri $r_i$ olsun. $r_i$'nin en az 21 eleman içermesi gerektiği açıktır. Güvercin yuvası prensibi gereğince: $\left \lfloor \frac{\binom{22}{2} - 1}{n} \right \rfloor + 1 = 21$ olmalıdır. Buradan da renk sayısının alabileceği en büyük değer $n = 11$ olarak bulunur.