Nehir geçişi bulmacası

Köpek, koyun ve lahana

Nehir geçişi bulmacası, nesneleri bir nehir kıyısından diğerine, genellikle en az sayıda yolculukla taşımayı amaçlayan bir bulmaca türüdür.[1] Bulmacanın zorluğu, hangi veya kaç öğenin aynı anda taşınabileceğine veya hangi veya kaç öğenin güvenli bir şekilde bir arada bırakılabileceğine ilişkin kısıtlamalardan kaynaklanır. Kurgu, örneğin nehrin bir köprü ile değiştirilmesi gibi görsel açıdan da değişim gösterebilir.[1] Bilinen en eski nehir geçişi problemleri, geleneksel olarak Alcuin tarafından yazıldığı söylenen Propositiones ad Acuendos Juvenes (İngilizce: Problems to sharpen the young, Türkçe: Gençleri keskinleştirmek için problemler) adlı el yazmasında yer alır. Bu el yazmasının en eski kopyaları 9. yüzyıla aittir; tilki, kaz ve fasulye torbası bulmacası ve kıskanç kocalar problemi de dahil olmak üzere üç farklı nehir geçme problemi içerir.[2]

Tilki, kaz ve fasulye torbası bulmacası
Köprü ve meşale problemi
Bazı bulmacaların çözümleri zaman çizelgesi olarak çizelgelenmiştir.

İyi bilinen nehir geçişi bulmacaları şunlardır:

  • Tilki, kaz ve fasulye torbası bulmacası, bir çiftçinin tilki, kaz ve fasulye torbasını, çiftçiye ilaveten yalnızca bir öğe alabilen bir tekne kullanarak, tilkinin kaz ile yalnız bırakılamayacağı ve kazın fasulye ile yalnız bırakılamayacağı kısıtlamalarına tabi olarak bir nehrin bir tarafından diğerine taşıması gereken bulmacadır. Tilki, tavuk ve bir torba tahıl ya da kurt, keçi ve lahana gibi eşdeğer bulmacalar da ifade edilmiştir.
  • Kıskanç kocalar problemi, üç evli çiftin bir nehri en fazla iki kişi alabilen bir kayık kullanarak, kocası olmadığı sürece hiçbir kadının başka bir erkeğin yanında bulunamayacağı kısıtlamasına tabi olarak geçmesi gerektiği problemdir. Bu, üç misyoner ve üç yamyamın nehri geçmesi gereken, hem misyonerlerin hem de yamyamların her iki kıyıda da durduğu herhangi bir zamanda, o kıyıdaki yamyamların misyonerlerden sayıca fazla olamayacağı kısıtlamasıyla misyonerler ve yamyamlar problemine benzer.
  • Köprü ve meşale problemi.
  • Propositio de viro et muliere ponderantibus plaustrum; Propositiones ad Acuendos Juvenes'de de yer alan bu problemde, eşit ağırlıktaki bir erkek ve bir kadın, her biri kendi ağırlığının yarısı kadar olan iki çocukla birlikte, yalnızca bir yetişkinin ağırlığını taşıyabilen bir kayık kullanarak bir nehri geçmek isterler.[3]

Bu problemler çizge teorisi yöntemleri,[4][5] dinamik programlama[6] veya tamsayılı programlama[3] kullanılarak analiz edilebilir.

Ayrıca bakınız

Kaynakça

  1. ^ a b Peterson, Ivars (2003), "Tricky crossings", Science News, 164 (24), 20 Ocak 2008 tarihinde kaynağından arşivlendi, erişim tarihi: 7 Şubat 2008 .
  2. ^ p. 74, Pressman, Ian; Singmaster, David (1989), ""The Jealous Husbands" and "The Missionaries and Cannibals"", The Mathematical Gazette, The Mathematical Association, 73 (464), ss. 73-81, doi:10.2307/3619658, JSTOR 3619658 .
  3. ^ a b Borndörfer, Ralf; Grötschel, Martin; Löbel, Andreas (1995), Alcuin's Transportation Problems and Integer Programming, Preprint SC-95-27, Konrad-Zuse-Zentrum für Informationstechnik Berlin, 19 Temmuz 2011 tarihinde kaynağından arşivlendi .
  4. ^ Schwartz, Benjamin L. (1961), "An analytic method for the "difficult crossing" puzzles", Mathematics Magazine, 34 (4), ss. 187-193, doi:10.2307/2687980, JSTOR 2687980 .
  5. ^ Csorba, Péter; Hurkens, Cor A. J.; Woeginger, Gerhard J. (2008), "The Alcuin number of a graph", Algorithms: ESA 2008, Lecture Notes in Computer Science, 5193, Springer-Verlag, ss. 320-331, doi:10.1007/978-3-540-87744-8_27 .
  6. ^ Bellman, Richard (1962), "Dynamic programming and "difficult crossing" puzzles", Mathematics Magazine, Mathematical Association of America, 35 (1), ss. 27-29, doi:10.2307/2689096, JSTOR 2689096 .

Dış bağlantılar