Vol. 11, No. 1,  39-44,  Juli  2014

## KONSTRUKSI POSISI- P DARI PERMAINAN WYTHOFF
Muhlis Maulana Ibrahim 1 , Loeky Haryanto 2 , Amir Kamal Amir 3
maulana.ibrahim.muhlis@gmail.com

## ABSTRAK
P ermainan Wythoff merupakan permainan yang dimainkan oleh dua orang pemain yang secara bergantian memilih sebuah langkah sahih untuk merubah posisi ( x , y )  Z ≥0 × Z ≥0 ke posisi ( x’ , y’ ). Terdapat barisan {( a n , b n )} ≥0 yang setiap pasangan ( a n , b n ) dari barisan ini disebut posisi- P . Salah satu posisi- P adalah (0, 0) dan  pemain  yang  mendapat  posisi  (0,  0)  dinyatakan  kalah.  Setiap  posisi- P ( a n ,  b n )  memenuhi  sifat:  tidak ada  pilihan  langkah  untuk  merubah  posisi- P ( a n ,  b n )  ke  posisi- P yang  lain.  Sebaliknya  dengan  memilih langkah yang tepat, setiap posisi ( x , y ) yang bukan posisi- P bisa dibawa ke posisi- P . Sesuai  dengan  cara  konstruksinya,  ada  tiga  bentuk  posisi- P dari  permainan  Wythoff:  sebagai  dua  barisan Beatty yang saling komplemen yang diperoleh dari rasio mulia, sebagai koordinat titik-titik yang diperoleh dari fungsi Sprague-Grundy dan operator Mex dan sebagai posisi kemunculan ke- n dari symbol a dan b di dalam kata Fibonacci atas alfabet { a , b }.
Kata  Kunci :  Posisi- P permainan  Wythoff,  rasio  mulia,  barisan  Beatty,  operator Mex ,  fungsi Sprague-Grundy, kata Fibonacci.

## ABSTRACT
Wythoff game is played by two players who alternatingly choose a valid step to change the current position ( x , y )  Z ≥0 × Z ≥0 of the game. There is a sequence {( a n , b n )} ≥0 in  which every pair ( a n , b n ) is called a P - position. One of the P -position is (0, 0) and any player who gets the position (0, 0) lost the game. Every P- position ( a n , b n ) satisfies the following properties: there is no valid step that changes a P -position( a n , b n ) to another P -position and conversely from any non P -position, there is a smart step that changes the position to a P –position.
In  accordance  with  the  construction,  there  are  three  forms  of P -positions:  as  complementary  Beatty sequences generated using golden ratio, as coordinate positions obtained from the Sprague-Grundy function equipped  with Mex operator  or  as  positions  of  the n- th  occurrence  of a and b in  Fibonacci  word  over alphabet { a , b }.
Key  Words : P- positions  of    Wythoff  game,  golden  ratio,  Beatty  sequences, Mex operator, Sprague-Grundy function, Fibonacci word.

## 1. Pendahuluan
Teori  permainan  kombinatorik  ( combinatorial  games )  adalah  teori  yang  membahas permainan  menang-kalah  atau  sukses-gagal  yang  dimainkan  oleh  dua  pemain  dengan  berbagai aturan.  Setiap  pemain  secara  bergantian  melakukan  langkah-langkah  untuk  merubah  posisi permainan sampai salah satu pemain kalah, yaitu tak bisa melanjutkan dengan satu langkah sah (langkah  yang  sesuai  aturan  permainan).  Posisi  menang  atau  kalah  dapat  dirumuskan  secara
1 Program S1 Jurusan Matematika FMIPA Universitas Hasanuddin
2 Jurusan Matematika FMIPA Universitas Hasanuddin
3 Jurusan Matematika FMIPA Universitas Hasanuddin
sistematis  dengan  berbagai  manipulasi  kombinatorik  berdasarkan  masukan  data  yang  diberikan atau dipilih pemain-pemainnya. 4
Salah  satu  ciri  permainan  kombinatorik  adalah  terdapat  himpunan  posisi-posisi  yang masing-masing disebut posisi -P (biasa juga disebut dengan posisi aman) sedemikian hingga jika posisi  permainan  berada  pada  posisi -P ,  maka  pemain  yang  mengerjakan  langkah  sebelumnya (previous move) bisa memaksakan kemenangan. Posisi yang bukan posisi -P disebut posisi -N (dari kata Next ).
Salah  satu  di  antara  permainan  kombinatorik  adalah  permainan  Wythoff  ( Wythoff  game ), permainan  yang  solusinya  pertama  kali  diberikan  oleh  Willem  Abraham  Wythoff  pada  tahun 1907.

## 2. Aturan Permainan Wythoff
Permainan Wythoff menggunakan dua tumpukan atau wadah, dapat berupa dua keranjang berisi bola atau dua tongkat tegak yang dikalungi gelang-gelang logam atau bentuk-bentuk yang lain di mana setiap pemain pada gilirannya mengikuti aturan sebagai berikut [1]:
 Terdapat dua pemain yang bermain secara bergantian;
 Setiap pemain bisa mengambil satu token atau lebih;
 Setiap pemain bisa mengambil token dari satu tumpukan dalam jumlah sembarang;
 Setiap  pemain  bisa  mengambil  token  dari  kedua  tumpukan,  asalkan  banyaknya  token  yang diambil dari masing-masing tumpukan adalah sama;
 Pemain yang mengambil token terakhir adalah pemenangnya.
Terdapat  bentuk  permainan  yang  diciptakan  oleh  Rufus  P.  Isaacs  yang  ekuivalen  dengan permainan  Wythoff.  Isaacs  menggambarkan  sebuah  permainan  yang  mirip  dengan  gerakan  sah dari  Ratu  ( Queen )  permainan  catur,  yaitu  hanya  bergerak  secara  vertikal  ke  selatan,  secara horizontal  ke  barat,  atau  secara  diagonal  ke  arah  barat  daya  pada  papan  catur.  Di  mana  Ratu ditempatkan pada sembarang posisi ( s , t )  (0, 0), bisa dikolom sebelah kanan ataudi barisbagian ataspapan  catur  atau  pada  diagonal.  Dengan  batasan  aturan  gerak  Ratu  seperti  di  atas,  pemain yangdapat menempatkan Ratu kesudut paling kiri paling bawahadalah pemenangnya.

## 3. Barisan Beatty
Misalkan  lambang  x  menyatakan  bilangan  bulat  terbesar  yang  lebih  kecil  atau  sama dengan x (pembulatan  ke  bawah  terhadap x ).  Barisan  Beatty  untuk  bilangan  tak  rasional a  > 1 adalah barisan       1 n na [ 3 ], yaitu barisan
 a  ,  2a  ,  3a  , ….

## Teorema: (Beatty)
Jika a dan b adalah bilangan tak rasional yang memenuhi 1 1 1 a b   , maka kedua barisan
      1 n na dan   1 n nb       saling  lepas  dan  hasil  gabungannya  adalah  himpunan  semua bilangan asli .
Kedua barisan tersebut dalam teorema di atas disebut dua barisan Beatty yang saling komplemen.

## 4. Operator Mex dan Fungsi Sprague-Grundy
Misalkan O =  {0,  1,  2,  …}  adalah  himpunan  bilangan-bilangan  cacah.  Operator Mex ( Minimum excluded ) didefinisikan sebagai berikut [ 2 ].
1,2,3 Jurusan Matematika FMIPA Universitas Hasanuddin Makassar , Jl. Perintis Kemerdekaan Km.10 Makassar

## Muhlis Maulana Ibrahim, Loeky Haryanto, Amir Kamal Amir
Definisi
Untuk setiap himpunan A  O dari bilangan-bilangan cacah didefinisikan Mex { A } = min ( O - A ) Definisi Mex bisa dikenakan pada barisan { a n } dengan mengadopsi A= { a 1 , a 2 , a 3, ...} dalam definisi di atas.
Fungsi Sprague-Grundy Sp ( s, t ) didefinisikan secara rekursif dengan nilai awal Sp (0,0) = 0 dan tiga himpunan awal G 1 (0,0) = G 2 (0,0) = G 3 (0,0) = {0}. Jika s <0 atau t<0, didefinisikan G 1 ( s, t ) = G 2 ( s, t ) = G 3 ( s, t ) =  . Selanjutnya,untuk setiap pasang bilangan bulat ( s , t ) ≠ (0, 0) berlaku Sp ( s , t ) = Mex ({ G 1 ( s  1, t )  G 2 ( s  1, t  1)  G 3 ( s , t  1)} di mana
G 1 ( s , t ) = 0 x s    { Sp ( x, t )}.
G 2 ( s , t ) = 0 min( , ) s x t y s t       { Sp ( x, y )}. G 3 ( s , t ) = 0 y t    { Sp ( s, y )}. Dengan kata lain,
G 1 ( s , t ) = { Sp (0 , t ), Sp (1 , t ), …, Sp ( s  1 , t )}, G 2 ( s , t ) = { Sp ( s  min{ s, t }, t  min{ s, t }), …, Sp ( s  2 , t  2), Sp ( s  1 , t  1)} G 3 ( s , t ) = { Sp ( s, 0), Sp ( s, 1), …, Sp ( s, t  1)} Dari Sp (0, 0) = 0, diturunkan Sp (0, 1) = 1 = Sp (1, 0), Sp (1, 1) = 2, dst.

## 5. Konstruksi Posisi- P Permainan Wythoff
Dalam konteks permainan kombinatorik, fokus utamanya adalah mencari nilai pasangan ( a n , b n ) n  0 yang  merupakan  barisan  posisi- P dari  permainan  Wythoff.  Posisi- P permainan  Wythoff bisa  diperoleh  dari  rasio  mulia φ ,dengan  fungsi  Sprague-Grundy  yang  dilengkapi  operator  Mex atau dari kata Fibonacci, seperti uraian berikut.

## 5.1 Konstruksi Posisi- P dengan Rasio Mulia
Barisan Fibonacci yang dilambangkan dengan { F n }di awali oleh 2 suku F 0 = 0, F 1 = 1 dan untuk n = 2, 3, 4, ... , nilai F n diperoleh dari relasi rekurensi F n = F n  1 + F n  2 (1) Persamaan (1) disebut relasi rekurensi linear homogin order 2.
Perbandingan (rasio) bilangan Fibonacciyang ke-( n+ 1) dengan bilangan Fibonacci ke- n untuk n≥ 1 menghasilkan barisan
1/1, 2/1, 3/2, 5/3, 8/5, 13/8, … dst yang konvergen ke bilangan
1 5 2   
atau  dalam  notasi  desimal φ =  1.618033988749894…,  yang  disebut  rasio  mulia  ( golden ratio ). Pembuktiannya dapat dilihat pada berbagai buku teks dan situs internet, misalnya pada [ 5 ].

## Muhlis Maulana Ibrahim, Loeky Haryanto, Amir Kamal Amir
Posisi -P pertamadidefinisikan sebagai ( a 0 , b 0 ) = (0, 0), yang disebut juga sebagai posisi - P mati.Dengan menggunakan rasio mulia φ , setiap posisi- P ( a n , b n )dengan n > 0 bisa diperoleh dari nilai-nilai berikut
a n =(  nφ  ), b n =(  nφ 2  ) (2)
Beberapanilai  awal nφ , nφ 2 ,  nφ  ,  nφ 2  danpasangan  ( a n ,  b n )  yang  diperoleh  disajikan  dalam tabel berikut.
Tabel 3.1Pasangan (  nφ  ,  nφ 2  ) sebagai Posisi- P Permainan Wythoff n 0 1 2 3 4 5 6 7 … nφ 0 1,618  3,236 4,854 6,472 8,090 9,708 11,326 …  nφ  0 1 3 4 6 8 9 11 … nφ 2 0 2,618  5,236 7,854 10,47 2 13,090 15,708 18,326 …
 nφ 2  0 2 5 7 10 13 15 18 …
Karena bisa dibuktikan bahwa untuk setiap n berlaku b n = a n + n [6] sehingga
( a n , b n ) = ( a n , a n + n ).                                                 (3) Dengan kata lain
( a n , b n ) = (  nφ  ,  nφ  + n ).    (4)
5.2 Konstruksi Posisi- P dengan Operator Mex dan Fungsi Sprague-

## Grundy
Penentuan posisi -P permainan Wythoff berdasarkan operator Mex dan fungsi Sprague- Grundy  menggunakan  papan  kotak-kotak  (seperti  papan  catur  tetapi  batas  atas  dan  kanan tidak ada). Setiap kotak diisi dengan bilangan cacah (bulat tak negatif) berdasarkan definisi operator Mex dan fungsi Sprgue-Grundy.
Di awali dengan koordinat (0, 0), kotak selanjutnya diisi dengan bilangan cacah terkecil yang  belum  ada  apabila  apabila  ditarik  garis  luruh  dari  kotak  tersebut  ke  arah  barat,  barat daya,  dan  selatan).  Jadi  menggunakan  operator Mex ( Minimum  excluded ),  akan  diperoleh semua nilai di dalam kotak-kotak :
⋮ ⋮ ⋮ ⋮ ⋮
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋰ 12 12 13 14 15 11 9 16 17 18 19 7 8 10 … 11 11 9 10 7 12 14 2 13 17 6 5 15 8 … 10 10 11 9 8 13 12 0 15 16 17 18 5 7 … 9 9 10 11 12 8 7 13 14 15 16 17 6 19 … 8 8 6 7 10 1 2 5 3 4 15 16 17 18 … 7 7 8 6 9 0 1 4 5 3 14 15 13 17 … 6 6 7 8 1 9 10 3 4 5 13 0 2 16 … 5 5 3 4 0 6 8 10 1 2 7 12 14 9 … 4 4 5 3 2 7 6 9 0 1 8 13 12 11 … 3 3 4 5 6 2 0 1 9 10 12 8 7 15 … 2 2 0 1 5 3 4 8 6 7 11 9 10 14 … 1 1 2 0 4 5 3 7 8 6 10 11 9 13 … 0 0 1 2 3 4 5 6 7 8 9 10 11 12 … 0 1 2 3 4 5 6 7 8 9 10 11 12 …
Gambar  1:  Koordinat  kotak  angka  0  (nol)
menunjukkan posisi- P

## Muhlis Maulana Ibrahim, Loeky Haryanto, Amir Kamal Amir
Koordinat kotak yang berisikan angka 0 (nol) menunjukkan posisi -P dari permainan Wythoff atau permainan Gerakan Ratu ( Queen’s Move ).
5.3Konstruksi Posisi- P dengan Kata Fibonacci Misalkan  * adalah  himpunan  semua  kata  hingga  atas  alfabet  =  { a , b }.  Dengan mendefinisikan fungsiσ :  *  * yang memenuhi sifat: i. σ( a ) = ab dan σ( b ) = a , ii. Untuk setiap kata s = s 1 s 2 … s k berlaku σ( s ) = σ( s 1 ) σ( s 2 )…σ( s k ) Kata Fibonacci s yang didefinisikan sebagai limit
s = lim ( ) k k a   .
Lebih  jauh,  untuk  setiap k berlaku  σ k ( a )  adalah  bagian  awal  ( prefix )  dari s .  Misalnya,  kata σ 5 ( a )= abaababaabaab memberikan 13 simbol-simbol awal dari kata Fibonacci. Dari kata Fibonacci, didefinisikan barisan pasangan bilangan bulat ( a n , b n ) n≥0 dengan a n =  posisi kemunculan huruf a ke- n kali dalam s ; dan b n =  posisi kemunculan huruf b ke- n kali dalam s ; Untuk  memudahkan pencarian pasangan ( a n , b n ), diadopsi notasi a i ( m ) untuk simbol a di posisi ke- m yang muncul ke- i kalinya di dalam kata Fibonacci (demikian pula b j ( n ) untuk simbol b di  posisi  ke- n yang  muncul  ke- j kalinya)  maka  barisan  di  atas  bisa  ditulis  ulang sebagai berikut
σ 5 ( a ) = a 1 (1) b 1 (2) a 2 (3) a 3 (4) b 2 (5) a 4 (6) b 3 (7) a 5 (8) a 6 (9) b 4 (10) a 7 (11) a 8 (12) b 5 (13). Dari nilai a i ( m ) dan b j ( n ) disimpulkan ( a n , b n ) = ( m, n ) adalah posisi- P permainan Wythoff. Jadi ( a 1 , b 1 )= (1, 2), ( a 2 , b 2 )= (3, 5), ( a 3 , b 3 )= (4, 7), ( a 4 , b 4 )= (6, 10), ( a 5 , b 5 )= (8, 13). Jika dibuat dalam tabel akan diperoleh tabel berikut.
Tabel 3.2 Pasangan ( a n , b n )sebagai Posisi- P Permainan Wythoff n 0 1 2 3 4 5 6 7 8 9 10 11 12 … a n 0 1 3 4 6 8 9 11 12 14 16 17 19 … b n 0 2 5 7 10 13 15 18 20 23 26 28 31 …
Pada lampiran disajikan sebanyak 231 posisi- P awal dari permainan Wythoff.

## 6. Hubungan  antara  Permainan  Wythoff  dengan  Beberapa  Konsep Matematika
 Rasio Mulia
Karena posisi- P permainan Wythoff berbentuk (  nφ  ,  nφ 2  ), sudah jelas rasio mulia φ tak bisa dilepaskan dari konsep permainan Fibonacci.
 Relasi Rekurensi Linear Homogin Karena rasio mulia adalah akar tak negatif dari persamaan karakteristik
f ( x ) = x 2  x  1 untuk relasi rekurensi barisan Fibonacci
F n = F n -1 + F n -2 , maka ada hubungan antara permainan Wythoff dengan relasi rekurensi.
 Otomata
Hubungan antara permainan Wythoff dengan otomata tergambar dari konstruksi posisi- P permainan melaluifungsi 𝜎 :  *  * di mana  * merupakan himpunan semua kata hingga atas  = { a , b } dan memenuhi sifat: ( a ) = ab dan( b ) = a .

## 7. Kesimpulan dan Saran
Adapun  beberapa  hal  yang  dapat  disimpulkan  dari  hasil  penelitian  ini  adalah  sebagai berikut:
1. Posisi- P permainan Wythoff bisa dikonstruksi dengan paling sedikit tiga cara:
i .  Menggunakan rasio mulia dan konsep dua barisan Beatty yang salingkomplemen. ii .  Menggunakan  operator Mex dan  fungsi  Sprague-Grundy  yang  diturunkan berdasarkan permainan Gerakan Ratu.
iii .  Menggunakan  kata  Fibonacci  yang  diperoleh  dari  penerapan  morfisma atasalfabet { a , b }.
2. Barisan Fibonacci bisa diperoleh dari kata Fibonacci.
3. Berdasarkan pengetahuan posisi- P dari permainan Wythoff, salah satu pemain, pemain 1  atau  pemain  2  (tergantung  posisi  awal),  bisa  memilih  langkah-langkah  yang membawa ke arah kemenangan.
4. Ekuivalensi  konstruksi  posisi- P yang  diturunkan  dari  fungsi  Sprague-Grundy  dengan konstruksi  posisi- P yang  diturunkan  dari  barisan  atau  kata  Fibonacci  adalah  akibat ekuivalensi  antara  permainan  Gerakan  Ratu  ( Queen’s  Move )  dengan  permainan Wythoff.
Adapun beberapa saran dari penulisan jurnal ini adalah sebagai berikut:
1. Perlu  penelitian  lebih  lanjut  dari  setiap  konstruksi  posisi- P permainan  Wythoff  yang diturunkan dari konsep matematis yang berbeda.
2. Walaupun salah satu pemain bisa memaksakan kemenangan berdasarkan pengetahuan posisi- P dari permainan Wythoff, tetapi di dalam praktek seorang pemain akan sangat sulit  menghapal  seluruh  posisi- P sehingga  disarankan  pembuatan  program  computer untuk  permainan  Wythoff  di  mana  salah  satu  pemain  adalah  computer  yang  bisa ‘menghapal’ ratusan ribu posisi- P .

## Daftar Pustaka
[1] I.G. Connel, A Generalization of Wythoff’s Game, University of Manitoba, 1959.
[2] L. Haryanto, R. Rakhman, A. Alimuddin, Generalisasi Permainan Wythoff ke Permainan Tribonacci, Universitas Hasanuddin, (dikirim ke JMSK).
[3] R. Honsberger, Ingenuity In Mathematics, Mathematical Association of America, United States of America, 1970.
[4] G.  Nivasch, More  on  the  Sprague-Grundy  function  for  Wythoff’s  game ,  Weizmann Institute of Science in Rehovot, Israel, 2009.
[5] http://pages.pacificcoast.net/~cazelais/222/fib-limit.pdf, diakses tanggal 25 Mei 2013.