Gönderen Konu: Tübitak Lise 2. Aşama 2011 Soru 1  (Okunma sayısı 3869 defa)

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 2.633
  • Karma: +9/-0
Tübitak Lise 2. Aşama 2011 Soru 1
« : Ağustos 06, 2013, 03:46:33 öö »
$n\ge 2$ ve $E=\lbrace 1,2,\ldots ,n\rbrace $ olsun. $
A_{1},A_{2},\ldots ,A_{k}$; $E$ nin altkümeleri olmak üzere, her $1\le i<j\le k$ için, $A_{i}\cap A_{j}$, $A_{i}'\cap A_{j}$, $A_{i}\cap A_{j}'$ ve $A_{i}'\cap A_{j}'$ kümelerinden tam olarak bir tanesi boş ise, $k$ nin alabileceği en büyük değeri belirleyiniz.

[$A$, $E$ nin bir altkümesi ise, $E$ nin $A$ ya ait olmayan elemanlarının kümesini $A'$ ile gösteriyoruz.]

(Selim Bahadır)
« Son Düzenleme: Kasım 13, 2013, 01:50:12 ös Gönderen: geo »

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 2.633
  • Karma: +9/-0
Ynt: 1
« Yanıtla #1 : Ağustos 17, 2013, 11:43:58 ös »
(Mehmet KAYSİ)

Cevap: $2n-3$.

Tümevarımla ispatlayacağız. $n=3$ iken, $k\leq 3$ olduğunu görmek kolay ve $3$'e örnek de $\{1\},\{2\},\{3\}$. Farzedelim ki $n-1$ için cevap $2n-5$ olsun.
$n$ için $k$'nın en büyük değerini aldığı durumu ele alalım. $\{A_1, A_2, \ldots A_k\}$ 'ye koleksiyon diyelim. Koleksiyonda boş kümenin ve $\{1,2,\dots ,n\}$'nin olamayacağı açık. Bu koleksiyon her $i$ için, $\{i\}$ ve $\{i\}^{'}$ kümelerinden tam olarak birini içermek zorunda. Ikisini birden içeremez, ikisini de içermiyorsa bir tanesini ekleyerek koleksiyonu büyütebilirdik.
$A$ bu koleksiyondaki bir küme ise, $A$'yı silip, $A^{'}$'ni eklersek tüm koşullar sağlanmaya devam eder. O zaman koleksiyondaki her kümenin eleman sayısının en fazla $\frac{n}{2}$ olduğunu kabul edebiliriz. Tek elemanlı olmayıp en az eleman sayısına sahip bir küme $A$ olsun. Genelliği bozmadan $1,2 \in A$ varsayabiliriz. $B$ bu koleksiyonda $\{1\}$ ve $\{2\}$ dışında bir küme olsun.
$A\cap B={\varnothing} $ ise, $1,2 \notin B$,
$A\cap B^{'}={\varnothing}$ ise, $A\subset B$ $\Rightarrow $ $1,2 \in B$,
$A^{'}\cap B={\varnothing}$ ise, $B\subset A$, ama bu $A$ ve $B$'nin seçiminden dolayı mümkün değil.
$A^{'}\cap B^{'}={\varnothing}$ ise, $A\cup B=\{1,2,3, \dots , n\}$. $n$ tekse, $|A|,|B|\leq \frac{n-1}{2}$ olduğundan bu mümkün olamaz. $n$ çiftse, tek olası durum $B=A^{'}$ olmasıdır, ama bu durumda da bahsi geçen dört kesişimden ikisi boş küme olur.
Yani $B$, $1$ ve $2$'nin ya iksini de içerir, ya da ikisini birden içermez. O halde $\{1\}$ ve $\{2\}$ yi silip $\{1,2\}$'yi bir eleman gibi düşünürsek, $n-1$ için olan duruma geçmiş oluruz. Öyleyse $n$ için cevap en fazla $2n-5+2=2n-3$ olabilir. $2n-3$ için de örnek: tüm tek elemanlılar ve $\{1,2\}$, $\{1,2,3\}$,$\{1,2,3,4\}$,$\dots$, $\{1,2,3,\dots ,n-2\}$
« Son Düzenleme: Haziran 22, 2014, 08:09:07 öö Gönderen: geo »

 


Sitemap 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 
SimplePortal 2.3.3 © 2008-2010, SimplePortal