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

[Eray]

$1,2,\dots,2016$ sayılarının her biri $k$ renkten birine, $a\mid b$ ve $b\mid c$ koşullarını sağlayan herhangi üç farklı $a,b$ ve $c$ sayıları aynı renkte olmayacak şekilde boyanabiliyorsa, $k$ en az kaç olabilir?

$\textbf{a)}\ 4 \qquad\textbf{b)}\ 5 \qquad\textbf{c)}\ 6 \qquad\textbf{d)}\ 7 \qquad\textbf{e)}\ 8$

[KereMath]

1 2 4 8 16 32 64 128 256 512 1024 sayılarından herhangi üçü aynı renge boyanamaz.Herhangi bir renk seçersek buradakilerden en fazla 2 tanesi aynı renge boyanabilir.Burada 11 sayı vardır.5 rengimiz var ise bu sayılardan en fazla 5*2=10 tanesini boyayabiliriz bundan dolayı en az 6 renk vardır.

[geo]

Yanıt: $\boxed C$

Cevap: $6$.

İlk önce en az $6$ renk gerektiğini gösterelim. $1,2,4,8,16,32,64,128,256,512,1024$ sayılarının herhangi üçü aynı renge boyanırsa koşullar sağlanmaz. Demek ki renk sayısı $11 / 2=5.5$ 'den az olmayacaktır. Şimdi $6$ renk ile gereken boyamayı yapalım. $1,2, \ldots, 2016$ sayılarını $11$ gruba ayıralım: $G_1=\{1\}$, $G_2=\{2,3\}$, $G_3=\{4,5,6,7\}$, $G_4=\{8,9,10, \ldots 14,15\}$, $\ldots, G_{10}=\{512,513, \ldots, 1022,1023\}$, $G_{11}=\{1024,1025, \ldots, 2015,2016\}$. Aynı gruptaki herhangi iki sayıdan daha küçük olan daha büyük olanı bölmüyor. Bu nedenle her renk en fazla iki grupta kullanılmak üzere, her gruptaki sayıların tümü aynı renge boyanırsa koşullar sağlanmış olur.

Kaynak: Tübitak 24. Ulusal Matematik Olimpiyatı Birinci Aşama Sınav Soru ve Çözümleri 2016