1880'de Amerikalı bulmaca ustası Sam Loyd, belirli bir 15 bulmacayı çözebilene 1000 dolar ödül duyurdu: standart 1'den 15'e dizilim, ama 14 ile 15'in yeri değiştirilmiş. Bulmaca çılgınlığı zaten Amerika'yı ve Avrupa'yı sarmıştı; Loyd'un gösterisi ateşe benzin döktü. Binlerce kişi denedi. Kimse kazanamadı.
Kimsenin kazanamamasının bir nedeni vardı. Loyd'un tahtası kanıtlanabilir biçimde çözülemezdi ve kanıt tek sayfaya sığacak kadar basitti. Bu makale, işte o sayfa.
İddia
On beş taşı ve bir boşluğu 4×4 tahtaya dizmenin 16!/2 ≈ 10.461.394.944.000 yolunun tam olarak yarısı standart hedefe çözülebilir. Diğer yarısı çözülemez. Loyd'un "14 ile 15 değişik" dizilimi çözülemez yarıdadır.
Bu genelleşir. Her N×N kayan bulmacada dizilimlerin yarısı çözülemez. 3×3 8 bulmacada toplam 362.880 dizilimin 9!/2 = 181.440'ı çözülebilir; 24 bulmaca, 35 bulmaca ve devamı aynı kuralı izler.
İnversiyonlar
Kanıt için tek bir tanım gerekiyor. Taşları okuma sırasıyla okuyun — 1. satırda soldan sağa, sonra 2. satır, 3. satır, 4. satır — ve boşluğu yok sayın. Elinizde on beş sayılık bir dizi olur.
Bir inversiyon, dizide a'nın b'den önce geldiği ama a > b olduğu bir (a, b) çiftidir. Tüm dizideki bu tür çiftleri sayın. Bu sayı, tahtanın inversiyon sayısıdır.
Örnek: hedef durum 1,2,3,…,15 sıfır inversiyona sahiptir. Loyd'un "14 ile 15 değişik" dizilimi 1,2,3,…,13,15,14 dizisini verir ve tam olarak bir inversiyonu vardır (15,14 çifti).
Anahtar önerme: bir kaydırma pariteyi kontrollü biçimde değiştirir
Kurallı bir hamle yaptığınızda inversiyon sayısına ne olur?
-
Yatay kaydırmalar (bir taş bir hücre sola veya sağa gider): kaydırılan taş, okuma sırasındaki yerini bir kaydırır. Dizideki diğer tüm taşlarla göreli sırası aynen korunur — çünkü yatay hareket, taşın hangi satırda olduğunu da, okuma sırasında ondan önce ve sonra hangi taşların geldiğini de değiştirmez. İnversiyon sayısı değişmez.
-
Dikey kaydırmalar (bir taş bir hücre yukarı veya aşağı gider): kaydırılan taş, okuma sırasında üç taşın üzerinden atlar — çıktığı veya girdiği satırdaki üç taşın. Bu üç taşın her biri ya "sonra"dan "önce"ye geçer ya da tersi; yani her biri inversiyon sayısına +1 veya -1 katkı yapar. Üç adet ±1'in toplamı her zaman tektir. Dolayısıyla inversiyon sayısı tek bir sayı kadar değişir.
Özetle: yatay kaydırma inversiyon sayısının paritesini (tek/çift) korur. Dikey kaydırma ise değiştirir.
Dikey kaydırmalarda boşluğun satırı da değişir
Boşluğun satırını takip edin (satırları yukarıdan sayarak). Yatay kaydırma boşluğu aynı satırda bırakır. Dikey kaydırma onu bir satır yukarı veya aşağı taşır, yani boşluğun satırının paritesi değişir (çift satır ↔ tek satır).
Elimizde birlikte değişen iki şey var:
- İnversiyon sayısının paritesi değişir ⇔ dikey kaydırma.
- Boşluk satırının paritesi değişir ⇔ dikey kaydırma.
Dolayısıyla toplamları her kurallı kaydırmada değişmez. Korunan bir nicelik bulduk.
Parite teoremi
Değişmezi tanımlayalım:
P = (inversiyon sayısı) + (boşluğun aşağıdan sayılan, 1'den başlayan satır numarası)
Korunan nicelik işte budur. Her kurallı kaydırmada P çift bir sayı kadar değişir, dolayısıyla paritesi (tek/çift) asla değişmez.
Hedef durumda sıfır inversiyon vardır ve boşluk aşağıdan 1. satırdadır — yani P = 1 (tek). P'si çift olan hiçbir tahtaya hedeften ulaşılamaz; aynı şekilde böyle bir tahtadan hedefe de ulaşılamaz.
Bu, 15 bulmaca için temiz bir çözülebilirlik testi verir:
- Taşları okuma sırasıyla okuyun, boşluğu yok sayın.
- İnversiyonları sayın.
- Boşluğun satırını aşağıdan sayın (1, 2, 3 veya 4).
- Toplayın. Toplam tekse tahta çözülebilir. Çiftse çözülemez.
Loyd'un "14 ile 15 değişik" diziliminde 1 inversiyon vardır ve boşluk aşağıdan 1. satırdadır — toplam 2, çift, çözülemez.
Diğer boyutlarda durum
N×N parite kuralı, N'nin tek mi çift mi olduğuna bağlıdır. Genel ifade:
- N tek (3×3, 5×5, …): bir tahta ancak ve ancak inversiyon sayısı çiftse çözülebilir. Boşluğun satırı önemli değildir, çünkü simetri nedeniyle boşluğun satır paritesi inversiyon sayısının paritesince belirlenir.
- N çift (4×4, 6×6, …): bir tahta ancak ve ancak (inversiyon sayısı) + (boşluğun aşağıdan satırı) tekse çözülebilir.
3×3 için test yalnızca "inversiyon sayısı çift mi?" sorusudur. 4×4 sürümünden daha basittir ve bir dakikada ezberlenir.
Hoş bir sonuç
Dizilimlerin tam yarısı çözülebilir olduğundan, rastgele karıştırıp pariteyi kontrol etmek, rastgele karıştırıp çözmeye çalışmaktan daha hızlıdır. Çözülebilir başlangıç konumu garanti etmesi gereken uygulamalar iki yoldan birini seçer:
- Parite testiyle ön eleme yapıp başarısızlıkta yeniden karıştırmak.
- Hedeften geriye doğru yürüyerek üretmek — rastgele geçerli kaydırmalar uygulayarak. Bu, çözülebilirliği yapısal olarak garanti eder ve çoğu uygulamanın (bizimki dahil) yaptığı budur.
Bir gün bir kayan bulmaca oynar ve ne yaparsanız yapın imkânsız bulursanız, uygulama onu kötü üretmiştir — sizin suçunuz değil, evrenden gelen bir bulmaca da değil.
Sam Loyd dipnotu
Loyd'un 1000 dolarlık ödülü, bulmaca tarihinin en iyi belgelenmiş şakalarından biridir. Çözülemezliği — bağımsız olarak — kanıtlayan matematikçi, kime inandığınıza bağlı olarak ya William Johnson ile William Story'dir (1879, American Journal of Mathematics) ya da Loyd'un kendisi. Loyd, icat etmediği birçok şeyi sahiplenmesiyle ünlü, kendi reklamını iyi yapan bir figürdü; 15 bulmacanın kendisi de 1874'te Noyes Chapman tarafından icat edilmişti — Loyd'un ödül gösterisinden altı yıl önce.
Loyd'un gerçek katkısı ödül, tanıtım ve çözülemez varyanttı — duyurduğu katkı olmasa da, yararlı bir katkı.