Teka-teki menyeberangi sungai: Perbedaan antara revisi
←Membuat halaman berisi 'thumb|Masalah serigala, kambing dan kubis '''Teka-teki melintasi sungai''' adalah sebuah jenis teka-teki dimana seseorang membawa baran...' |
(Tidak ada perbedaan)
|
Revisi per 12 Maret 2019 03.32
Teka-teki melintasi sungai adalah sebuah jenis teka-teki dimana seseorang membawa barang-barang dari satu tepi sungai ke tepi lainnya, biasanya dengan pergerakan satu arah. Kesulitan teka-teka tersebut berkembang dari pembatasan atau cara beberapa barang tersebut dapat dibawa pada saat yang sama, atau bagaimana barang tersebut dapat dibawa dengan selamat.[1] Setting tersebut memiliki banyak keragaman, contohnya, dengan menggantikan sungai dengan jembatan.[1] Masalah melintasi sungai terawal muncul dalam manuskrip Propositiones ad Acuendos Juvenes (bahasa Inggris: Masalah-masalah untuk mempertajam kaum muda), biasanya dikatakan ditulis oleh Alcuin. Salinan terawal dari manuskrip tersebut berasal dari abad ke-9; karya tersebut berisi tiga masalah melintasi sungai, termasuk teka-teki rubah, angsa dan sekantung buncis dan masalah suami-suami pencemburu.[2]
Teka-teki melintasi sungai yang terkenal meliputi:
- Teka-teki rubah, angsa dan sekantung buncis, dimana seornag petani harus membawa rubah, angsa dan sekantung buncis dari satu sisi sungai ke sisi lainnya memakai sebuah perahu yang hanya dapat menampung satu barang selain petani tersebut. Permasalahannya adalah rubah tak dapat ditinggal sendiri dengan angsa, dan angsa tak dapat ditinggal sendiri dengan sekantung buncis. Teka-teki serupa juga melibatkan rubah, ayam dan sekantung bahan pokok, atau rubah, kambing dan kubis, dlsb
- Masalah suami-suami pencemburu, dimana tiga pasangan suami-istri harus melintasi sebuah sungai memakai sebuah perahu yang hanya dapat menampung dua orang. Permasalahannya adalah tidak ada wanita yang dapat bersama dengan pria lain selain suaminya juga ada bersamanya. Ini mirip dengan masalah misionaris dan kanibal, dimana tiga misionaris dan tiga kanibal harus melintasi sungai, dengan permasalahan bahwa saat para misionaris dan kanibal berada di suatu tepi, para kanibal di tepi tersebut tak boleh mengalahkan jumlah para misionaris.
- Masalah jembatan dan penerang.
- Propositio de viro et muliere ponderantibus plaustrum. Dalam masalah ini, yang juga muncul dalam Propositiones ad Acuendos Juvenes, seorang pria dan seorang wanita memiliki berat yang sama,. bersama dengan dua nak, masing-masing memiliki berat setengah dari mereka, berniat untuk melintasi sungai memakai perahu yang hanya dapat menampung berat satu orang dewasa.[3]
Masalah-masalah tersebut dianalisis memakai metode grafis-teoretikal,[4][5] dengan pemprograman dinamis,[6] atau dengan pemprograman integer.[3]
Referensi
- ^ a b Peterson, Ivars (2003), "Tricky crossings", Science News, 164 (24), diakses tanggal 2008-02-07.
- ^ p. 74, Pressman, Ian; Singmaster, David (1989), ""The Jealous Husbands" and "The Missionaries and Cannibals"", The Mathematical Gazette, The Mathematical Association, 73 (464): 73–81, doi:10.2307/3619658, JSTOR 3619658.
- ^ 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, diarsipkan dari versi asli tanggal 2011-07-19.
- ^ Schwartz, Benjamin L. (1961), "An analytic method for the "difficult crossing" puzzles", Mathematics Magazine, 34 (4): 187–193, doi:10.2307/2687980, JSTOR 2687980.
- ^ 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, hlm. 320–331, doi:10.1007/978-3-540-87744-8_27.
- ^ Bellman, Richard (1962), "Dynamic programming and "difficult crossing" puzzles", Mathematics Magazine, Mathematical Association of America, 35 (1): 27–29, doi:10.2307/2689096, JSTOR 2689096.