Kompetisi Sains Nasional (KSNK) Kota 2021 - Komputer, Nomor 9

Andi dan Budi sedang bermain Tic Tac Toe, yaitu permainan yang dilakukan di sebuah petak. Andi menuliskan huruf X dan Budi menuliskan huruf O secara bergantian dimulai dari Andi. Pemain yang berhasil membuat 3 huruf dalam 1 garis lurus memenangkan permainan (garis mendatar, vertikal dan diagonal diperbolehkan).

Sebagai contoh, jika petak berukuran 3 x 3 dan berakhir seperti pada gambar di bawah ini:

X	O	X
O	X	X
X	O	O

maka Andi telah memenangkan permainan, karena pada salah satu diagonal terdapat garis lurus berisi 3 buah huruf X.

Permainan dikatakan seimbang apabila petak sudah penuh terisi, sementara kedua pemain belum ada yang menjadi pemenang. Apabila ukuran petak adalah 30 x 31 dan diketahui permainan berakhir seimbang, berapa banyak kemungkinan susunan posisi akhir dari petak tersebut (rotasi dan refleksi petak dihitung berbeda)?

1. 6
2. 8
3. 2^29 + 2^30
4. 2^30 + 2^31
5. 2^31 + 2^32