Question 26 — UTC Tryout #2 OSN-K 2025 B1a

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 = 6$ dan tersedia 7 karakter berikut: {1, 3, 5}, {2, 4}, {1, 6}, {3, 4, 5}, {2, 6}, {1, 4}, {3, 6}

Berapa karakter paling sedikit yang perlu direkrut Bearcu untuk membentuk party yang seimbang?