Çözüm Özeti


Hatasız sekans şudur (4 simetrik varyanttan kanonik olanı):
t=1: A + D → B odasına | t=2: Boş dönüş | t=3: B + C → B odasına | t=4: Boş dönüş (mekik protokolünün kapanışı) + gemi kalkışı
Şimdi bunu matematiksel olarak türetelim.

1. Yasaklı Durumların Çıkarılması


Üç kural, herhangi bir ortam (A odası, B odası veya robot kol) için iki yasak kümesi üretir:
Yasak-1 (Kural 1): {A, B} birlikte ∧ C yok → patlama. Bu, kolun A ve B'yi birlikte taşıyamayacağı anlamına gelir, çünkü kol kapasitesi 2 olduğundan yanlarına C alınamaz.
Yasak-2 (Kural 2): D'nin bulunduğu ortamda toplam çeşit ≥ 3 (yani D + en az 2 farklı madde) → fitil yanar, 4 adım sonra çöküş. Güvenli üst sınır: D'nin yanında en fazla 1 madde.
Kritik gözlem (t=0): Kasada 4 çeşit madde var, yani Kural 2 fitili daha siz başlamadan yanmış durumda. Geri sayım t=0'da başladı, çöküş sınırı t=4'ün sonu. Dolayısıyla ilk hamle, D'nin bulunduğu ortamı 3 çeşidin altına düşürmek zorunda.

2. Neden Tam 4 Adım? (Alt ve Üst Sınır Kanıtı)


Yük denklemi: Robot A'da başlar, konumu her adımda değişir (A→B→A→B). Taşıma seferleri yalnızca tek sayılı adımlarda (t=1, t=3) yapılabilir. Net taşınan madde: x₁ − y₁ + x₂ − y₂ = 4 olmalı (x = gidişte taşınan, y = dönüşte geri getirilen, her biri ≤ 2). Tek çözüm: x₁ = x₂ = 2 ve y₁ = y₂ = 0. Yani her gidiş tam dolu, her dönüş zorunlu olarak boş olmalı. Dönüşte madde geri getirmek matematiksel olarak elenir.
Alt sınır: 4 madde / 2 kapasite = en az 2 gidiş + aradaki zorunlu dönüş + mekik protokolü gereği kolun yuvasına son dönüşü = 4 adım. Daha kısa olamaz.
Üst sınır: t=0'da yanan fitil + geminin t=4'te kalkması nedeniyle daha uzun da olamaz.
Yük dağılımı teoremi: A ve B aynı sefere binemez (Yasak-1). C ve D ilk sefere birlikte binemez, çünkü geride {A, B} yalnız kalır → anında patlama. Tek madde taşınamaz (aşağıdaki tuzak analizine bakın). Sonuç: her sefer mutlaka {A veya B} + {C veya D} kombinasyonu olmalıdır.

3. Adım Adım Durum Tablosu


AdımHareketA OdasıRobot KolB OdasıKural Kontrolüt=0—A, B, C, Dboş (A'da)—K1 ✓ (C tampon) · K2 fitili yanık!t=1A→B: A+D taşınırB, CA, D (transit) → bırakırA, DA odası: 2 çeşit, D yok ✓ · Kolda A-B ayrık ✓ · B odası: D yanında 1 madde ✓ · Fitil söner (geçen: 1 adım)t=2B→A: boş dönüşB, CboşA, DTüm ortamlar değişmedi ✓t=3A→B: B+C taşınır— (boş)B, C (transit) → bırakırA, B, C, DVarışta C, B ile eşzamanlı bırakılır → A-B hiçbir saniye C'siz buluşmaz ✓ · K2: 4 çeşit → fitil yeniden yanar (patlama ancak t=7'de olurdu)t=4B→A: boş dönüş + gemi kalkışı— (kol yuvada)boşA, B, C, D → gemiye yüklenirFitilde geçen süre: 1 adım < 4 ✓Fitil muhasebesi (en kötü senaryo, sıfırlanmayan sayaç varsayımıyla bile): D'nin kararsız ortamda geçirdiği toplam süre = (t=0→t=1) 1 adım + (t=3→t=4) 1 adım = 2 adım < 4. Sistem her iki yorumda da güvenli.

4. Gizli Tuzak Analizi — Diğer Sekanslar Neden Başarısız?

  • {C, D} ilk taşınırsa: Geride {A, B} kalır → C'siz temas, anında patlama.
  • Yalnız C taşınırsa: Geride {A, B, D} kalır → yine patlama.
  • {A, B} birlikte taşınırsa: Kolda ve varışta C yok → patlama.
  • Tek tek taşıma (örn. yalnız A): Geride {B, C, D} = D'li 3 çeşit kalır, fitil sönmez; ayrıca kapasite israfı yüzünden 4. madde t=5'e sarkar → gemi kaçar, t=0 fitili t=4'te dolar → deadlock.
  • Yalnız D ilk (en sinsi tuzak): Geride {A, B, C} kalır ve bu güvenli görünür (D yok, Kural 2 tetiklenmez). Ama t=3'te taşınan ikili B odasında D ile buluşunca fitil erkenden yanar ve 4. madde A odasında mahsur kalır (t=4 dönüş adımıdır, taşıma yapılamaz) → görev tamamlanamaz.
  • Dönüşte madde geri getirmek: Yük denklemini bozar, net taşıma 4'ün altına düşer → 4 adımda imkânsız.

5. Çözüm Uzayının Tamamı


Yük dağılımı teoremi gereği tam olarak 4 eşdeğer çözüm vardır: (A+D)→(B+C), (A+C)→(B+D), (B+D)→(A+C), (B+C)→(A+D). Hepsinde ortak yapı aynıdır: A ile B farklı seferlere ayrılır, C bir tanesine "refakatçi", D diğerine "yalnız yolcu" olarak eşlik eder ve dönüşler boştur. Kanonik çözümün avantajı anlatısaldır: zaten kararsızlaşmaya başlamış olan D ilk seferde tehlike bölgesinden çıkarılır, katalizör C ise son ana kadar geride kalan maddeye bekçilik eder.