Tübitak Lise 1. Aşama 2024 Soru 16

[matematikolimpiyati]

Bir dik koordinat düzleminde, $0 \leq x \leq 9$ ve $0 \leq y \leq 9$ koşullarını sağlayan tam sayı koordinatlı $(x,y)$ noktalarının $N$ tanesi boyanmıştır. Üç köşesi de boyalı olan bir dik üçgen bulunmuyorsa $N$ en fazla kaç olabilir?

$\textbf{a)}\ 16  \qquad\textbf{b)}\ 18  \qquad\textbf{c)}\ 20  \qquad\textbf{d)}\ 22  \qquad\textbf{e)}\ 26$

[Lokman Gökçe]

Yanıt: $\boxed{B}$

Genel olarak $n\times n$ tane noktadan oluşan karesel bir sistemde, en fazla $N=2n-2$ tane boyalı nokta işaretlenirse, dik üçgen bulunmayan bir konfigürasyon elde etmek mümkündür. Bunun örneğini verelim:

En üst satırdaki ilk soldan $n-1$ noktayı boyayalım. Sağ üst köşedeki noktayı boyamayalım. Bu boyasız noktanın altında kalan, (yani en sağdaki sütundaki) $n-1$ noktayı da boyayalım. Toplam $2n-2$ nokta vardır. Bu noktaların herhangi üçü seçilirse daima geniş açılı üçgen oluşturur. Dik üçgen oluşmaz. Bizim problemimizde $n=10$ olup $10\times 10$ noktadan oluşan bir karesel sistem vardır. Dolayısıyla $N_{\max} = 2\cdot 10 - 2 = 18$ dir.


$N>2n-2$ olursa, neden mutlaka bir dik üçgen oluşmak zorundadır? Bu problemi ve ispatını da 2022 Kasım-Aralık tarihlerinde, sitemizdeki Satranç Tahtası - Boyama başlığında sunmuştuk.


Not: İspat, (muhtemelen bir dahi olan) öğrencim Andrew Carratu'ya aittir. Bazı anekdotlar için bağlantıyı okuyabilirsizin.

[geo]

Bir satırdaki boyalı noktaların sayısı $0$ ya da $1$ ise o satıra hafif, aksi halde ağır diyelim.
Benzer şekilde sütunları da hafif ve ağır diye tanımlayalım.

Bir ağır satır ile bir ağır sütun boyalı bir noktada kesişmişse bir dik üçgen oluşmuş demektir. Böyle bir durum istemiyoruz.
Tüm satırlar hafifse, en fazla $10$ boyalı nokta var demektir.
Tüm sütunlar hafifse, yine en fazla $10$ boyalı nokta vardır.
Boyalı nokta sayısını daha da artırmak istiyoruz.
Bir ağır satırın tüm noktaları boyalı ise tüm satırlar hafif olmalı. Bu durumu az önce ele almıştık. Benzer durum, sütunlar için de geçerlidir.

En az bir ağır satır ve en az bir ağır sütunun olduğu duruma bakalım:
Ağır satırlardaki boyalı noktaların her biri, bir hafif sütunda yer almalı. Bu hafif sütunlar farklıdır; çünķü bu durumda hafif sütunda en az iki boyalı nokta olur. O halde ağır satırlardaki boyalı nokta sayısı en fazla hafif sütun sayısı kadardır. En az bir ağır satır ve en az bir ağır sütun olduğu durumu incelediğimiz için, en fazla $9$ hafif sütun olacaktır.
Benzer şekilde; ağır sütundaki boyalı noktaların her biri, bir hafif satırda yer almalı. Bu hafif satırlar farklı olacağı için, sütunlardaki boyalı noktaların sayısı en fazla hafif satır sayısı kadar, yani $9$ olacaktır.
Yani, en az bir satır ve en az bir sütunun ağır olduğu durumda, en fazla $18$ nokta boyalı olabilir. Diğer durumlarda en fazla $10$ nokta boyalı olabilir.

$18$ boyalı nokta için örnek durum; $(1,0),(2,0),\dots,(9,0),(0,1),(0,2),\dots , (0,9)$ şeklinde verilebilir.

Kaynak:
Bu çözüm,
Mathematical Olympiads 2000-2001: Problems and Solutions from Around the World, Titu Andreescu, Zuming Feng, George Lee. Syf. 153-154. kitabındaki USAMO 2000/4 sorusuna yapılmış çözümün uyarlanmış halidir.
USAMO 2000'deki soru; $0\leq x \leq 999$ ve $0\leq y \leq 999$ şartıyla, dik kenarları eksenlere paralel olan dik üçgen şeklinde sorulmuş. Bizim sorumuzda eksenlere paralel şartı olmadığı için örnek $18$ nokta seçerken dış satır ve sütunları seçmemiz gerekir.

Diğer çözümler için bkz. AoPS.