Tübitak Lise 1. Aşama 1998 Soru 07

[geo]

Alınan herhangi $n$ küme arasında birbirini içermeyen en az $3$ tane veya herhangi ikisinden biri diğerini içeren en az $3$ tane küme bulunmasını garanti eden en küçük $n$ tam sayısı nedir?

$
\textbf{a)}\ 4
\qquad\textbf{b)}\ 5
\qquad\textbf{c)}\ 6
\qquad\textbf{d)}\ 7
\qquad\textbf{e)}\ 8
$

[geo]

Yanıt: $\boxed{B}$

Soruda istenen $p \lor q$ ifadesinin tersi $p' \land q'$ dir. Dört küme arasından birbirini içermeyen en fazla $2$ tane ve herhangi ikisinden biri diğerini içermeyecek en fazla $2$ tane küme bulunan tek bir konfigürasyon vardır: $A \subset B$, $C \subset D$ (Kolaylık olması açısından $A \cap C = \{\}$ ve $B \cap D = \{\}$ kabul edebiliriz.). Görüldüğü gibi $4$ küme olduğunda soruda verilen şartı sağlamayan bir konfigürasyon bulunabiliyor. Bu konfigürsayona bir $E$ kümesi eklediğinizde bu küme $A$ ya da $C$ kümelerinden birinin alt kümesi ya da $B$ ya da $D$ kümelerden birini içeriyorsa herhangi ikisinden biri diğerini içeren $3$ küme bulunmuş olacak, değilse $A,C,E$ kümeleri birbirini içermeyen $3$ küme olacak. Bu durumda alınan herhangi $5$ küme arasından sorudaki şart kesinlikle sağlanır.

[geo]

Kümelerin kümesi $S$ olsun.
$(S, \subseteq)$ kısmi sıralı bir kümedir. Kısmi sıralı kümelerdeki zincir ve anti-zincir kavramlarını kullanacağız.
Soru bize $3$ uzunluklu bir anti-zincirin veya $3$ uzunluklu bir zincirin var olması için $S$ nin 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. $5 = 2\cdot 2 + 1$ olduğu için $5$ elemanlı bir kısmi sıralı küme içerisinde $2+1 = 3$ elemanlı bir zincir ya da $2+1 = 3$ elemanlı bir anti-zincir vardır. O halde aradığımız en küçük $n$ değeri $5$'tir.

Kaynaklar:
Partially Ordered Sets
Bağıntılar