Câu hỏi 48
Cho $m, n$ là các số nguyên dương. Có $n$ đống tiền vàng; đống thứ $i$ chứa $a_i (\gt 0)$ đồng ($i = 1, \dots, n$). Xét trò chơi sau:
**Bước 1** Bob chọn các tập $B_1, B_2, \dots, B_n$ sao cho mỗi $B_i$ là tập con không rỗng của $\{1, 2, \dots, m\}$.
**Bước 2** Alice chọn một tập $S$ sao cho $S$ là tập con không rỗng của $\{1, 2, \dots, m\}$, sau khi biết các tập $B_1, B_2, \dots, B_n$ mà Bob đã chọn ở Bước 1.
**Bước 3** Tiền vàng trong đống thứ $i$ ($i = 1, 2, \dots, n$) được trao cho Bob nếu số phần tử của $B_i \cap S$ là chẵn; nếu không thì được trao cho Alice.
Chứng minh rằng dù Bob chọn các tập $B_1, B_2, \dots, B_n$ thế nào, Alice luôn có thể chọn tập $S$ để nhận tổng số tiền vàng nhiều hơn Bob.
**Bước 1** Bob chọn các tập $B_1, B_2, \dots, B_n$ sao cho mỗi $B_i$ là tập con không rỗng của $\{1, 2, \dots, m\}$.
**Bước 2** Alice chọn một tập $S$ sao cho $S$ là tập con không rỗng của $\{1, 2, \dots, m\}$, sau khi biết các tập $B_1, B_2, \dots, B_n$ mà Bob đã chọn ở Bước 1.
**Bước 3** Tiền vàng trong đống thứ $i$ ($i = 1, 2, \dots, n$) được trao cho Bob nếu số phần tử của $B_i \cap S$ là chẵn; nếu không thì được trao cho Alice.
Chứng minh rằng dù Bob chọn các tập $B_1, B_2, \dots, B_n$ thế nào, Alice luôn có thể chọn tập $S$ để nhận tổng số tiền vàng nhiều hơn Bob.