Tübitak Lise 1. Aşama 2001 Soru 30

[geo]

Başlangıçta, düzgün bir $n$-genin köşelerinde bulunan $n$ havaalanından $k$ tanesinde birer uçak vardır. Her gün, bu uçaklardan her biri, o gün bulunduğu havaalanının en yakınındaki iki havaalanından birine uçuyor. Başlangıç dağılımı ne olursa olsun, bütün uçakların günün birinde aynı havaalanında toplanması, aşağıdaki $(n, k)$ sıralı ikililerinden hangisi için olanaksızdır?

$
\textbf{a)}\ (10, 6)
\qquad\textbf{b)}\ (10, 4)
\qquad\textbf{c)}\ (11, 3)
\qquad\textbf{d)}\ (11, 5)
\qquad\textbf{e)}\ (13, 8 )
$

[Lokman Gökçe]

Yanıt: $\boxed{A}$

İddia 1: $n$ nin çift sayı olması durumunda $k>\dfrac{n}{2}$ iken bütün uçakların aynı havaalanında toplanması olanaksızdır. $k \leq\dfrac{n}{2}$ iken bütün uçakların aynı havaalanında toplanması mümkündür.

İddia 2: $n$ nin tek sayı olması durumunda $k$ nın her değeri için bütün uçakların aynı havaalanında toplanması mümkündür.

Bu iddialara göre $(n,k)=(10,6)$ durumunda uçakların aynı havaalanında toplanması olanaksız olduğunu anlarız. Şimdi Bu iddiaları ispat edelim.

İddia 1'in İspatı: Düzgün $2n$ genin köşeleri $A_0A_1\dots A_{2n-1}$ ve saat yönünde sıralanmış olsun. Tüm uçakların toplanacağı havaalanının $A_0$ olduğunu kabul edelim. $A_m$ havaalanındaki bir uçak $A_0$ a (saat yönünde veya ters yönde ilerlemesi durumuna göre) $m$ günde ya da $2n-m$ günde gidebilir. $m$ ve $2n-m$ sayılarının pariteleri (çift-tek durumları) aynıdır. Bunun anlamı: örneğin, $A_3$ deki bir uçak $A_0$ a tek sayı bir günde ulaşabilrken $A_4$ deki bir uçak $A_0$ a çift sayı bir günde ulaşabilir. Dolayısıyla pariteleri farklı olan uçaklar asla aynı yerde toplanamazlar. $0$ dan $2n-1$ e kadar olan sayılardan yarısı çifttir, yarısı da tektir. Eğer $k>n$ ise güvercin yuvası prensibi gereği en az bir uçağın bulunduğu yer çift indislidir ve en az bir uçağın bulunduğu yer de tek indislidir. Dolayısıyla bu uçakları asla bir araya getiremeyiz. $k\leq n$ ise $k$ tane uçağı çift indisli yerlere yerleştirerek $A_0$ da toplanmalarını sağlarız.

İddia 2'in İspatı: Düzgün $2n+1$ genin köşeleri $A_0A_1\dots A_{2n}$ ve saat yönünde sıralanmış olsun. Tüm uçakların toplanacağı havaalanının $A_0$ olduğunu kabul edelim. $A_m$ havaalanındaki bir uçak $A_0$ a (saat yönünde veya ters yönde ilerlemesi durumuna göre) $m$ günde ya da $2n+1-m$ günde gidebilir. Bu sayılardan biri çift iken diğeri tektir, yani pariteleri farklıdır. Dolayısıyla herhangi bir şehirdeki uçağı $A_0$ a istersek tek günde, istersek çift günde ulaştırabiliriz. Dolayısıyla çokgenin kenar sayısı tek sayı iken $k$ nın her değeri için bütün uçakların aynı havaalanında toplanması mümkündür.