Jump to content
Sign in to follow this  
ivanwangsa

Hapus bilangan sana sini

Recommended Posts

Misalkan $n$ adalah sebuah bilangan bulat positif. $n$ bilangan bulat positif pertama telah ditulis oleh Pak Johan pada papan tulis. Kemudian, Pak Johan menguji Ani dan Budi, dua orang muridnya, dengan permainan seperti berikut.


 


Ani dan Budi bermain secara bergiliran, dimulai dari Ani. Pada gilirannya, pemain memilih satu angka yang masih tersisa di papan tulis, kemudian menghapus semua angka yang membagi angka yang telah terpilih tersebut. Pemain yang tidak dapat menjalankan gilirannya dianggap kalah.


 


Untuk setiap bilangan bulat positif $n$, tentukan siapa yang memiliki strategi kemenangan, Ani atau Budi? Dan apakah strateginya?


  • Upvote 1

Share this post


Link to post
Share on other sites

Ani punya strategi kemenangan. Tapi saya ga tau strategi eksplisitnya.


 


Andaikan Budi punya strategi kemenangan. Misalkan pertama Ani menghapus bilangan $1$. Kemudian Budi menghapus pembagi-pembagi dari $k$, sesuai strategi kemenangannya. Dari situasi ini pemain yang terakhir melangkah memiliki strategi kemenangan.


 


Apabila pada langkah pertama Ani menghapus semua pembagi dari $k$ (termasuk $1$), maka diperoleh situasi yang sama dengan posisi Ani dan Budi ditukar. Akibatnya, Ani memiliki strategi kemenangan dengan meniru strategi Budi. Kontradiksi.


 


Jadi Ani punya strategi kemenangan. (Di permainan seperti ini, salah satu pemain pasti punya strategi kemenangan. Hayo kenapa?)


  • Upvote 1

Share this post


Link to post
Share on other sites

Apabila pada langkah pertama Ani menghapus semua pembagi dari $k$ (termasuk $1$), maka diperoleh situasi yang sama dengan posisi Ani dan Budi ditukar.

 

Kayaknya ngga bisa gitu deh... Misalnya bilangannya 1,2,3,4,5,6, dan Ani menghapus angka 4, maka angka 1,2,4 dihapus. Sekarang giliran Budi, dia akan mendapati papan bertuliskan 3,5,6, TIDAK SAMA dengan posisi Ani sebelumnya (kecuali saya salah mengerti maksud anda).

Share this post


Link to post
Share on other sites

Maksudnya bukan begitu.


 


Jadi begini, asumsikan Budi punya strategi kemenangan. Maka apapun langkah pertama Ani, Budi tetap bisa menjamin kemenangan. Katakanlah Ani menghapus angka 1, maka bilangan-bilangan sisanya adalah 2,3,4,5,6. Dari posisi terakhir ini Budi punya strategi kemenangan, katakanlah dengan menghapus semua pembagi dari 4. Maka menjadi 3,5,6. Posisi ini adalah posisi kemenangan untuk Budi.


 


Dengan kata lain, apabila kita tiba di posisi 3,5,6, pemain yang berikutnya melangkah kalah.


 


Sekarang kita ulang permainannya. Di langkah pertama, Ani menghapus semua pembagi dari 4. Maka bilangan-bilangan sisanya adalah 3,5,6. Dari argumen di atas, posisi ini adalah posisi kekalahan untuk pemain berikutnya, yaitu Budi. Ini kontradiksi dengan fakta bahwa Budi punya strategi kemenangan.


Share this post


Link to post
Share on other sites

Oh ngerti deh. Tapi tetep argumennya tidak valid. Maksudnya gini: kalau memang Ani menghapus angka 1, maka papan 2,3,4,5,6 BELUM TENTU merupakan posisi kemenangan untuk Budi. Kalau memang posisi 1,2,3,4,5,6 adalah posisi kemenangan dari awal, maka Ani yang memiliki strategi kemenangan. Tapi jika 1,2,3,4,5,6 adalah posisi kekalahan (dalam arti, pilihan apapun yang diambil Ani akan menghasilkan di posisi kemenangan untuk Budi), maka Budi lah yang memiliki strategi kemenangan.


 


Intinya: pemain mana yang memiliki strategi kemenangan akan tergantung dari $n$ itu sendiri.


 


Namanya strategi kemenangan itu selalu inputnya adalah konfigurasi papan dari game, sehingga argumen anda yang "Andaikan Budi memiliki strategi kemenangan" itu yang nggak valid. Harusnya analisa kita adalah: konfigurasi - konfigurasi berikut adalah posisi kemenangan, dan konfigurasi-konfigurasi lainnya adalah posisi kekalahan. Jika Ani menghapus angka 1, dan sisanya adalah 2,3,4,5,6 dan itu merupakan posisi kekalahan untuk Budi, maka tidak perduli apapun strategi Budi, pasti Budi kalah (karena menghapus angka 1 itu sendiri adalah bagian dari strategi kemenangan Ani).


Edited by hendrata

Share this post


Link to post
Share on other sites

Justru kita asumsikan bahwa Budi punya strategi kemenangan. Artinya, 2,3,4,5,6 harus merupakan posisi kemenangan untuk Budi. Tapi nanti ternyata diperoleh kontradiksi, maka Ani yang punya strategi kemenangan.


Share this post


Link to post
Share on other sites

Hmm.. Oke saya akan tulis seformal mungkin.


 


Definisi: Misalkan $S$ adalah suatu himpunan bilangan asli dan di papan tulis tertulis bilangan-bilangan di $S$. Kita sebut $S$ posisi kemenangan apabila pemain yang mendapat giliran pertama memiliki strategi kemenangan. Kalau tidak, maka pemain yang mendapat giliran kedua memiliki strategi kemenangan dan kita sebut $S$ posisi kekalahan.


 


Notasi: Untuk setiap bilangan asli $m$, misalkan $\langle m\rangle$ adalah himpunan dari semua pembagi dari $m$.


 


Fakta 1: Himpunan kosong adalah posisi kekalahan.


Fakta 2: Jika $S$ adalah posisi kemenangan, maka terdapat $k\in S$ sehingga $S\setminus\langle k\rangle$ adalah posisi kekalahan.


Fakta 3: Jika $S$ adalah posisi kekalahan, maka untuk setiap $k\in S$ himpunan $S\setminus\langle k\rangle$ adalah posisi kemenangan.


 


Klaim: Untuk setiap bilangan asli $n$, himpunan $\{1,2,\ldots,n\}$ adalah posisi kemenangan.


 


Bukti:


(1) Andaikan tidak, maka $\{1,2,\ldots,n\}$ adalah posisi kekalahan.


(2) Menurut fakta 3, himpunan $\{1,2,3,\ldots,n\}\setminus\langle 1\rangle=\{2,3,\ldots,n\}$ adalah posisi kemenangan.


(3) Menurut fakta 2, terdapat $k\in\{2,3,\ldots,n\}$ sehingga $\{2,3,\ldots,n\}\setminus\langle k\rangle$ adalah posisi kekalahan.


(4) Karena $1$ adalah pembagi dari $k$, maka $1\in\langle k\rangle$.


(5) Maka $\{2,3,\ldots,n\}\setminus\langle k\rangle=\{1,2,\ldots,n\}\setminus\langle k\rangle$.


(6) Dari (3) dan (5), kita peroleh bahwa $\{1,2,\ldots,n\}\setminus\langle k\rangle$ adalah posisi kekalahan.


(7) Di sisi lain, karena $\{1,2,\ldots,n\}$ adalah posisi kekalahan (lihat (1)), maka fakta 3 mengatakan bahwa $\{1,2,\ldots,n\}\setminus\langle k\rangle$ adalah posisi kemenangan.


(8) Kita peroleh kontradiksi dari (6) dan (7).


(9) Maka pengandaian di langkah (1) adalah salah.


(10) Maka $\{1,2,\ldots,n\}$ adalah posisi kemenangan.


Share this post


Link to post
Share on other sites

Hmm iya ya, bukti formalnya bener sih. Saya justru masih pengen cari generalisasinya dengan mencari aturannya posisi mana aja yang merupakan posisi kemenangan, dan posisi mana aja yang merupakan posisi kekalahan.


 


Misalnya, suatu "rantai" (2,4,8,16,dst) pasti posisi kemenangan. Sejumlah genap rantai simetris pasti posisi kekalahan (2,4,8, 3,9,27 adalah posisi kekalahan, karena pemain kedua pasti bisa meniru langkah pemain pertama secara simetris). Kalau ada 3 rantai, jadi mirip game Nim: misalnya (2,4,8, 3,9, 5), ini adalah posisi kekalahan.


 


Menurut bukti anda di atas, setiap papan yang mengandung "1" pasti posisi kemenangan. Demikian juga jika gcd dari seluruh papan ada di papan, ini juga posisi kemenangan (2,10,12,14 adalah posisi kemenangan).


 


Kalau ada faktor persekutuan, ini jauh lebih ribet: (2,3,6) adalah posisi kemenangan, tapi (2,3,5,6) adalah posisi kekalahan.


Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

×