Geomania.Org Forumları
Yarışma Soruları => Tübitak Lise 1. Aşama => 1997 => Konuyu başlatan: matematikolimpiyati - Temmuz 04, 2022, 02:15:50 ös
-
Her $a,b,c,d$ için$,\ (a \mid b,\ b \mid c\ \text{ve}\ c\mid d) \implies \{a,b,c,d\} \not\subset T$ koşulunu sağlayan ve pozitif tam sayılardan oluşan $n$ elemanlı her $T$ kümesi$,$ hiçbiri bir diğerini bölmeyen en az $6$ tam sayı içeriyorsa $n$ tam sayısının alabileceği en küçük değer nedir?
$\textbf{a)}\ 18 \qquad\textbf{b)}\ 15 \qquad\textbf{c)}\ 17 \qquad\textbf{d)}\ 16 \qquad\textbf{e)}\ \text{Hiçbiri}$
-
Yanıt: $\boxed D$
$15$ elemanlı $T = \{2, 2^2, 2^3, 3, 3^2, 3^3, 5, 5^2, 5^3, 7,7^2,7^3, 11, 11^2, 11^3\}$ kümesi, hiçbiri bir diğerini bölmeyen en fazla $5$ tam sayı içerir.
Çünkü $T_k = \{k,k^2, k^3\}$ olmak üzere $S_2$, $S_3$, $S_5$, $S_7$, $S_{11}$ kümelerinin her birinden en fazla bir eleman alınabilir.
$16$ elemanlı $T = \{2, 2^2, 2^3, 3, 3^2, 3^3, 5, 5^2, 5^3, 7,7^2,7^3, 11, 11^2, 11^3, 13\}$ kümesinde ise hiçbiri bir diğerini bölmeyen $6$ eleman bulunabiliyor.
$(\mathbf Z^+, \mid)$ kısmi sıralı bir küme (https://en.wikipedia.org/wiki/Partially_ordered_set)dir. Kısmi sıralı kümelerdeki zincir (https://en.wikipedia.org/wiki/Total_order#Chains) ve anti-zincir (https://en.wikipedia.org/wiki/Antichain) kavramlarını kullanacağız.
Soru bize en fazla $3$ uzunluklu bir zincir olduğunu, $6$ uzunluklu bir anti-zincirin var olması için kümenin en az kaç elemanlı olması gerektiğini soruyor.
Dilworth (https://en.wikipedia.org/wiki/Dilworth%27s_theorem) veya Mirsky (https://en.wikipedia.org/wiki/Mirsky%27s_theorem) Teoremlerinin bir sonucu (https://en.wikipedia.org/wiki/Mirsky%27s_theorem#Erd%C5%91s%E2%80%93Szekeres_theorem) olarak $rs + 1$ elemanlı kümede $r+1$ uzunlukta bir zincir ya da $s+1$ uzunlukta bir anti-zincir bulunur. $16 = 3\cdot 5 + 1$ olduğu için $16$ elemanlı bir kısmi sıralı küme içerisinde $3+1 = 4$ elemanlı bir zincir ya da $5+1 = 6$ elemanlı bir anti-zincir vardır. Tanım gereği $4$ elemanlı zincir olmadığı için $6$ elemanlı bir anti-zincir vardır.
Kaynaklar:
Partially Ordered Sets (https://www.math.cmu.edu/~af1p/Teaching/Combinatorics/Slides/Posets.pdf)
Bağıntılar (https://acikders.tuba.gov.tr/pluginfile.php/184/mod_resource/content/0/DersNotlari/AD1PDF/bolum1.pdf)