Tübitak Lise 1. Aşama 1997 Soru 34

[matematikolimpiyati]

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}$

[geo]

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ümedir. Kısmi sıralı kümelerdeki zincir ve anti-zincir 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 veya Mirsky Teoremlerinin bir sonucu 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
Bağıntılar