Gönderen Konu: Tübitak Lise 2. Aşama 2010 Soru 6  (Okunma sayısı 3007 defa)

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 1801
  • Karma: +8/-0
Tübitak Lise 2. Aşama 2010 Soru 6
« : Ağustos 06, 2013, 04:45:39 öö »
$K$, düzlemdeki dışbükey bir $2010$-genin kenar ve köşegenlerinin kümesi olsun. $A$, $K$ nin bir altkümesi olmak üzere; $A$ ya ait her doğru parçası çifti kesişiyorsa, $A$ ya kesişimli küme diyelim. İki kesişimli kümenin birleşiminin en çok kaç elemana sahip olabileceğini belirleyiniz.

(Umut Varolgüneş)
« Son Düzenleme: Kasım 13, 2013, 02:30:36 ös Gönderen: geo »

Çevrimdışı bvarici

  • G.O Yeni Üye
  • *
  • İleti: 6
  • Karma: +0/-0
Ynt: Tübitak Lise 2. Aşama 2010 Soru 6
« Yanıtla #1 : Ekim 06, 2013, 04:19:21 ös »
(Muhammed Zahid Öztürk)

Cevabımız $4019$. Eğer $n\geq5$ ise $n$-gen için cevabın $2n-1$ olduğunu göstereceğiz.

$A$ bir kesişimli küme olsun öyle ki $\left|A\right|\ge n$. $A$'daki köşe sayısı doğru parçası sayısından büyük olmayacağından $A$ bir döngü içerir. Bunu anlamak için tersini düşünelim. Bir döngü içermese bir ağaç olması gerekirdi, fakat $n$ köşeli bir ağaçta en fazla $n-1\ $kenar olabilir. Bu yüzden bir döngü kesin vardır. $PQ$ ve $QR$ bu döngüde iki doğru parçası olsun. Döngüdeki her doğru parçası, $XP$ ve $RY$ hariç, $PQ$ ve $QR$'nin ikisini birden kendi iç noktalarında keser. Bundan dolayı her doğru parçası $PQ$ ve $QR$ ye göre karşıdan karşıya geçmektedir.  Burada döngünün tek sayıda doğru parçası içerdiğini ve döngüdeki köşelerden hiçbirinin  $\angle PQR$ açısının iç bölgesinde olmadığını çıkarırız.

Şimdi bu döngüdeki köşelimizi adlandıralım. Döngümüzde $k$ bir pozitif tamsayı olmak üzere $2k+1$ tane köşe olduğunu kabul edelim. Bu köşeler $P_1,P_2,\dots ,P_{2k+1}$  olsun. Bu köşeleri saat yönünde sıralandırmış olmak için döngüdeki doğru parçalarının $P_iP_{i+k}$, $P_iP_{i+k+1}$ olduğunu $1\le i\le 2k+1$ için (İndisler $\bmod n$'e göredir) kabul edeceğiz. (Her doğru parçasının $PQ$ ve $QR$ ye göre karşılıklı olmasının doğal sonucu) Bu doğru parçalarını $A^*$ ile gösterelim. Burada $2k+1$ tane doğru parçası olduğuna dikkat edelim. $A$ bir kesişimli küme olduğundan $A$'daki diğer doğru parçaları ancak $XP_i$ formunda olabilir; $X$,  $\angle P_{i+k+1}P_iP_{i+k}$  açısının iç bölgesinde bir köşe. $\left|A\right|\ge n$  olduğundan tüm böyle doğru parçaları ($A^{\Delta }$  ile gösterelim) $A$'ya ait olmak zorundadır. Çünkü bu köşe döngüden sadece bir köşeye bağlı olabilir ya da başka bir deyişle döngümüzü kurarken elimizdeki tüm doğru parçalarını toplarsak da $n$ sayısına ancak ulaşabiliriz. Bu nedenle eğer $A$ bir kesişimli küme ve  $\left|A\right|\ge n$  ise ve  $\left|A\right|=n$' dir ve  $A=A_{\left(P_1,P_2,\dots ,P_{2k+1}\right){\rm \ }}={\rm \ }A^*\cup A^{\Delta }$.   

Şimdi göstereceğiz ki eğer $A$ ve $B$ kesişimli kümeler ve ${\rm \ }\left|A\right|=n{\rm =}\left|B\right|$  ise $A$ ve $B$ ayrık olamaz. Ayrık olduklarını varsayalım. Her köşenin bağlı olduğu en az bir köşe olduğundan şöyle bir varsayımda bulunabiliriz. $Q_1Q_2,Q_2Q_3,\dots ,Q_{m-1}Q_m,Q_mQ_1$  bir döngü olsun öyle ki $Q_iQ_{i+1}$ doğru parçaları $i$ tekse $A$'ya, $i$ çiftse $B$'ye ait olsun.$\ \left(Q_{m+1}=Q_1\right)$  Öyle bir döngü vardır ki çokgenin her köşesi $A$ ve $B$'den en az birer doğru parçasının bitiş noktasıdır. $A$ ve $B$ kesişimli olduğundan tüm $Q_iQ_{i+1}$' ler $i$ tekse $Q_1Q_2$'yi, $i$ çiftse $Q_2Q_3$'ü keser. Bu nedenle  $i$ çift ise tüm $Q_i$'ler ya $Q_1Q_2$'nin üzerindedir ya da $Q_1Q_2$'ye göre $Q_3$ ile farklı taraftadır. Ve $i$ tek ise tüm $Q_i$'ler ya $Q_2Q_3$'ün üzerindedir ya da $Q_2Q_3$' ye göre $Q_1$ ile farklı taraftadır. $m$ tektir ve $Q_1$ ${\rm \ }A^*$ 'ın bir köşesidir. O zaman $Q_3$  ya $Q_mQ_1$'in üzerindedir ya da $Q_mQ_1$' e göre $Q_2$ ile farklı taraftadır. Ve $Q_{m-1}$ ya $Q_1Q_2$' nin üzerindedir ya da   $Q_1Q_2$'e göre $Q_m$ ile farklı taraftadır. $XQ_1$, $B$'ye ait bir doğru parçası olsun. $XQ_1$,  $Q_2Q_3\ $ve $Q_{m-1}Q_m$'in ikisini de kesmek zorundadır ve $B$'ye aittir. O halde $X$ çokgende $Q_2$ ve $Q_m$ arasındadır. Fakat bu durumda $XQ_1$ aynı zamanda  $A^{\Delta }$ 'ya ve bu nedenle $A$'ya aittir. Çelişki!

Son olarak eğer $P,Q,R,S,T$  çokgende beş ardışık köşe ise, $A_{\left(P,Q,R\right)}\cup A_{\left(R,S,T\right)}$  $2n-1$ doğru parçası içerir. 
« Son Düzenleme: Haziran 28, 2014, 01:45:03 öö Gönderen: geo »
Burak VARICI

 


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 
SimplePortal 2.3.3 © 2008-2010, SimplePortal