KEMUSTAHILAN PUZZLE MN 1

ABSTRAKPuzzle mn 1 merupakan generalisasi dari Puzzle 15: Puzzle ini terdiri dari m ngrid yang dilabelkan dengan 1; 2; : : : ;mn 1 dan sebuah grid tanpa label (disebutblank). Dalam permainan ini, diberikan sembarang posisi awal (pelabelan dari se-mua grid) dan sebuah posisi akhir, maka langkah demi langkah dilakukan agar posisiakhir dapat dicapai dari posisi awal. Langkah yang dibolehkan hanyalah menggesersembarang grid yang berdekatan dengan blank sehingga labelnya bertukar. Tulisanini ingin membahas bila mana posisi akhir tidak dapat dicapai dari posisi awal. Ada(mn)! kemungkinan untuk posisi awal. Akan dibuktikan bahwa adaminimal12(mn)!yang membuat puzzle ini mustahil untuk diselesaikan. Sementara untuk setengahposisi awal lainnya tidak dibahas apakah posisi-posisi awal itu dapat mencapai keposisi akhir.Kata Kunci: Puzzle mn 1, grup permutasi, posisi mustahilABSTRACTThe mn 1 Puzzle is the generalization of 15 Puzzle that consist of m n grids.Each gridwas labeled by number 1; 2; : : : ;mn 1 and therewas an empty grid calledblank. In this game, given any initial position and a final position, we apply a finitenumber of moves to the initial position so we can get a final position. A move is anaction of sliding any grid adjacent to the blank so that the label will be switched. Inthis paper, we will talk about the situation when the final position cannot be achievefrom the initial position. There are mn! possibilities of the initial position, we willprove that at least half of them cannot be solved. But we are not going to discussabout either the other half of possibilities can be solved or not.Keywords: mn 1 Puzzle, permutation group, impossible positio