Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde de kullanılan ve normal gösterim elde etmeyi hedefleyen, özellikle de sondan normal şekil gösterimi için oynanan bir oyundur.

Oyunun aşağıda tanımlı olan kuralları ile MU kelimesinin elde edilip edilemeyeceği sorulur:

  1. Oyunda kullanılabilecek harfler M, I ve U’dur. Bu harfler dışında harf kullanılamaz.
  2. Oyuna MI kelimesi ile başlanır.
  3. Oyundaki kelimenin sonuna, U harfi eklenebilir. (Örneğin MI kelimesi MIU yapılabilir)
  4. Oundaki M harfinden sonra gelen harfler ikiye katlanabilir (Örneğin MIU kelimesi, MIUIU şeklinde, M harfinden sonra gelen IU kelimesini iki kere yazarak elde edilmiştir)
  5. Ardışık olarak tekrar eden I harfleri U harfine dönüşebilir. Örneğin MUIIIU kelimesi MUUU kelimesine dönüştürülebilir.
  6. Çift U harfi silinebilir. Örneğin MUUU kelimesi, MU kelimesine dönüşebilir.

Sorumuz, başlangıçta bulunan MI kelimesinin, yukarıdaki kurallar kapsamında MU olarak yazılıp yazılamayacağıdır.

Sorunun cevabı, bu şekilde bir geçişin imkansız olduğudur.

Bu tip bir problemin çözümünde bir “yeksan” (invariant, değişmez) aramak gerekir. Yani problemdeki değişen durumlara karşı yeksan olan (değişmeyen) bir kararlı hal yakalanabiliyor mu diye bakılması gerekir.

Çözümün ispatlanması sırasında I harfi içeren kelimelere bakmamız gerekir. Bu harfin (I) sayısını değiştiren kurallar, yukarıdaki listede, 4. ve 5. Kurallardır. 4. kural, sondaki harfleri iki misline katlamaktadır. Dolayısıyla sonda bulunan I harfi kaç tane ise bunun sayısı iki misline katlanacaktır. 5. kuralda ise I harfleri U harfi ile değişebilmektedir.

Bu iki kural dışında I harfinin sayısını değiştiren bir kural yoktur.

Ayrıca, başlangıçta 1 adet I harfi ile başlanmaktadır.

Şimdi kurallarımızı tekrar gözden geçirdiğimizde, I harflerinin sayısının 2 misline çıkabildiğini veya 3 I harfinin U harfine döndüğünü görürüz. Ayrıca oyunun bitmesi için hiç I harfi bulunmamalıdır.

Bu şartlarda oyun bitmez çünkü:

  • Başlangıçtaki I sayısı (ki 1ile başlar) 3’e tam bölünmez.
  • 3’e tam bölünemeyen bir sayının iki misli de üçe bölünmez.
  • 3’e bölünemeyen bir sayıdan 3 çıkarmak ta sayıyı 3’e bölünür hale getirmez.

Dolayısıyla hiç I içermeyen MU kelimesine ulaşılması imkansızdır.

Yorumlar

Ersin için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir