Question 27 — UTC Tryout #2 OSN-K 2025 B1b

Bearcu sedang bermain RPG. Pada game ini, setiap lawan memiliki kelemahan terhadap satu elemen. Elemen-elemen ini dilambangkan dengan bilangan dari 1 sampai n. Bearcu perlu membentuk party yang terdiri sejumlah karakter. Masing-masing karakter dapat mengalahkan lawan dengan elemen tertentu, yang dinotasikan sebagai himpunan bagian dari {1, 2, ... n}. Sebagai contoh, jika n = 5, karakter dengan himpunan {1, 3, 4} bisa mengalahkan lawan dengan kelemahan elemen 1, 3, atau 4.

Suatu party dikatakan seimbang jika untuk semua lawan yang mungkin, terdapat setidaknya satu karakter dalam party yang bisa mengalahkan lawan itu. Sebagai contoh, jika n = 5, party yang terdiri atas dua karakter {1, 3, 4} dan {2, 3, 5} seimbang. Akan tetapi, party dengan karakter {1, 2, 3} dan {2, 5} tidak seimbang, karena tidak memiliki elemen 4. Urutan karakter di dalam party tidak mempengaruhi.

Misalkan n = 8 dan tersedia 56 karakter berikut untuk direkrut:

{1,2,3}  {1,3,6}  {1,5,7}  {2,3,7}  {2,5,8}  {3,5,6}  {4,5,8}
{1,2,4}  {1,3,7}  {1,5,8}  {2,3,8}  {2,6,7}  {3,5,7}  {4,6,7}
{1,2,5}  {1,3,8}  {1,6,7}  {2,4,5}  {2,6,8}  {3,5,8}  {4,6,8}
{1,2,6}  {1,4,5}  {1,6,8}  {2,4,6}  {2,7,8}  {3,6,7}  {4,7,8}
{1,2,7}  {1,4,6}  {1,7,8}  {2,4,7}  {3,4,5}  {3,6,8}  {5,6,7}
{1,2,8}  {1,4,7}  {2,3,4}  {2,4,8}  {3,4,6}  {3,7,8}  {5,6,8}
{1,3,4}  {1,4,8}  {2,3,5}  {2,5,6}  {3,4,7}  {4,5,6}  {5,7,8}
{1,3,5}  {1,5,6}  {2,3,6}  {2,5,7}  {3,4,8}  {4,5,7}  {6,7,8}

Ada berapa cara Bearcu membentuk party yang seimbang dengan banyaknya karakter paling sedikit?