Geomania.Org Forumları
Yarışma Soruları => Tübitak Lise 1. Aşama => 1998 => Konuyu başlatan: geo - Nisan 26, 2014, 03:25:27 ös
-
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
$
-
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.
-
Kümelerin kümesi $S$ olsun.
$(S, \subseteq)$ 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 $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 (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. $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 (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)