Geomania.Org Forumları
Yarışma Soruları => Tübitak Lise 1. Aşama => 2019 => Konuyu başlatan: Squidward - Haziran 02, 2019, 03:11:56 ös
-
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$
-
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.