Với [imath]n=2[/imath] ta dễ dàng kiểm tra được.
Giả sử đpcm đúng với [imath]n=m \geq 2[/imath]. Ta sẽ chứng minh đpcm đúng với [imath]n=m+1[/imath].
Xét [imath]A=\lbrace{ a_1,a_2,...,a_m,a_{m+1} \rbrace}[/imath]
Xét một cách chọn [imath]2^m+1[/imath] tập con bất kỳ.
+ Nếu tồn tại không ít hơn [imath]2^{m-1}+1[/imath] tập hợp không chứa phần tử [imath]a_{m+1}[/imath].
Khi đó [imath]2^{m-1}+1[/imath] tập hợp này sẽ là tập con của [imath]B=\lbrace{ a_1,a_2,...,a_m \rbrace}[/imath] nên theo giả thiết quy nạp ta có đpcm.
+ Nếu tồn tại không quá [imath]2^{m-1}[/imath] tập hợp không chứa phần tử [imath]a_{m+1}[/imath].
Khi đó, tồn tại [imath]2^m+1-2^{m-1}=2^{m-1}+1[/imath] tập hợp chứa [imath]a_{m+1}[/imath]
Xét [imath]2^{m-1}+1[/imath] tập hợp đó và bỏ đi phần tử [imath]a_{m+1}[/imath]. Khi đó [imath]2^{m-1}+1[/imath] tập hợp trên sẽ là tập con của [imath]B[/imath], nên theo giả thiết quy nạp tồn tại [imath]X=Y \cup Z[/imath].
Từ đó [imath]X \cup \lbrace{ a_{m+1} \rbrace}=(Y \cup \lbrace{ a_{m+1} \rbrace}) \cup (Z \cup \lbrace{ a_{m+1} \rbrace})[/imath] nên tồn tại [imath]3[/imath] tập con [imath]X'=X \cup \lbrace{ a_{m+1} \rbrace},Y'=Y \cup \lbrace{ a_{m+1} \rbrace},Z'=Z \cup \lbrace{ a_{m+1} \rbrace}[/imath] thuộc [imath]2^m+1[/imath] tập con ban đầu thỏa mãn bài toán.
Suy ra đpcm đúng với [imath]n=m+1[/imath]. Theo nguyên lý quy nạp, đpcm đúng với mọi [imath]n \in \mathbb{N}^*[/imath].
Có gì không hiểu thì em hỏi lại nha
Ngoài ra, em tham khảo kiến thức tại
[Lý thuyết] Chuyên đề HSG: Toán rời rạc
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
