Matematik Olimpiyatı 2021, 2. Aşama, Soru 1

Başlangıçta masadaki iki kutudan biri boş olup, diğerinde farklı renkli 29 bilye bulunmaktadır. Dolu kutuyla başlamak ve kutulara sırayla hamle yapmak üzere her hamlede sırası gelen kutudan bir veya birkaç bilye seçilip diğer kutuya aktarılıyor. Aynı bilye öbeği bir defadan fazla seçilmeden en çok kaç hamle yapılabilir?

Şıklar:

Cevap:  2[29] − 2

Çözüm:
Cevap: 2[29] − 2. 


Toplam hamle sayısının 2[29] −1 olamayacağını gösterelim. Toplam hamle sayısı 2[29] −1 ise 29 elemanlı bilye kümesinin tüm boş olmayan alt kümeleri seçilmiştir. Bir bilyeyi içeren toplam hamle sayısı 2[28] bir çift sayı olduğuna göre, tüm hamleler yapıldıktan sonra tüm bilyeler başlangıçtaki kutuda bulunacaklar. Diğer taraftan 2[29] −1 bir tek sayı olduğuna göre, en son hamleden sonra başlangıçta boş olan kutuda da bilye bulunması gerekiyor, çelişki. Şimdi, hamle sayısının 2[29] −2 olabileceğini gösterelim. 


Birinci Yol: Öncelikle bir lemma kanıtlayacağız. 


Lemma: Başlangıçta iki kutunun biri boş olup diğereinde farklı renkli n > 2 bilye bulunsun. Sadece bir a bilyesini içeren 2[n−1] hamlenin tamamı yapılarak yine başlangıç durumuna dönülebilir. 


İspat: n üzerinden tümevarım yapacağız. Bilyeler {a1, a2, a3, . . ., an} olsun. 


n = 3 durumunda gruplar sırasıyla {a1, a2}, {a1}, {a1, a3}, {a1, a2, a3} olarak seçilirse koşullar sağlanmış olur. n = k için lemma doğru olsun. 


Önce tümevarım varsayımını kullanarak a1 i içeren fakat a2 yi içermeyen 2[n−2] hamlenin tamamını yaparak başlangıç durumuna dönülebilir. Daha sonra yine tümevarım varsayımını kullanarak hem a1 hem de a2 yi içeren 2[n−2] hamlenin tamamını yaparak başlangıc durumuna dönülebilir. Sonuç olarak a1 bilyesini içeren 2[n−1] hamlenin tamamını yapılmış olarak başlangıc durumuna dönülür, lemmanın ispatı tamamlanır. 


Şimdi 2[29] −2 hamlenin yapılabileceğini gösterelim. Lemma’ya göre, önce a1 i içeren tüm hamleler, sonra a1 i içermeyen ve a2 yi içeren tüm hamleler, sonra a1, a2 yi içermeyen ve a3 ü içeren tüm hamleler,..., sonra a1, a2, ..., a26 yi içermeyen ve a27 yi içeren tüm hamleler yapılabilir. Bundan sonra gruplar {a28, a29} ve {a28} olarak seçilirsa, olası 2[29] −1 hamleden {a29} dışındaki tamamı yapılmış olur. 


İkinci Yol: n üzerinden tümevarım yaparak her n ≥ 2 için, yapılmayan tek hamle {a1}, tüm hamleler yapıldıktan sonra a1 bilyesinin başlangıçta boş olan kutuda, diğer bilyelerin ise başlangıçta

bulundukları kutuda olacak şekilde \(2^n - 2\) hamle yapılabileceğini gösterelim. 


\(n = 2\) durumunda gruplar sırasıyla \(\{a_1, a_2\}, \{a_2\}\) olarak seçilirse koşullar sağlanmış olur. 


\(n = k\) durumunda hamlelerin yapılabileceğini varsayalım. \(n = k + 1\) durumunda ilk olarak \(a_{k+1}\) bilyesini ayırıp kalan bilyelere \(n = k\) durumundaki \(2^k - 2\) hamleyi yapalım ve sonra \(a_{k+1}\) bilyesini diğer kutuya aktaralım. Bundan sonra tümevarım varsayımına göre \(a_{k+1}\) ile aynı kutuda sadece \(a_1\) bilyesi bulunacaktır. \(a_1\) ve \(a_{k+1}\) bilyelerini aynı anda başlangıç kutusuna aktarırsak tüm bilyeler başlangıçtaki kutuda bulunmuş olur. Son olarak \(n = k\) durumundaki \(2^k - 2\) hamleyi her hamleye \(a_{k+1}\) bilyesini ekleyerek uygularsak \(2^k - 2 + 2 + 2^k - 2 = 2^{k+1} - 2\) hamle yapılmış olur.