Câu hỏi 2
Với $m$ là số nguyên dương, xét bảng ô vuông $m\times2018$ gồm $m$ hàng, 2018 cột, trong đó có một vài ô trống, còn một vài ô được đánh số 0 hoặc 1. Bảng được gọi là “đầy đủ” nếu với bất kỳ chuỗi nhị phân $S$ có 2018 ký tự nào, ta đều có thể chọn một hàng rồi điền thêm 0, 1 vào các ô trống để 2018 ký tự của hàng tạo thành $S$ (nếu $S$ đã có sẵn trên một hàng thì cũng coi là thỏa mãn). Bảng được gọi là “tối giản” nếu nó đầy đủ và bỏ đi bất kỳ hàng nào thì không còn đầy đủ.
(a) Với $0\le k\le2018$, chứng minh tồn tại bảng tối giản $2^k\times2018$ có đúng $k$ cột chứa đủ cả 0 lẫn 1.
(b) Cho bảng tối giản $m\times2018$ có đúng $k$ cột chứa cả 0 lẫn 1. Chứng minh $m\le2^k$.
Một chuỗi nhị phân độ dài 2018 có dạng $x_1x_2\cdots x_{2018}$, trong đó $x_i\in\{0,1\}$ với mọi $i$.
(a) Với $0\le k\le2018$, chứng minh tồn tại bảng tối giản $2^k\times2018$ có đúng $k$ cột chứa đủ cả 0 lẫn 1.
(b) Cho bảng tối giản $m\times2018$ có đúng $k$ cột chứa cả 0 lẫn 1. Chứng minh $m\le2^k$.
Một chuỗi nhị phân độ dài 2018 có dạng $x_1x_2\cdots x_{2018}$, trong đó $x_i\in\{0,1\}$ với mọi $i$.