Rubik Cube

Rubik Cube adalah Puzzle yang diciptakan tahun 1974 oleh Professor Arsitektur, Erno Rubik. Untuk lebih jelas mengenai sejarah Rubik Cube, silakan lihat wikipedia.

Berkat adanya acara The Master saat Deddy Corbuzier "mengalahkan" Abel Brata dalam "blindfolded" Rubik Cube, di Indonesia permainan ini menjadi popular berkali-kali lipat. Toko-toko mainan, aksesories, games, souvenir, etc semuanya menjual Rubik Cube..!!

Ada beberapa pertanyaan matematis yang berhubungan dengan Rubik Cube:
1. Ada berapa banyak permutasi yang mungkin dalam membentuk suatu rubik cube 3x3x3?
2. Suatu Rubik Cube yang diacak secara random dapat dipecahkan dalam x langkah atau kurang. Tentukan nilai x yang minimum.
3. Bagaimana algoritma terbaik untuk memecahkan Rubik Cube?

=======================================================================

Berapa Banyak Permutasi Yang Mungkin?

Rubik Cube original (3x3x3) mempunyai 8 corner dan 12 edge. Untuk setiap corner, terdapat 8! cara untuk menyusun semua corner di tempat yang berbeda-beda. Secara orientasi, tiap pojok ini mempunyai 3 wajah/orientasi. Namun, dari 8 corner ini, corner yang satu harus bergantung dari ke-7 corner yang lainnya. Artinya, kemungkinan orientasi corner ada sebanyak 3⁷ (2187) kemungkinan. Untuk edge, terdapat 12!/2 kemungkinan untuk menempatkan ke petak yang berbeda, mengingat permutasi ganjil pada corner juga mengimplikasikan permutasi ganjil pada edge. Tiap edge memiliki 2 wajah/ orientasi. Dari 12 edge yang ada, 11 adalah independent, sedangkan edge yang satu lagi pasti terikat dengan edge lainnya, maka terdapat 2¹¹ (2048) kemungkinan untuk menyusun orinetasi edge. Bagian tengah dari Rubik tidak pernah berubah, maka kemungkinannya adalah 1.

Mengalikan semuanya, maka hasilnya:

Jadi, total permutasi yang mungkin dalam membentuk Rubik Cube adalah

43.252.003.274.489.856.000

Sangat banyak sekali....

=======================================================================

Optimal Solusi untuk Rubik Cube??

Perhatikan bahwa untuk memecahkan suatu Rubik Cube secara optimal, dibutuhkan kemampuan analisis terhadap pola-pola Rubik Cube. Mengingat jumlah permutasi Rubik secara total berjumlah 43 Quantillion, maka mustahil bagi manusia untuk dapat memecahkan Rubik Cube dalam langkah seminimum mungkin. (mungkin bukan mustahil, tapi tentunya akan sangat sangat sangat sangat lama).

Agustus 2007, Daniel Kunkle menggunakan super komputer untuk memecahkan Rubik Cube untuk menunjukkan bahwa semua pola Rubik dapat dipecahkan tidak lebih dari 26 langkah. Tahun 2008, Tomas Rokichi mempunyai bukti komputasional bahwa semua Rubik dapat dipecahkan dalam 25 langkah atau kurang. Selanjutnya, jumlah ini akan berkurang menjadi 23. Agustus 2008, Rokichi membuktikan bahwa langkah maksimum untuk Rubik Cube adalah 22 langkah. God Algorithm (Algoritma yang bertujuan meyelesaikan Rubik dalam langkah seminimum mungkin) untuk menyelesaikan Rubik Cuba ada banyak, misalnya: Thistlethwaite's Algorithm, Kociemba's Algorithm, Korf's Algorithm, etc. Semua dapat dilihat di wikipedia. Ketiga algoritma tersebut digunakan pada komputer.

Untuk melakukan langkah seminimum mungkin memang mustahil jika dilakukan oleh manusia, namun tidak mustahil untuk dapat dipecahkan dengan cepat oleh manusia. Ada yang melakukannya kurang dari 1 menit, kurang dari 30 detik, etc.

Metode yang sederhana dalam memecahkan Rubik Cube dengan cepat, antara lain:
1. Fridrich Method (Layer by Layer Method) ditemukan oleh Jessica Fridrich
Metode ini dimulai dengan membentuk tanda cross pada layer pertama, dilanjutkan dengan memecahkan layer pertama, layer kedua, hingga layer ketiga. Metode ini adalah metode yang sering digunakan oleh orang, mudah dimengerti, namun membutuhkan banyak sekali langkah (boros).

Untuk mempelajari metode ini, bisa cari di wikibook, atau di youtube..
Layer by layer Mthod selanjutnya dikembangkan menjadi F2L alternatif, ZB Method, ZZ Method, dan VH Method. Lihat di wikibook.

2. Petrus System (Block Methods)
Metode ini dimulai dengan membentuk 2x2x3 block di cube, dilanjutkan dengan memecahkan 3x3x2 block, tapi juga mengubah edge di layer terakhir. Kemudian, layer terakhir dikerjakan dalam 2 tahap, pertama pojok, kedua adalah edge. Metode ini sering digunakan dalam contest langkah seminimum mungkin.

Metode Petrus memiliki kemiripan dengan metode Heiss, dan Gilles Roux Method. Lihat di wikibook.

3. Waterman Method (Corner First Method)
Untuk mempelajari metode ini, dibutuhkan 90 algoritma dasar (yang sudah cukup banyak dan menyulitkan untuk dipelajari..). Pecahkan face di L, pojok di R, dan selesaikan edge. Metode ini adalah metode menyelesaikan Rubik Cube yang sangat sangat cepat.

Metode yang mirip adalah Jelinek Method, yaitu metode untuk 4x4x4 cube. Lihat di wikibook.

Untuk mempelajari Waterman Method memang dibutuhkan kesabaran, karena lebih rumit daripada Fridrich Method, namun sudah terbukti keampuhannya dari pemenang Rubik Cube: Josef Jelinek!! Silakan lihat sendiri di situsnya:

WATERMAN METHOD

Untuk menyelesaikan Rubik Cube, kalian bisa menggunakan software yang bisa didownload gratis di internet. Semua rubik dapat dikerjakan dalam 20 langkah (rata-rata)..

Note: Lihat juga di situs resmi Rubik di http://rubiks.com.
Solusi Rubiks.com layer by layer: http://www.youcandothecube.com/secret-unlocked/solution-stage-one.aspx.
Saran saya, pelajarai semua metodenya. Layer by layer, block by block, waterman, dan berbagai versi berbeda lainnya. Menggabungkan beberapa metode tersebut membuat rubiks dapat dikerjakan dengan lebih cepat :).

Click Here to Read More..

Chinese Remainder Theorem Eksplisit

Di post sebelumnya sudah dibahas mengenai Chinese Remainder Theorem, tapi hanya dijelaskan solusi yang dilakukan secara iteratif. (Lihat di SINI) . Di post ini, akan ditunjukkan Rumus/ Teorema Chinese Remainder Theorem yang eksplisit yang dapat secara langsung digunakan untuk mencari solusi.

Diberikan sistem kongruensi sebagai berikut.

haruslah saling relatif prima
Dengan demikian, kita dapat mencari nilai dengan rumus berikut.

dimana

untuk setiap .
dan adalah invers dari modulo untuk setiap .

Untuk lebih memahami, silakan lihat contoh di bawah. :)

CONTOH 1:
Suatu bilangan bulat positif akan bersisa 1 jika dibagi 3, bersisa 2 jika dibagi 5, dan bersisa 3 jika dibagi 7. Tentukan bilangan bulat terkecil yang memenuhi kondisi tersebut.

Jawab
Soal di atas dapat ditulis ulang menjadi:

Karena 3,5, dan 7 relatif prima, maka rumus CRT (Chinese Remainder Theorem) dapat langsung digunakan.
Kita dapatkan , , , dan . Untuk menentukan , kita selesaikan , menjadi , maka . Untuk menentukan , kita selesaikan , maka . Untuk menentukan , kita selesaikan , maka

Tinggal memasukkan semua elemen yang ada ke dalam rumus.

Jadi, bilangan bulat positif terkecil itu adalah 52. Bisa dicek bahwa 52 akan bersisa 1 jika dibagi3, bersisa 2 jika dibagi 5 dan bersisa 3 jika dibagi 7.

Untuk membuktikan formula ini sangat sederhana. Lihat kotak dibawah.

Tentukan

Solusi yang diberikan adalah

Mula-mula pandang bahwa

(merupakan solusi yang sudah didefinisikan sebelumnya)

Jika solusi tersebut memenuhi syarat awal bahwa akan bersisa jika dibagi untuk setiap , maka solusi tersebut terbukti kebenarannya.

Kita coba periksa sisanya jika dibagi dengan
Karena , maka tentunya .
Karena , maka juga.
Dan seterusnya dari hingga
Oleh karenanya:

Menurut definisi sebelumnya , maka

Ternyata, jika dibagi dengan akan bersisa . Artinya, ini sesuai dengan salah satu syarat yang diberikan.

Pembuktian masih dilanjutkan dengan mengecek sisanya jika dibagi .
Karena , maka
Karena , maka .
Dan hal sama juga berlaku pada hingga (silakan dicek sendiri, dan ketahuilah mengapa demikian)
Oleh karenanya:

Karena kita tahu bahwa , maka

Ternyata sesuai dengan syarat baris kedua.

Pembuktian dilanjutkan dengan mengecek sisanya jika dibagi hingga . Masing-masing akan menyisakan , hingga . Dengan demikian, definisi awal yang diberikan terbukti.

TERBUKTI sebagai solusi CRT

Namun, ada hal yang masih perlu dibuktikan. Karena mempunyai banyak jawab, akibatnya juga mempunyai banyak jawab.
Misalkan dan adalah solusi CRT yang nilainya berbeda, maka:
________Untuk setiap :

Menggabungkan keduanya:

Sesuai dengan teorema keterbagian bahwa: "jika dan , maka ", maka

Dari hasil di atas, diketahui bahwa antara solusi yang satu dengan solusi yang lain adalah kongruen modulo M. Jadi, solusi CRT menjadi:

TERBUKTI

Untuk lebih memahami penggunaan CRT. Perhatikan contoh di bawah. Kerjakan sebagai latihan.

CONTOH 2:
Temukan integer yang bersisa 1 jika dibagi 2 dan jika dibagi 3

Jawab:


, ,
, maka
, maka

CONTOH 3:
Temukan integer terkecil yang memenuhi

Jawab:
(Note: akan lebih mudah jika diselesaikan dengan komputer :D)







Kemudian, carilah .
, maka , maka
, maka
, maka , maka
, maka , maka
, maka , maka
(Note: untuk mencari invers modulo, biasakan untuk menggunakan teorema Euler).

Selanjutnya tinggal memasukkan ke rumus

Jadi, bilangan terkecil itu adalah 150999.

=======================================================================

Demikianlah posting kali ini.
Materi CRT memang jarang digunakan dalam olimpiade matematika, namun aplikasinya menarik :D.

Untuk memahaminya, pelajari materi dasar dahulu seperti keterbagian, modulo, dan invers modulo. Jika masih belum paham, tanyakan di comment atau YM atau email, bagian mana yang membuat kamu tidak paham. Key? :).

Click Here to Read More..