Vol. 14, No. 1,  100-105,  Juli  2017
Generalisasi Permainan Wythoff ke Permainan Tribonacci
Loeky Haryanto 1 ,Rahmaniah Rakhman 2 , Arnensih Alimuddin 3
Abstrak
Kata fibonacci bisa diturunkan dengan menggunakan suatu iterasi morfisma pada monoid { a , b }*. Dengan  mengidentifikasi posisi  kedua huruf a dan b di dalam kata  fibonacci, diperoleh barisan  ( a n , b n ) n  0 yang  membentuk  posisi- P dari  permainan  Wythoff.  Demikian  pula,  kata tribonacci  bisa  diturunkan  dengan  menggunakan  suatu  iterasi  morfisma  pada  monoid  { a , b , c }*.  Dengan  mengidentifikasi  ketiga  huruf a , b dan c di  dalam  kata  tribonacci,  diperoleh barisan  ( A n , B n , C n ) n  0 yang  membentuk  posisi- P dari  suatu  permainan  yang  ditulis  oleh [2] Error!  Reference  source  not  found. dan  diberi  nama:  permainan  tribonacci.  Selain menggunakan morfisma, kedua barisan ( a n , b n ) n  0 dan ( A n , B n , C n ) n  0 bisa dikonstruksi secara rekursif dengan menggunakan operator Mex ( Minimum excluded ). Berdasarkan parameterdan persyaratan yang digunakan pada kedua konstruksi, disimpulkan bahwa barisan ( A n , B n , C n ) n  0 merupakan  perluasan  dari  barisan  urutan-2  ( a n , b n ) n  0 .  Tetapi  ada  masalah  perluasan  cara konstruksi posisi- P permainan Wythoff berdasarkan barisan Beatty ke cara yang serupa untuk konstruksi posisi- P permainan tribonacci.
Kata  Kunci: Morfisma,  barisan  fibonacci,  permainan  Wythoff,  permainan tribonacci, posisi-P.

## Abstract
The fibonacci word can be derived by iterating a morphism onmonoid { a , b }*. Identifying the positions of the two letters a dan b in this word leads to a construction of a sequence ( a n , b n ) n  0 which  constitutes  the P -positions  of  Wythoff  game.Likewise,  the  tribonacci  word  can  be derived by iterating a  morphism onmonoid { a , b , c }*.  Identifying the positions of the  three letters a , b dan c in  this  word  leads  to  a  construction  of  a  sequence  ( A n , B n , C n ) n  0 which constitutes the P -positions of a game proposed by [2] who called the game: tribonacci game. Besides  using  morphisms,  both  sequence  can  be  constructed  using  the  operator  Mex ( minimum  excluded ).  Based  on  parameters  and  conditions  used  in  both  constructions,  it  is concluded  that  the  sequence  of  triples  ( A n , B n , C n ) n  0 is  a  generalization  of  the  sequence  of pairs  ( a n , b n ) n  0 .    However,  there  is  a  problem  generalizing  Beatty-sequence  method  of construction the P -positions for Wythoff case to a similar method for tribonacci case.
Keywords: Morphism,  fibonacci  sequence,  Wythoff  game,  tribonacci  game,  P - positions.
1 Jurusan Matematika FMIPA Universitas Hasanuddin, email: Lukih2006gmail.com
2 Guru Bidang Matematika, SD  Negeri  Sudirman Makassar, email : Rahmaniah.Rakhman@yahoo.com
3 Mahasiswa Program Matematika Fakultas Pasca Sarjana Universitas Hasanuddin, email : arnensih@yahoo.co.id

## 1. Pendahuluan
Permainan kombinatorik ( combinatorial games ) selalu dimainkan oleh dua orang pemain yang  secara  bergantian  melakukan  langkah-langkah  untuk  merubah  posisi  permainan  sampai salah  satu  pemain  kalah,  yaitu  tak  bisa  melanjutkan  dengan  suatu  langkah  sahih,  langkah  yang sesuai aturan permainan.
Ciri  lain  dari  permainan  kombinatorik  adalah,  terdapat  himpunan  posisi-posisi  yang masing-masing  disebut  posisi- P sedemikian  hingga  jika  posisi  permainan  berada  pada  posisi- P , maka  pemain  yang  mengerjakan  langkah  sebelumnya  ( Previous  move )  bisa  memaksakan permainan  ke  posisi- P dan  sebaliknya  dari  posisi- P ,seorang  pemain  yang  akan  melakukan langkah berikutnya ( Next move ) tak bisa merubah posisi- P tersebut ke posisi- P yang lain, apa pun langkah sahih yang dipilih. Posisi yang bukan posisi- P disebut posisi- N . Salah  satu  posisi- P a  dalah  posisi- P mati,  di  mana  pemain  yang  mendapat  giliran melangkah setelah posisi- P mati ini tak bisa lagi melangkah apa pun dan harus menyerah kalah. Suatu  permainan  kombinatorik  dikatakan  bisa  terselesaikan  ( solved )  jika  semua  posisi- P dari permainan bisa diperoleh.
Permainan  tribonacci  diilhami  oleh  permainan Wythoff yang  sudah  ada  lebih  dari  satu abad  sebelumnya.  Menurut  berbagai  sumber  (misalnya  [1],  hal.  41  dan  52),  permainan  yang diperkenalkan  oleh  Wythoff  pada  tahun  1907  tersebut  merupakan  pengembangan  dari  suatu permainan NIM, permainan yang posisi- P -nya disajikan oleh bilangan-bilangan biner dari posisi permainan.  Semua  permainan  yang  disebut  di  atas  termasuk  dalam  kelompok  permainan kombinatorik.
Pada  Bagian Error!  Reference  source  not  found. berikut,  dibahas  aturan  permainan Wythoff dan permainan tribonacci. Di bagian ini, para pembaca dianggap sudah mengenal konsep untaian  atas  suatu  alfabet  ( string  over  an  alphabet )  ,  termasuk  konsep   sebagai monoid atau semigroup dan konsep morfisma yang terdefinisi pada   . Pada Bagian Error! Reference source not  found. ,  dibahas  solusi  dari  permainan  Wythoff  sedangkan  pada  Bagian Error!  Reference source  not  found. ,  dibahas  solusi  permainan  tribonacci.  Bagian Error!  Reference  source  not found. berisi  kesimpulan  bahwa  permainan  tribonacci  merupakan  perluasan  dari  permainan Wythoff, walaupun masih ada masalah perluasan yang belum terselesaikan.

## 2. Aturan Permainan Wythoff dan Permainan Tribonacci
Permainan  Wythoff  menggunakan  dua  tumpukan  atau  wadah,  mungkin  berbentuk  dua keranjang  berisi  bola  atau  dua  tongkat  tegak  yang  dikalungi  gelang-gelang  logam  atau  bentuk- bentuk  yang  lain.  Jika  masing-masing  tumpukan  berisi  sebanyak a token  (bisa  berupa a buah bola, a gelang, a lembar kartu atau sembarang a benda) dan b token, maka permainan fibonacci dikatakan pada posisi ( a , b ).
Dalam  permainan  fibonacci,  setiap  pemain  secara  bergantian  mengambil  token  dari kedua tumpukan dengan salah satu dari kedua cara berikut:
Cara F1.   Pemain bisa mengambil berapa pun token dari satu tumpukan; atau Cara F2.  Pemain bisa mengambil token dari dua tumpukan, asalkan banyak token yang diambil dari masing-masing tumpukan adalah sama.
Permainan  tribonacci  menggunakan  tiga  tumpukan  atau  wadah.  Jika  masing-masing tumpukan  berisi  sebanyak a token, b token  dan c token  maka  permainan  tribonacci  dikatakan pada posisi ( a , b , c ).
Dalam  permainan  tribonacci,  setiap  pemain  secara  bergantian  mengambil  token  dari beberapa tumpukan dengan salah satu cara dari ketiga cara berikut:

## Loeky Haryanto, Rahmaniah Rakhman, Arnensih Alimuddin
Cara T1.   Pemain bisa mengambil berapa pun token dari salah satu atau dari dua tumpukan; atau Cara T2.  Dari posisi ( a , b , c ), pemain bisa mengambil token dari tiga tumpukan , masing-masing sebanyak α token dari tumpukan pertama , sebanyak β token dari tumpukan kedua , dan sebanyak  token  dari  tumpukan  ketiga  asalkan  banyaknya  token  yang  diambil memenuhi dua syarat pengambilan berikut:
a. 0 < α ≤  a, 0 < β ≤ b, 0 <  ≤ c , dan b. 2  maks{ α, β,  }  α + β +  .
Cara T3.  Dari posisi ( a , b , c ), pemain juga bisa mengambil token dari tiga tumpukan sekaligus: masing-masing  sebanyak α token  dari  dua  tumpukan  berbeda  dan  sebanyak β token dari tumpukan ketiga, asalkan memenuhi kedua syarat berikut :
a. Β > 2 α > 0, dan
b. Jika a’ (ganti: b’,  c’ )  adalah  banyak  token  yang  tersisa  setelah  diambil  dari tumpukan pertama (ganti: tumpukan kedua , ketiga) , maka tidak boleh terjadi a' < c' < b' .

## 3. Solusi Permainan Wythoff
Barisan  bilangan  fibonacci  bisa  diturunkan  dari  kata  fibonacci,  yaitu  sebuah  untaian ( string ) s atas  alfabet  =  { a , b }  yang  didefinisikan  oleh  morfisma  :     .  Morfisma  memenuhi sifat:  ( a ) = ab ,  ( b ) = a dan untuk setiap untaian u = u 1 u 2 ... u n   yang panjangnya n berlaku  sifat  morfik:  ( u )  =  ( u 1 )  ( u 2 )...  ( u n ).  Dengan  notasi  0 = id (yaitu,  0 adalah  fungsi identitas)  dan  notasi  baku  komposisi  fungsi:  untuk  setiap k =  1,  2,  3,  ....,  k =  (  k  1 );  kata Fibonacci s didefinisikan sebagai limit
s = lim k   k ( a ). (1)
Secara komputasi, kata fibonacci bisa didekati oleh untaian-untaian hingga berikut yang diperoleh dari iterasi  pada a sebanyak k = 0, 1, 2, ... dan seterusnya:  0 ( a ) = a ,  ( a ) = ab ,  2 ( a ) = aba ,  3 ( a ) = abaab , ...,  10 ( a ) = abaababaabaababaababaabaababaabaababaababaabaababaababaabaababaab aababaababaabaababaabaababaababaabaababaababaabaababaabaababaabab aabaababaababa ...,dan seterusnya. Barisan { f n } n  0 yang didefinisikan melalui f 0 = 1, f 1 = 2, dan untuk setiap n > 1 berlaku f n = |  n ( a )| (panjang untaian  n ( a )) disebut barisan fibonacci . Barisan ini bisa juga  didefinisikan secara  rekursif  dengan nilai awal f 0 = 1, f 1 = 2,  dan  untuk  setiap n >1 berlaku relasi rekurensi: f n = f n  1 + f n  2 . Cara lain mendefinisikan barisan ini adalah dengan menggunakan rumus Binet: f n = 1 5 1 5 1
2 2
5 [( ) ( ) ] n n    , n = 1, 2, 3, ... .
Dari kata fibonacci, didefinisikan barisan pasangan bilangan bulat ( a n , b n ) n  0 dengan = posisi kemunculan huruf   ke-  kali dalam  ; dan
= posisi kemunculan huruf   ke-  kali dalam  ; n n a a n
b b n s s (2)
Bisa dibuktikan, pasangan ( a n , b n ) merupakan posisi- P permainan Wythoff. Beberapa buku teks menyajikan  pembuktiannya.  misalnya  buku  teks  ([3],  Theorem  2,  hal.  105).  Terdapat  sebanyak 150 posisi- P awal dari permainan  Wythoff. Tabel Error! Reference source not found. berikut menyajikan sebanyak 13 pasangan posisi- P awal ( a n , b n ).
Tabel 1. Pasangan ( a n , b n ) sebagai posisi- P permainan Wythof.

## Loeky Haryanto, Rahmaniah Rakhman, Arnensih Alimuddin
Salah  satu  pemain  bisa  dipaksa  oleh  pemain  lain  untuk  selalu  berada  di  posisi- P sehingga akhirnya berada pada posisi- P mati, yaitu posisi ( a 0 , b 0 ) = (0, 0) dimana pemain tersebut tak bisa lagi melangkah (kalah).
Pembuktian bahwa barisan pasangan ( a n , b n ) membentuk barisan posisi- P dari permainan Wythoff pertama kali dikerjakan oleh Wythoff pada tahun 1907 dan pembuktian ini bisa dijumpai pada  buku-buku  teks  tentang  permainan  kombinatorik,  misalnya  buku  teks  karangan Error! Reference source not found. ([3], hal.101-105). Cara  lain  (cara  rekursif)  mendefinisikan  Tabel Error!  Reference  source  not  found. adalah  dengan  menggunakan  operator Mex ( Minimum  excluded )  yang  didefinisikan  sebagai berikut.

## Definisi 1.
Untuk setiap himpunan atau barisan dari bilangan-bilangan asli   1 m i i x  didefinisikan
Mex   1 m i i x  = min { n  N | n  x i , untuk setiapi  {1, 2, …, m }}.
Dengan definisi Mex di atas, diperoleh cara berikut untuk mendapatkan Tabel 1 secara rekursif, yaitu melalui relasi rekurensi:
{ , | 0 };
. n i i n n a Mex a b i n b a n      (3)
Sebenarnya masih ada cara ketiga menurunkan pasangan ( a n , b n ), yaitu sebagai salah satu barisan  Beatty.  Cara  ini  adalah  cara  yang  paling  elementer  dan  paling  banyak  ditulis  dalam berbagai  buku  teks  permainan  kombinatorik.  Sesungguhnya  (misalnya  [3])  posisi- P permainan Wythoff  membentuk  barisan  Beatty  (  n ρ  ,  n ρ 2  )  di  mana  ρ  = 1 5 2  adalah  rasio  mulia  ( golden ratio )  dan  x  adalah  hasil  dari  pembulatan  ke  bawah  terhadap  bilangan x (yaitu,  ...  adalah fungsi floor ).
Tetapi  cara  ini  belum  bisa  diperluas  untuk  konstruksi  posisi- P permainan  tribonacci. Misalnya dengan memandang ruas paling kanan dari bentuk kesamaan berikut ( a n , b n ) = (  n ρ  ,  n ρ 2  ) = (  n ρ + 0  ,  n σ+ 0  ),
di mana σ = ρ 2 , setiap usaha perluasan ruas kanan bentuk ini ke bentuk
( A n , B n , C n ) = (  n α + α ’  ,  n β+ β ’  ,  n γ+ γ ’  ), (4)
akan gagal, sesuai Teorema 5 dari tulisan [2].
n 0 1 2 3 4 5 6 7 8 9 10 11 12 13  a n 0 1 3 4 6 8 9 11 12 14 16 17 19 21  b n 0 2 5 7 10 13 15 18 20 23 26 28 31 34 

## 4. Solusi Permainan Tribonacci
Barisan tribonacci bisa diturunkan dari kata tribonacci melalui cara yang serupa dengan cara penurunan barisan fibonacci. Persisnya, kata tribonacci adalah sebuah untaian ( string ) t atas alfabet  = { a , b , c } yang  didefinisikan oleh morfisma  :     . Morfisma ini memenuhi sifat:  ( a ) = ab ,  ( b ) = ac ,  ( c ) = a dan untuk setiap untaian u = u 1 u 2 ... u n   (panjang n ) berlaku sifat morfik:  ( u ) =  ( u 1 )  ( u 2 )...  ( u n ). Kata tribonacci t didefinisikan sebagai limit
t = lim k   k ( a ). (5)
Secara komputasi, kata tribonacci bisa didekati oleh untaian-untaian hingga berikut yang diperoleh dari iterasi  pada a dengan banyak kali k = 0, 1, 2, ... dan seterusnya:  0 ( a ) = a ,  ( a ) = ab ,  2 ( a ) = abac ,  3 ( a ) = abacaba , ...,  8 ( a ) = abacabaabacababacabaabacabacabaabacababacabaabacabaabacababacabaa bacabacabaabacababacabaabacababacabaabacabacabaabacababacabaabaca baabacababacabaabac ..., dan seterusnya. Barisan { T n } n  0 yang didefinisikan melalui T 0 = 1, T 1 = 2, T 2 = 4, dan untuk setiap n > 2 berlaku T n = |  n ( a )| (panjang untaian  n ( a )), disebut barisan tribonacci. Definisi lain dari barisan tribonacci adalah definisi secara rekursif dengan nilai awal T 0 = 1, T 1 = 2, T 2 = 4, dan untuk setiap n > 2 berlaku T n = T n  1 + T n  2 + T n  3 . Dari kata tribonacci, didefinisikan barisan urutan-3 ( A n , B n , C n ) n  0 dengan
= posisi kemunculan huruf   ke-  kali dalam  ; dan ;
posisi kemunculan huruf   ke-  kali dalam  ; dan ;
posisi kemunculan huruf   ke-  kali dalam  .
n n n A a n B
b n C c n   t t t (6)
Secara lengkap, terdapat sebanyak 180 posisi- P awal dari permainan Tribonacci. Cara  lain  mendapatkan  Tabel Error!  Reference  source  not found. adalah  dengan  cara rekursif melalui relasi rekurensi:
= { ,   , | 0 };
{ , ;  0 };
. n i i i n n i i i i n n n A Mex A B C i n
B A Mex B A C B i n C A B n            (7)
Pembuktian  kedua  cara  konstruksi  melalui  ekspresi  ( Error!  Reference  source  not found. )  dan  melalui  ekspresi  ( Error!  Reference  source  not  found. )  akan  membentuk  satu barisan  urutan-3  ( A n , B n , C n )  yang  sama,  yaitu  barisan  semua  posisi- P permainan  tribonacci, dibuktikan oleh [2], atau secara lebih detail dan dengan sedikit perbaikan, disajikan di [4].
Tabel 2. Urutan-3 ( A n , B n , C n ) Sebagai Posisi- P Permainan Tribonacci
n 0 1 2 3 4 5 6 7 8 9 10  11  12  13  14  15 ⋯ A n 0 1 3 5 7 8 10  12  14  16  18  20  21  23  25  27 ⋯ B n 0 2 6 9 13  15  19  22  26  30  33  37  39  43  46  50
⋯ C n 0 4 11  17  24  28  35  41  48  55  61  68  72  79  85  92 ⋯

## 5. Kesimpulan
Konstruksi  suatu  struktur  matematis  (barisan,  matriks,  gelanggang  aljabar,  dan sebagainya)  merupakan  perluasan  dari  konstruksi  struktur  matematis  yang  lain  jika  semua parameter  yang  ada  di  dalam  struktur  pertama  berasosiasi  dengan  parameter  yang  serupa  yang juga  ada  pada  struktur  yang  kedua  (tetapi  tidak  sebaliknya),  atau  syarat-syarat  yang  diperlukan untuk konstruksi struktur yang pertama lebih longgar (lebih sedikit) daripada syarat-syarat yang diperlukan untuk konstruksi struktur yang kedua.
Kedua permainan Wythoff dan tribonacci memiliki himpunan posisi- P yang dikonstruksi dengan  dua  cara  yang  serupa.  Himpunan  posisi- P kedua  permainan  masing-masing  diturunkan dari  barisan  fibonacci  dan  barisan  tribonacci.  Fakta  bahwa  barisan  tribonacci  merupakan perluasan  dari  barisan  fibonacci,  merupakan  petunjuk  pertama  bahwa  permainan  tribonacci merupakan  perluasan  dari  permainan  Wythoff.  Fakta  lain,  banyaknya  parameter A n , B n ,  dan C n dari  posisi- P permainan  tribonacci  adalah  tiga  buah  sedangkan  banyaknya  parameter a n dan b n dari posisi- P permainan Wythoff hanya dua.
Demikian pula, kata fibonacci dikonstruksi atas alfabet { a , b } yang terdiri atas dua huruf sedangkan  kata  tribonacci  dikonstruksi  atas  alfabet  { a , b }  yang  terdiri  atas  tiga  huruf,  padahal konstruksi keduanya dilakukan  melalui proses limit yang serupa: melalui ekspresi limit ( Error! Reference source not found. ) dan melalui ekspresi limit ( Error! Reference source not found. ). Posisi- P permainan  tribonacci  merupakan  perluasan  dari  posisi- P permainan  fibonacci bisa  juga  dilihat  dari  keserupaan  antara  ekspresi  ( Error!  Reference  source  not  found. )  yang diperoleh  dari  posisi- P permainan  Wythoff  dengan  ekspresi  ( Error!  Reference  source  not found. ) yang diperoleh dari posisi- P permainan tribonacci, tetapi yang terakhir mengandung tiga parameter. Hal ini lebih dipertegas oleh kemiripan antara ekspresi ( Error! Reference source not found. ) untuk permainan Wythoff dengan ekspresi ( Error! Reference source not found. ) untuk permainan tribonacci, tetapi yang terakhir lebih lengkap dan lebih banyak parameternya.
Masalah  yang  tersisa  adalah  bagaimana  memperluas  cara  konstruksi  posisi- P untuk permainan  Wythoff  dengan  menggunakan  barisan  Beatty  ke  cara  konstruksi  posisi- P untuk permainan  tribonacci.  Jika  perluasan  cara  ini  ada,  tidak  mungkin  berbentuk  seperti  ekspresi ( Error! Reference source not found. ).

## Daftar Pustaka
[1]    Berlekamp  E.R.,  Conway  J.H.,  and  Guy  R.,  2003. Winning  ways  for  your  Mathematical Play, Vol.1 .  AK Peters.
[2]     Duchêne  E.,  and  Rigo  M.,  2008.  A  Morphic  Approach  to  Combinatorial  Games:  The tribonacci Case . RAIRO, Theoretical Informatics and Applications. 42 : 375-393.
[3]    Honsberger  R.,  1970.  Ingenuity  in  Mathematics. Mathematical  Association  of  America, Edisi 5 .
[4] Rakhman R., 2012. Solusi Permainan Tribonacci Sebagai Sebuah Perluasan dari
Permainan Wythoff. Tesis . Program Studi S2 Matematika, Fakultas MIPA, Universitas Hasanuddin.