Tübitak Ortaokul 1.Aşama 2015 Soru 28

[ERhan ERdoğan]

$1,2,\cdots,20$ sayılarının her biri kırmızı ve mavi renklerden birine, her $k=1,2,\cdots,a$ için farkları $k$ olan iki kırmızı ve iki mavi sayı bulunacak biçimde boyanabiliyorsa, $a$ nın alabileceği en büyük değer nedir?

$
\textbf{a)}\ 14
\qquad\textbf{b)}\ 15
\qquad\textbf{c)}\ 16
\qquad\textbf{d)}\ 17
\qquad\textbf{e)}\ 18
$

[çılgın]

Yanıt: $\boxed{D}$

$1$ den $17$ ye tüm farkların bulunduğu bir diziye örnek olarak $KKMMMMMMMKMKKKKKKKMM$ verilebilir, örneğin doğruluğu kolayca kontrol edilir.

Şimdi $1$ den $18$ e tüm farkların bulunduğu bir boyama olamayacağını gösterelim. $(1,19),(2,20)$ ikililerinden tam olarak biri mavi, biri kırmızı olmak zorundadır. Genelliği bozmadan $1$ ve $19$ mavi, $2$ ve $20$ kırmızı olsun. $17$ fark oluşturabilecek mavi ikilileri $(1,18),(2,19),(3,20)$ dir, fakat $2$ ve $20$ kırmızı olduğundan $(1,18)$ kalır ve $18$ mavi olmak zorundadır. Aynı şekilde $3$ kırmızı olmak zorundadır. $16$ fark oluşturacak mavi ikilileri $(1,17),(2,18),(3,19),(4,20)$ olur fakat $2,3,19$ kırmızı olduğundan $(1,17)$ kalır ve $17$ mavi olmak zorundadır. Bu şekilde devam ederek $MKKKKKKKKKMMMMMMMMMK$ dizisine ulaşırız ki arasındaki fark $9$ olan bir ikili yoktur yani şartı sağlamaz, dolayısıyla $a$ en fazla $17$ olabilir.