Fantezi Cebir > Kombinatorik

Satranç Tahtası - Boyama

(1/1)

Eray:
$100\times100$ boyutunda bir satranç tahtasında bazı birim karelerin merkezleri siyah renge boyanacaktır. Birim kare merkezlerinden üçü birden siyaha boyalı olan hiçbir üçlü dik üçgen oluşturmayacak şekilde en fazla kaç birim kare merkezi siyaha boyanabilir?

Lokman Gökçe:
Çözüm:


Bir satırın tamamı ($100$ karenin merkezi) siyah renge boyanamaz. Aksi halde diğer bir boyayacağımız $101$. kare ile dik üçgen oluşur. Aynı şekilde bir sütunun tamamı siyah renkle boyanamaz diyebiliriz. Şimdi $a$ tane satırda en az $2$ şer kare ve $b$ tane satırda tam $1$ kare boyanmış olsun. Bir sütunun $a$ satırdan her biriyle kesişiminde en fazla $1$ boyalı kare olmalıdır. Aksi halde, o sütunda $2$ boyalı kare olursa dik üçgen oluşturur. Bu $a$ tane satırda toplamda en fazla $99$ kare bulunur. $b$ satırda da birer kare olduğundan tahtada toplam $99 + b$ boyalı kare bulunur. $b\leq 100$ dür fakat $b=100$ iken $a=0$ olur. Bu ise boyalı kare sayısını $100$ yapar, bunu istemiyoruz. O halde $b\leq 99$ dur. Böylece toplamda en fazla $99 + b \leq 198$ boyalı kare elde ederiz. $198$ boyalı kare için örnek durum şudur: En alt satır ve en sağdaki sütunun tüm karelerini boyayalım, fakat köşe kareyi boyamayalım. Bu halde $198$ boyalı kare vardır ve hiç dik üçgen yoktur.

Lokman Gökçe:
Birkaç Anekdot: Bu problem, kombinatorikte az çok bilinen bir problemdir diye tahmin ediyorum. 2002 yılında (bu satırları yazışımdan 22 yıl önce) derlediğim bazı kombinatorik notlarım arasında bu problem vardı ve $1000 \times 1000$ tahta için soruluyordu. Dolayısıyla yanıtı $N=1998$ oluyor. Belki $1998-1999$ yıllarında bir yerde ulusal olimpiyatlarda sorulmuş olabilir.

Kaynağının ne kadar geriye gittiğini bilemiyorum. 2022'de problemi sorarak sitemizde kazandıran, IMO milli takım eski öğrencilerimizden Eray Atay'a teşekkürler.

Ben de problemi tekrar okuduğumda, o esnada 10. sınıfta olan ABD'li öğrencim Andrew Carratu'ya bir olimpiyat dersimizde sormuştum. Benim 2002 notlarımdaki çözüm uzun ve biraz sevimsizdi. Muazzam bir matematik kavrayışına sahip Andrew, yukarıda paylaştığım çözümü çabucak bulmuştu. Kendisi 10. sınıfın sonunda MOSP'a (2023 Mathematical Olympiad Summer Program) ve 11. sınıfta (2024 Şubat'ta) ABD matematik milli takımına davet edildi. Son olarak 2024 MOSP'a bir kez daha davet aldı. Umarım, ABD IMO takımına asil üye olarak seçilmeyi başarır.

geo:
Sorunun kaynağı: USAMO 2000/4
Diğer çözümler için bkz. AoPS.

Navigasyon

[0] Mesajlar