Genç Balkan Matematik Olimpiyatı 2015 Soru 4

[Eray]

Bir L-şekli, her biri üç birim kare kaplamak üzere aşağıdaki dört parçadan biridir:

$25$ birim kare içeren $5 \times 5$ bir tahta, bir $k\le25$ pozitif tamsayısı ve yeterli miktarda L-şekli veriliyor. A ve B isimli iki oyuncu şu şekilde bir oyun oynuyorlar: oyuna A başlamak üzere, sırası gelen oyuncu daha önce işaretlenmemiş bir birim kareyi işaretliyor. $k$ birim kare işaretlendiğinde oyun bitiyor.

Oyun sonunda işaretlenmemiş karelere L-şekilleri, her bir L-şekli üç işaretlenmemiş birim kare kaplayacak şekilde yerleştiriliyor. L-şekilleri üst üste gelmiyorsa, bu tür yerleştirmeye iyi yerleştirme diyoruz.

Her iyi yerleştirmede en az üç işaretlenmemiş birim kare kalıyorsa, oyunu B kazanıyor. B'nin kazanma stratejisinin bulunduğu en küçük $k$ sayısını belirleyiniz.

[alpha]

$k=4$ için B'nin kazanma stratejisini göstermeden önce cevabın 4'ten küçük olamayacağını gösterelim.

$\bullet k=1$ için B'nin kazanamadığı açıktır.

$\bullet k=2$ için A ortadaki noktayı işaretler,

B hangi noktayı işaretlersen işaretlesin, B'nin işaretlediği noktadaki yukarıdaki şekildeki yerleştirmede noktayı içine alan L-şekli çıkarılınca
2 boş karenin kaldığı iyi bir yerleştirme ortaya çıkar ki bu durumda B kazanamaz.

$\bullet k=3$ için A yukarıdaki hamlesinin aynısını yapar , 2. hamlesinde ise A yukarıdaki durumda boş kalan 2 noktadan birin işaretler ve B yine kazanamaz.

Şimdi B'nin $k=4$ için kazanma stratejisini gösterelim:

B, A hangi kareyi işaretlerse işaretlerse işaretlesin şekildeki 2 kareyi işaretler (Eğer A bu karelerden birini işaretlerse diğer rastgele bir kare işaretleyebilir o kare yerine)

Şimdi o 2 kare işaretlendiğinde elde edilebilecek tüm iyi yerleştirmelerde en az 5 karenin boş kaldığını gösterelim.

Tahtayı şekilde gibi siyah beyaz boyarsak 13 siyah ve 12 beyaz kare olduğunu görürüz ancak 2 beyaz renk işaretlendiği için 13 siyah ve 10 beyaz kare vardır.
Bir L-şeklinde,  2 beyaz ve  1 siyah veya 2 siyah ve 1 beyaz kare bulunulabilir.
Şekle , 2 tane siyah kare içeren en fazla 4 tane L-şekli sığabildiği açıkça gözükmektedir.
Bu durum 5'ten az karenin kalabileceği tek dağılım türü 4 tane 2 siyah kare içeren , 3 tane 2 beyaz içeren L-şeklinin bulunduğudur.
Bu dağılımı yaparken bütün siyah kareler kullanılmalıdır ancak 1.sütun 3.satırdaki siyah kare kapatılmak istendiğinde sol üst veya alt karedeki karelerden biri şekildeki gibi bloke olmaktadır.

Bu yüzden bütün siyah kareler kullanılamamakta ve böyle bir yerleştirme mevcut olmamaktadır.Bu en az 5 karenin kaldığını göstermektedir.Burada beyaz 2 hamlesinde en fazla iki tane boş kareyi işaretler ve geriye en az 3 tane boş kare kalır ki bu durumda B kazanmayı garantiler.Cevap $4$'tür.