Bir Rubik Küpü Yeterince Karıştırmak İçin En Az Kaç Hamle Gerekiyor?

Rubik küp, 40 yılı aşkındır en popüler bulmacalardan biri. Bu küp aynı zamanda ilginç matematiksel sorular da barındırıyor bünyesinde. Mesela, bir Rubik küpü yeterince karıştırdığınızı nasıl anlarsınız?

Rubik küpü çözmek için birkaç farklı yöntem bulunmuştur. Küpün hareketi; bir yüzünü 90, 180 veya 270 derece çevirmekten geçiyor. Başlangıç durumundaki (yani çözülmüş) küpe farklı hamleler uygulanarak tam tamına 43,252,003,274,489,856,000 farklı durum elde edilebilir.

Bu karmaşıklığa rağmen 2010 yılında Rubik küpün 20 veya daha az hamlede çözülebileceği gösterilmiştir ( http://www.cube20.org/).  Daha önce kullanılan yöntemler 20’den daha fazla hamle içerdiği için bu sayıya “Tanrı Sayısı” denilmiştir.

Bir Rubik Küpü Karıştırmak

Şimdi gelin bu duruma tersten bakalım. Acaba bir Rubik küpü yeterince karıştırmak için en az kaç hamle gerekiyor? Tanrı sayısını hesaplamaktan daha kolay olmalı. En azından küpü karıştırmak  herhangi bir beceri istemiyor.

Benzer soru “iskambil kağıdı karıştırma” olayı için soruldu ve başarıyla cevaplandı. Bu ünlü problem,  matematikçiler Dave Bayer ve Perci Diaconis tarafından yapılan “riffle shuffle (kağıt karma)” adlı 1990 çalışmasında derinlemesine irdelendi ( https://en.wikipedia.org/wiki/Shuffling#Riffle ).

Çalışmaya göre; yapılan gözlemler ve bilgisayar hesaplamaları sonucu bir deste iskambil kağıdını 7 defa karmak, kağıtlarının sırasının yeterince karışmasını sağlayacaktır. 7 defadan az karmak yeterli değildir ve daha fazla karmak da karışıklığı önemli  ölçüde iyileştirmez.

Markov Zinciri

Rubik kübü karıştıracak birisi, üst üste rastgele çevirmeler yapar. Bu şekilde ortaya çıkan bu gibi rastgele durum dizilerine “Markov zinciri” olarak adlandırılır.

Markov zincirinin en kilit noktası, bir olayın gerçekleşme olasılığı, bir önceki veya bir sonraki olayın gerçekleşme olasılığını etkilememesidir.

Markov zinciri teorisini küp karıştırmaya uygulandığında, rastgele hareketlerin sayısı arttıkça olası durumlardan herhangi birinde belirli bir olasılığın 1 / 43,252,003,274,489,856,000’e  yakın hale geldiği anlaşılmaktadır. Matematikçiler bunu “tekdüze olasılık dağılımı” olarak adlandırır, çünkü her olası durum aynı olasılıkla oluşur.

t hamle sonra oluşan olasılık dağılımı D(t) olsun. t arttıkça D(t) azalacaktır. Yani biz küpü karıştırdıkça D(t) küçülecektir.

Kart karıştırma ve bulmaca karıştırmanın yanı sıra, Markov zincir karıştırma teorisinin çok ciddi pratik uygulamaları var. Modern bilim ve mühendislikte en önemli hesaplama araçlarından biri Monte Carlo yöntemidir.

Bu yöntem, adını verdiği ünlü kumarhane gibi temelde şansa dayanmaktadır. Özünde, çok sayıda rastgele tahmin kullanarak zor matematiksel problemleri yaklaşık olarak çözmeye çalışır.

Pratikte, Markov zinciri genellikle bu rastgele durumları üretmek için kullanılır. Markov zincirinde, Monte Carlo yöntemlerinin doğruluğunu anlamak için anahtar görev, t  arttıkça D(t) ‘nin ne kadar hızlı azaldığını tahmin etmektir.

3x3x3 Rubik küpte bu problemi çözmek, henüz çözülmediği için önemli bir meydan okuma olacaktır. Biz şimdilik 2x2x2 lik küpe yoğunlaşalım:

Bu küpte orta parçalar yoktur, sadece köşe parçalar vardır. 3,674,160 olası duruma sahiptir ve Tanrı Sayısı da 11’dir. Şimdi küpü karıştıralım:

11 hamle sonra D(t)=0.695 olur ki bu yüksek bir değer. 19 hamleden sonra D(t) 0.25’in altına düşer. Kaldı ki bu değer Markov zincirleri teorisine göre “the mixing time” (karışma noktası/zamanı) olarak geçer. 25 hamle sonra 0.092 ve 100 hamle sonra 0.00000017…

D(t) değerleri bu şekilde… Peki ama küpün yeterince karışması için en az kaç tane hamle yapalım?

D(t)’nin ne kadar küçük olmasını istediğimize bağlı aslında. Ama Tanrı sayısı kadar hamlenin (11) yetersiz olduğu kesin, değil mi? Sayısal değerleri incelediğimizde 19 hamle tatmin edici …

Daha ayrıntılı D(t) hesapları için: https://en.wikipedia.org/wiki/Markov_chain_mixing_time

Yeterince karıştırdıysak, çözmeye başlayabiliriz…

Şevket ÜNCÜ

Matematiksel

Kaynakça:

https://phys.org/news/2020-01-hard-scramble-rubik-cube.html

Etiketler

Bir cevap yazın

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

Başa dön tuşu