Câu hỏi 161
Cho số nguyên dương $m$ và một bảng hình chữ nhật kích thước $m \times 2018$ gồm $m$ hàng và $2018$ cột. Ta viết $0$ hoặc $1$ vào một số ô của bảng (mỗi ô chỉ một số) và các ô còn lại để trống. Bảng được gọi là *đầy đủ* nếu với mọi dãy nhị phân $S$ độ dài $2018$, ta luôn có thể chọn một hàng của bảng để viết thêm một số chữ số $0$, $1$ sao cho $2018$ số trên hàng đó (giữ nguyên thứ tự) tạo thành dãy $S$ (trong trường hợp bảng đã có một hàng là $S$ thì bảng cũng được coi là đầy đủ). Bảng được gọi là *tối tiểu* nếu nó đầy đủ và nếu bỏ đi bất kì hàng nào của bảng thì bảng không còn đầy đủ nữa.
a. Với $0 \le k \le 2018$, chứng minh rằng tồn tại một bảng tối tiểu kích thước $2^k \times 2018$ có đúng $k$ cột, mỗi cột chứa cả $0$ và $1$ (trên các cột đó có thể có một số ô trống).
b. Cho một bảng tối tiểu kích thước $m \times 2018$ có đúng $k$ cột, mỗi cột chứa cả $0$ và $1$. Chứng minh rằng $m \le 2^k$.
a. Với $0 \le k \le 2018$, chứng minh rằng tồn tại một bảng tối tiểu kích thước $2^k \times 2018$ có đúng $k$ cột, mỗi cột chứa cả $0$ và $1$ (trên các cột đó có thể có một số ô trống).
b. Cho một bảng tối tiểu kích thước $m \times 2018$ có đúng $k$ cột, mỗi cột chứa cả $0$ và $1$. Chứng minh rằng $m \le 2^k$.