Matematik Olimpiyatı 2015, 2. Aşama, Soru 3

\(n \ge 4\) olmak üzere düzlemde \(n\) nokta veriliyor. Tüm nokta ikilileri doğru parçalarıyla birleştirildikten sonra hiçbir diğer doğru parçasıyla uç noktaları dışında kesişmeyen doğru parçalarının

sayısı en çok kaç olabilir?

Şıklar:

Cevap:  2n - 2

Çözüm:
Cevap: 2n - 2.


Diğer hiçbir doğru parçasıyla uç noktaları dışında kesişmeyen doğru parçalarına özel doğru parçası diyelim.  \( n \geq 4 \)  için özel doğru parçalarının sayısının en fazla 2n - 2 olduğunu tümeverimla gösterelim. n = 4 durumu barizdir.

  


Verilen n nokta bir konveks n-genin koşeleri ise özel doğru parça sayısı tam olarak n oluyor (n-genin kenarları) ve bu durumda  \( n < 2n - 2 \) . Aksi taktirde bu n noktadan biri olan A noktası bu n noktanın konveks örtüsünün (convex hull) sınırı üzerinde olmayacaktır. Kalan n - 1 noktanın bazı ikililerini tüm kapalı alanlar üçgen olacak şekilde birleştirelim. (triangulation). A noktası bu üçgenlerin birinin içinde bulunmak zorundadır. Bu üçgen  \( P_{1}P_{2}P_{3} \)  olsun.  \( P_{1}P_{2}P_{3} \)  üçgeninin içinde kalan n - 3 noktadan A dışında başka nokta bulunmadığı açıktır. A noktası atılırsa tümevarım varsayımına göre en fazla  \( 2(n - 1) - 2 = 2n - 4 \)  özel doğru parçası olabilir. A yeniden yerleştirildiğinde sadece  \( [AP_{1}], [AP_{2}], [AP_{3}] \)  özel doğru parçaları eklenebilir (bir köşesi A olan diğer doğru parçaları  \( P_{1}P_{2}P_{3} \)  üçgeninin kenarlarından biri ile kesişiyorlar).


A noktası atıldıktan sonra  \( [P_{1}P_{2}], [P_{1}P_{3}], [P_{2}P_{3}] \)  doğru parçalarının en az biri özel değilse, bir  \( \ell \)  doğru parçası  \( P_{1}P_{2}P_{3} \)  üçgenini kesmelidir ( \( \ell \)  nin bir uç noktası  \( P_{1}, P_{2} \)  ve  \( P_{3} \)  noktalarından biri olabilir). O zaman  \( \ell \)   \( [AP_{1}], [AP_{2}], [AP_{3}] \) doğru parçalarının en az birini kesecektir. Demek ki A yeniden yerleştirildiğinde  \( [AP_{1}], [AP_{2}], [AP_{3}]\) doğru parçalarından en fazla ikisi özel olabiliyor ve özel doğru parça sayısı en fazla  \( 2n - 4 + 2 = 2n - 2 \)  oluyor.


A noktası atıldıktan sonra  \( [\boldsymbol{P}_{1}\boldsymbol{P}_{2}], [\boldsymbol{P}_{1}\boldsymbol{P}_{3}], [\boldsymbol{P}_{2}\boldsymbol{P}_{3}] \)  doğru parçalarının hepsi özel ise, A noktası yeniden yerleştirildiğinde n > 4 olduğu için  \( P_{1}P_{2}P_{3} \)  üçgeninin dışında bir Q noktası bulunuyor ve  \( [AQ] \)  doğru parçası  \( [P_{1}P_{2}], [P_{1}P_{3}],[P_{2}P_{3}] \)  doğru parçalarının en az birini kesiyor. Dolayısıyla  \( [P_{1}P_{2}], [P_{1}P_{3}][P_{2}P_{3}] \)  doğru parçalarının en az bini özel olma özelliğini kaybediyor. Sonuç olarak yine özel doğru parça sayısı en fazla  \( 2n -4 + 2 = 2n - 2 \)  oluyor.


text</td>
[[87, 875, 945, 952]]<|/det|>
Son olarak 2n - 2 özel doğru parçasının olabileceğini gösterelim. Bir çember ve bu çember dışında bir A noktası alalım. A noktasından bu çembere çizilen teğetler çemberle X ve Y noktalarında kesişmiş olsun. Küçük XY yayı üzerinde herhangi  \( A_{1}, A_{2}, \ldots, A_{n-1} \)  noktalarını alalım. O zaman  \( [A_{1}A_{2}], [A_{2}A_{3}], \ldots, [A_{n-1}A_{1}], [AA_{1}], [AA_{2}], \ldots, [AA_{n-1}] \)  doğru parçalarının her biri özel doğru parçası