Tübitak Lise 2. Aşama 1998 Soru 3

[Lokman Gökçe]

Bir çemberin üstündeki noktalar üç renge boyanıyorlar. Köşelerini çember üstünde aynı renge boyanmış noktaların oluşturduğu sonsuz sayıda ikizkenar üçgenin bulunduğunu gösteriniz.

[geo]

Köşeleri çember üstünde bulunan herhangi bir düzgün $13$-gen alalım. Bu $13$-genin aynı renge boyanmış en az beş köşesi vardır. Bu beş köşeden en az üçünün ikizkenar bir üçgen oluşturduğunu göstereceğiz. Bu ise ${{\mathbb Z}}_{13}=\left\{1,\dots ,13\right\}$ kümesinin $5$ elemanlı herhangi bir $P$ altkümesinde $x\ne y$, $x+y\equiv 2z \pmod {13}$ olacak biçimde $x,y,z\in P$ bulunduğunu göstermeye eşdeğerdir. Son önermenin doğru olmadığını varsayalım. $$S=\left\{x+y \pmod {13}|x,y\in P,\ x\ne y\right\}$$ dersek, $S$'nin en az $9$ değişik elemanının olduğu görülür. ( $P=\left\{x,y,z,u,v\right\}$ olsun ve $x+y\equiv z+u$ olduğunu varsayalım. Bunun dışında $P$'den alınan iki değişik çiftin toplamları $\pmod {13}$ eşitse, genelliği yitirmeden, bunun $z+y\equiv x+v$ biçiminde olacağı görülür. O zaman da, varsayımımızın aksine $u+v\equiv 2y$ olur.) Ancak bu durumda da, $S$'ye ait en az bir eleman $\left\{2x,2y,2z,2u,2v\right\}$ kümesine aittir.

Kaynak:
Matematik Dünyası 1999-III

[geo]

Van der Waerden teoremi gereği, $1,2,\dots , n$ dizisinde $3$ renkli $3$ terimli aritmetik alt dizi bulunabilir. Bu şekildeki en küçük $n$ sayısı $W(3,3)=27$ dir. Bu da düzgün $27-$gende tek renkli bir ikizkenar üçgen olacağı anlamına gelir.

Bizim sorumuzda aritmetik dizi $\bmod n$ ye göre çembersel olabileceği için daha az köşeli bir $n-$gen bulunabilir. (Bir önceki çözümde $n=13$ ün sağladığı gösterilmişti.)

Wikipedia'daki makalede Van der Waerden Teoremi'nin $3$ renkli $3$ terimli aritmetik alt dizi için ispatı verilmiş. Örnek olarak da $n=7(2\cdot 3^7+1)(2\cdot 3^{7\cdot (2\cdot 3^7+1)}+1)$ terimli bir dizi seçilmiş. Yani Van der Waerden teoreminden çıkan sonuç, yeterince büyük $n$ ler için aritmetik alt dizi bulunabileceği. Wikipedia'daki $W(3, 3)\leq 7(2\cdot 3^7+1)(2\cdot 3^{7\cdot (2\cdot 3^7+1)}+1)$ için verilen ispat bu sorunun çözümü için verilebilir.

[geo]

Matematik Dünyası'nda yer alan resmi çözümden faydalanarak sonuca gidebildiğimi düşünüyorum; ama resmi çözümdeki her önermeyi doğrulayamıyorum. O yüzden resmi çözümden faydalanarak yaptığım kendi çözümümü (anlayışımı) paylaşıyorum.

Düzgün $13$-geni ele alalım. Güvercin Yuvası İlkesi gereği aynı renkte $\left \lceil \frac {13}{3} \right \rceil = 5$ köşe vardır.
Köşeleri $1,2,\dots, 13$ olarak numaralandıralım. Herhangi üç köşe arasında $\bmod 13$ te aritmetik dizi oluşuyorsa bu üç köşe ikizkenar üçgen oluşturur. Bu da $z-x \equiv y - z \pmod {13}$, eşdeğer biçimde $x+y \equiv 2z \pmod {13}$ anlamına gelir.
Aynı renkli $5$ köşe arasında ikizkenar üçgenin varlığını ispatlarsak, düzgün $13$-geni merkezi etrafında $\alpha \in \left [0,\tfrac {2\pi}{13}\right )$ döndürerek sonsuz sayıda çokgen elde ederiz. Dolayısıyla sonsuz sayıda ikizkenar üçgen elde ederiz.

Aynı renki köşeler $P = \{x,y,z,u,v\}$ olsun. Bunlardan hiçbirisi için $a+b \equiv 2c \pmod {13}$ şeklinde bir ilişki olmadığını varsayalım.
$5$ sayı, $\binom {5}{2} = 10$ ikili belirtir: $x+y, x+z, x+u, x+v, y+z, y+u, y+v, z+u, z+v, u+v$. Bu sayılardan bazıları birbirine eşit olabilir. Bu sayıların oluşturduğu kümeye $S$ diyelim. $S$ nin herhangi bir elemanı $S' = \{2x,2y,2z,2u, 2v\}$ kümesinde yer almamalı. $2x \equiv 2y \Leftrightarrow x \equiv y \pmod {13}$ olacağı için ve $|P|=5$ olduğu için $S'$ kümesi tam olarak $5$ elemanlıdır. $|S| + |S'| \leq 13$ olacağı için $|S| \leq 8$ dir.
Bu da $S$ nin (bazıları tekrarlı) $10$ eleman adayı arasından üç tanesi arasında $a \equiv b \equiv c \pmod {13}$ bağıntısı ya da $a \equiv b \  \land \ c \equiv d \pmod {13}$ bağıntısı sağlayan $4$ farklı eleman adayı olması gerektiği anlamına gelir.
Önce $a \equiv b \equiv c \pmod {13}$ olamayacağını, sonra da $a \equiv b \  \land \ c \equiv d \pmod {13}$ şeklindeki sayıların varlığının varsayımımız üzerinde bir çelişki oluşturacağını göstereceğiz.

$x+y \equiv y +z \pmod {13}$ olamaz; çünkü bu $x \equiv z \pmod {13}$ anlamına gelir. Bu durumda $|P|=5$ olduğu için üç ayrık çift bulamayız. (Bunun için en az $6$ eleman gerekirdi.)

Diğer duruma geçelim: $a \equiv b \  \land \ c \equiv d \pmod {13}$
$a = x+y$, $b=z+u$ olsun.
$c = x+z$ ise $d = y + u$ ya da $d = y+v$ ya da $d = u+v$ olabilir.

$d = y+ u$ olamaz; çünkü $a+c \equiv b+d$ den $2x \equiv 2u \Rightarrow x \equiv y \pmod {13}$.

$d = y +v$ olduğunda $a+c \equiv b+d$ den $2x \equiv u + v \pmod {13}$ olacağı için bu varsayımımız ile çelişir.

$d = u+v$ olduğunda $b+x \equiv a+d$ den $2z \equiv y + v \pmod {13}$ olacağı için bu varsayımımız ile çelişir.

Bu durumda $S$ kümesi $S'$ kümesinden en az bir eleman içerir. Yani düzgün $13$-gende her zaman en az bir tek renkli ikizkenar üçgen elde ederiz.

Not: Burada verilen çözüm, resmi çözüm ile neredeyse aynı. Resmi çözümde bence "$S$'nin en az $9$ değişik elemanının olduğu görülür." yerine  "$S$'nin en fazla $8$ değişik elemanının olduğu görülür." denmeliydi.

[geo]

Çember üzerindeki noktaları sonsuz sayıda düzgün $13-$genlere bölelim. Her $13-$gen için, Güvercin Yuvası Prensibi'ne göre en az $5$ aynı renkte köşe bulunur: bu renk kırmızı olsun. Bu $5$ köşenin herhangi bir dağılımında tek renkli ikizkenar üçgen oluşacağını göstereceğiz. Bu nedenle her $13-$gen içinde tek renkli ikizkenar üçgen bulunacak. Sonsuz sayıda $13-$ gen için sonsuz sayıda tek renkli ikizkenar üçgen olacaktır.

İddia: Düzgün bir $13-$genin $5$ köşesi kırmızı renkli ise, bu $5$ köşeden $3$ ü ikizkenar üçgen olacak şekilde seçilebilir..

İspat: Bu $5$ köşenin hiçbirinin ikizkenar üçgen oluşturmadığını varsayalım. Köşeleri $P_0, \ldots, P_{12}$ olarak adlandıralım. $\bmod {13}$ te alınan indislerle, öncelikle $P_i$ ve $P_{i+2}$'nin her ikisinin de kırmızı olamayacağını kanıtlayalım. Aksini varsayalım. Genelliği yitirmeden, $P_{12}$ ve $P_1$ kırmızı olsun; o zaman $P_{10}, P_0$ ve $P_3$ kırmızı olamaz. Ayrıca, $\left(P_{11}, P_4\right),\left(P_4, P_7\right)$ ve $\left(P_7, P_8\right)$ çiftlerinden her birinden en fazla bir köşe kırmızı olabilir; aksi halde her biri $P_1$ ile ikizkenar üçgen oluşturur. Benzer şekilde, $\left(P_2, P_9\right),\left(P_9, P_6\right)$ ve $\left(P_6, P_5\right)$ çiftlerinden her birinden en fazla bir köşe kırmızı olabilir. Bu durumda $\left\{P_{11}, P_4, P_7, P_8\right\} \cup\left\{P_2, P_9, P_6, P_5\right\}$ kümesinden üç köşe kırmızıdır; genelliği yitirmeden iki köşenin $\left\{P_{11}, P_4, P_7, P_8\right\}$ kümesinden geldiğini varsayalım. $P_4$ ve $P_8$ köşelerinin her ikisi de kırmızı olamaz; çünkü $P_{12}$ ile ikizkenar üçgen oluştururlar. Benzer şekilde $P_{11}$ ve $P_8$ ikisi birden kırmızı olamaz; çünkü $P_1$ ile ikizkenar üçgen oluştururlar. Bu nedenle $P_{11}$ ve $P_7$ köşeleri kırmızı olmalıdır. Ancak sonra kalan $P_2$, $P_5$, $P_6$, $P_9$ köşelerinden herhangi bir köşe, $P_1, P_7, P_{11}, P_{12}$'den ikisi ile ikizkenar üçgen oluşturur. Çelişkiden dolayı $P_i$  ve $P_{i+2}$ her ikisi birden kırmızı olamaz.

Şimdi $P_i$ ve $P_{i+1}$'in kırmızı olamayacağını kanıtlamamız gerekiyor. Varsayalım ki öyle. Genelliği yitirmeden $P_6$ ve $P_7$ kırmızı olsun. O zaman son paragraftaki sonuç nedeniyle $P_4, P_5$, $P_8$ ve $P_9$ kırmızı olamaz. $P_0 P_6 P_7$ üçgeninin ikizkenar olması nedeniyle $P_0$ da kırmızı olamaz. $\left(P_3, P_{11}\right)$ ve $\left(P_{11}, P_1\right)$ çiftlerinden her biri en fazla bir kırmızı köşe içerebilir; çünkü $P_3 P_7 P_{11}$ ve $P_1 P_6 P_{11}$ üçgenleri ikizkenar olur. Ayrıca, bir önceki paragraftaki sonuç nedeniyle $P_1$ ve $P_3$ köşelerinin ikisi birden kırmızı olamaz. Bu nedenle $\left\{P_1, P_3, P_{11}\right\}$ kümesinden en fazla biri kırmızı olabilir. Benzer şekilde, $\left\{P_{12}, P_{10}, P_2\right\}$ kümesinden en fazla biri kırmızı olabilir. Ancak o zaman en fazla dört kırmızı köşemiz olur, yine bir çelişki oluşur.

Bu nedenle eğer $P_i$ kırmızı ise, $P_{i-2}, P_{i-1}, P_{i+1}, P_{i+2}$ kırmızı olamaz; o zaman en fazla dört kırmızı köşemiz olur, yine bir çelişki oluşur.

Kaynak: Mathematical Olympiads 1999–2000: Problems and Solutions from Around the World, Syf. 192-193.