Aklıma ilk gelen yöntem şu şekildeydi. İçinde kağıt olan kutuyu göstermek için birden fazla yazı tura dizilimi tanımlayabilirsem ve bunların her birine hangi konumdan olursa olsun tek bir yazı tura değişimiyle gelebilirsem o zaman soruyu çözmüş olurum. Dört kutu ve dört para var. Dört para için toplam 16 tane değişik yazı tura dizilimi var. Her bir kutu için dört tane dizilim kullanma şansım var yani. Peki bunları yukarıdaki varsayımıma uygun bir şekilde seçebilir miyim?
Öncelikle birinci kutu için seçeceğim ilk para diziliminin herhangi bir dizilim olabileceğini düşündüm. Diyelim ki YYYY (yazı – yazı – yazı – yazı) dizilimi birinci kutuda kağıt var anlamına gelsin. Bu durumda gardiyan kağıdı birince kutuya koyduktan sonra paraların durumu YYYY de olabilir. Yani bu dizilimden bir yazıyı tura yaptığım dizilimin de birinci kutu anlamına gelmesi lazım. Bu dizilimi de YYYT şeklinde seçeyim.
Şimdi YYYY ve YYYT dizilimlerine tek bir değişimle erişebilen dizilimleri bulmaya çalışayım.
Not: Burada dizilimlere ayrıca sayısal bir değer vereceğim ki, tabloların bütünlüğü daha kolay anlaşılsın. Dizilimlerin sayı değerini hesaplarken ikilik düzeni kullanacağım. Y için 0, T için 1 değerini kullanacağım ve dizinin onluk düzendeki değerini dizinin yanında parantez içinde göstereceğim.
YYYY (0) -> YYYT (1) YYYT (1) -> YYYY (0) YYTY (2) -> YYYY (0) YYTT (3) -> YYYT (1) YTYY (4) -> YYYY (0) YTYT (5) -> YYYT (1) TYYY (8) -> YYYY (0) TYYT (9) -> YYYT (1)
Bu şekilde sekiz dizilim için ilk kutuyu gösterebileceğim iki dizilim bulmuş oldum. Kalan sekiz dizilim için de birinci kutuyu simgeleyen iki dizilim bulmam lazım şimdi. Aklıma ilk gelen fikir yukarıdaki tablonun tam tersini almak oldu. Yani T yerine Y ve Y yerine T olacak şekilde seçimlerimi yapabilirim belki. Bu şekilde yukarıdaki tabloda olmayan dizileri elde edeceğimi göstermem lazım. Bunun en kolay yolu tabii ki yeni tabloyu yazmak olacaktır.
TTTT (15) -> TTTY (14) TTTY (14) -> TTTT (15) TTYT (13) -> TTTT (15) TTYY (12) -> TTTY (14) TYTT (11) -> TTTT (15) TYTY (10) -> TTTY (14) YTTT (7) -> TTTT (15) YTTY (6) -> TTTY (14)
Böylece birinci kutuyu simgeleyecek dört adet dizilim bulmuş oldum: YYYY, YYYT, TTTT, TTTY. Olası her dizilimden bu dizilimlere tek bir hareketle geçiş yapabiliyorum.
Şimdi ikinci kutu için bir seçim yapayım. Şimdiye kadar seçtiğim dört dizilim dışındaki herhangi bir dizilim başlangıç için işe yarayacaktır. Örneğin YYTY dizisini alayım. Şimdi yine yukarıdaki mantığı yürüterek başlangıçta bu dizilimin oluşabileceğini varsayıp tek bir değişimle elde edebileceğim ve daha önce seçilmemiş başka bir dizilim seçeyim. O da YYTT olsun. Yine yukarıdaki gibi bu iki dizilime tek bir değişimle ulaşılabilen dizilimleri yazayım.
YYYY (0) -> YYTY (2) YYTT (3) -> YYTY (2) YTTY (6) -> YYTY (2) TYTY (10) -> YYTY (2) YYTY (2) -> YYTT (3) YYYT (1) -> YYTT (3) YTTT (7) -> YYTT (3) TYTT (11) -> YYTT (3)
Aynı şekilde bu dizilimlerin terslerini aldığımda da kalan dizilimler için gereken ikinci kutu çözümlerini de şu şekilde yazabilirim:
TTTT (15) -> TTYT (13) TTYY (12) -> TTYT (13) TYYT (9) -> TTYT (13) YTYT (5) -> TTYT (13) TTYT (13) -> TTYY (12) TTTY (14) -> TTYY (12) TYYY (8) -> TTYY (12) YTYY (4) -> TTYY (12)
Böylece ikinci kutuyu kodlamak için şu dizilimleri bulmuş oldum: YYTY, YYTT, TTYT ve TTYY.
Bu yöntem madem şimdilik çalışıyor gibi gözüküyor, o zaman devam edeyim. Üçüncü kutuyu kodlama için bu sefer YTYY dizilimiyle başlayayım. Yukarıdaki yöntemleri tekrarlayacağım. Başlangıç dizisi YTYY olabileceğine göre tek değişiklikle ulaşabileceğim ama daha önceki kutular için seçmediğim bir dizilim seçeyim. Örneğin, YTYT. Tekrar bu dizilimlere her dizilimden tek bir değişiklikle geçebilir miyim kontrolünü yapayım.
YTYT (5) -> YTYY (4) YTTY (6) -> YTYY (4) YYYY (0) -> YTYY (4) TTYY (12) -> YTYY (4) YTYY (4) -> YTYT (5) YTTT (7) -> YTYT (5) YYYT (1) -> YTYT (5) TTYT (13) -> YTYT (5)
Yine sekiz değişik dizilimden bu iki dizilime geçebildim. Şimdi bunların da tersleri dizilimleriyle kalan tabloyu oluşturayım.
TYTY (10) -> TYTT (11) TYYT (9) -> TYTT (11) TTTT (15) -> TYTT (11) YYTT (3) -> TYTT (11) TYTT (11) -> TYTY (10) TYYY (8) -> TYTY (10) TTTY (14) -> TYTY (10) YYTY (2) -> TYTY (10)
Böylece üçüncü kutuyu kodlayan dizilimleri de bulmuş oldum: YTYY, YTYT, TYTT ve TYTY.
Kalan dört dizilim de dördüncü kutuyu kodlamak için kullanılabilir: TYYT, TYYY, YTTT, YTTY.
YYYY (0) -> TYYY (8) YYYT (1) -> TYYT (9) YYTY (2) -> YTTY (6) YYTT (3) -> YTTT (7) YTYY (4) -> YTTY (6) YTYT (5) -> YTTT (7) YTTY (6) -> YTTT (7) YTTT (7) -> YTTY (6) TYYY (8) -> TYYT (9) TYYT (9) -> TYYY (8) TYTY (10) -> TYYY (8) TYTT (11) -> TYYT (9) TTYY (12) -> TYYY (8) TTYT (13) -> TYYT (9) TTTY (14) -> YTTY (6) TTTT (15) -> YTTT (7)
Böylece problem için bir çözüm bulmuş oldum.
Algoritma olarak her bir kutuyu kodlamak için yaptığım adımlar şöyle oldu: Daha önce seçilmemiş bir dizilim aldım. Sonra bu dizilime bir değişiklik uzakta başka bir dizilim aldım ve sekiz değişik dizilimin bu iki dizilime bir değişiklik uzakta olduğunu gösterdim. Kalan diğer iki dizilimi de bu seçtiğim iki dizilimin tersi olarak seçtim ve bu dizilimlerin de diğer sekiz dizilime birer değişiklik uzaklıkta olduğunu gösterdim.
Şimdi aklıma takılan bazı sorulara bakayım:
- Her adımda seçtiğim ilk iki dizilim her zaman sekiz değişik dizilimden bir değişiklik uzakta mı? Birbirine bir değişiklik mesafede iki dizilimin bir basamakları farkllı ve diğer üç basamakları aynı olmak zorundadır. Seçtiğim iki dizilimin arasındaki mesafe bir değişiklik olduğundan ikisi de bu iki dizilime bir değişiklik mesafede olan dizilimler arasında olacak ve birbirlerinden farklıdırlar. Kalan üçer basamak için de ya elimdeki sayılara (ikisine de) o basamak değeri kadar ek yapacağım (eğer basamak değeri sıfır ise) ya da sayının değerinden o basamak değeri kadar çıkaracağım. İki durumda da oluşan sayılar elimdeki sayılardan ve birbirlerinden farklı olacaklar. Basamakların değerleri de 1, 2, 4 ya da 8 olduğundan değişik basamakların değerlerini (sadece bir basamağın) ekleyerek ya da çıkararak eşit sayılar elde edemeyiz.
- Dizilimlerin tersini aldığımda (yani yazı yerine tura, tura yerine yazı koyunca) önceki sekiz dizilimle bir çakışma olabilir mi? Dizilimlerin onluk düzendeki değerlerine bakarsak bir dizilimin değeriyle o dizilimin tersinin değerini topladığımızda her zaman 15 sayısına ulaşıyoruz. Çakışma olabilmesi için sekizlik grupta toplamları 15 olan iki dizilimin olması gerekir. Şöyle bir mantık yürüteyim. Birbirine mesafesi bir olan iki dizilimden herhangi birine mesafesi bir değişim olan iki rastgele dizilim arasındaki mesafe en fazla üç olabilir olabilir. Dizilimlerin birine A diyelim ve bu seçtiğim ilk dizilime bir değişim mesafede olsun. Diğer B dizilimi de ikinci dizilime bir değişim mesafede olsun. O zaman A diziliminden B dizilimine önce bir seçtiğim iki dizilim üzerinden en fazla üç dizilimle gidebilirim. Şimdi toplamları 15 değerini veren dizilimlere bakayım.
YYYY (0) -> TTTT (15) : aradaki mesafe 4 YYYT (1) -> TTTY (14) : aradaki mesafe 4 YYTY (2) -> TTYT (13) : aradaki mesafe 4 YYTT (3) -> TTYY (12) : aradaki mesafe 4 YTYY (4) -> TYTT (11) : aradaki mesafe 4 YTYT (5) -> TYTY (10) : aradaki mesafe 4 YTTY (6) -> TYYT (9) : aradaki mesafe 4 YTTT (7) -> TYYY (8) : aradaki mesafe 4
Tablodan da görüldüğü gibi toplamın 15 olabilmesi için seçtiğim iki dizilimin ürettiği sekiz dizilimdeki iki dizilim arasındaki mesafenin dört olması lazım ama bu mesafe en fazla üç olabiliyor. Demek ki toplamı 15 eden iki dizilim bu sekiz dizilim arasında yok. O zaman tersleri ile aralarında bir çakışma da olamaz. Yani kullandığım yöntem gerçekten de işe yarıyor gibi gözüküyor.
Not: Literatürde bu dizilimler arasındaki mesafeye (birinden diğerine geçişte gereken değişiklik sayısına) Hamming mesafesi deniyor.