Trích:
Nguyên văn bởi huynhcongbang  Ngày thi thứ nhất.
Bài 2. Với $m$ là số nguyên dương, xét bảng ô vuông $m\times 2018$ gồm $m$ hàng, $2018$ cột mà 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 ra một hàng nào đó của bảng rồi điền thêm $0,1$ vào đó để $2018$ ký tự của hàng tạo thành chuỗi $S$ (nếu chuỗi $S$ đã có sẵn trên hàng nào đó rồi thì coi như thỏa mãn). Bảng được gọi là “tối giản” nếu nó đầy đủ và nếu ta bỏ đi bất kỳ hàng nào thì nó không còn đầy đủ nữa. a) Cho $k\le 2018,$ chứng minh rằng tồn tại bảng tối giản ${{2}^{k}}\times 2018$ sao cho có đúng $k$ cột có đủ cả $0$ lẫn $1.$ b) Cho bảng tối giản $m\times 2018$ có đúng $k$ cột có chứa $0,1$, các cột còn lại đều trống. Chứng minh rằng $m\le {{2}^{k}}.$ |
Câu a: Xét bảng $2^k\times k$ (gồm $2^k$ hàng và $k$ cột) mà mỗi hàng chứa một xâu nhị phân có độ dài bằng $k$ khác nhau. Rỏ ràng bảng này chứa tất cả các xâu nhị phân có độ dài bằng $k$. Bổ sung vào bảng này $2018-k$ cột mà mỗi ô không đánh số nào, bảng này thỏa mãn yêu cầu bài toán.
Câu b: Giả sử có bảng tối giản $m\times 2018$ mà $m>2^k$ và có đúng $k$ cột có chứa $0,1$, các cột còn lại đều trống. Xóa đi tất cả các cột trống, ta được bảng $m\times k$ và bảng này tối giản đối với các xâu có độ dài bằng $k$. Với mỗi hàng thuộc bảng này, ta chèn thêm các hàng mà mỗi hàng là một xâu nhị phân có độ dài bằng $k$ được sinh ra từ hàng này, rồi xóa hàng này đi. Cứ làm như thế cho các hàng còn lại. Khi đó ta được bảng mới mà mỗi hàng là một xâu nhị phân có độ dài bằng $k$. Ta xóa đi các hàng để bảng này tối giản ( các hàng giống nhau), do bảng ban đầu tối giản nên đối với mỗi hàng ban đầu bị xóa thì có ít nhất một hàng được sinh ra từ hàng đầu còn lại trong bảng mới. Tức là sau khi tối giản lại thì bảng mới có ít nhất $m$ hàng và bảng này chứa tất cả các xâu nhị phân có độ dài bằng $k$. Do có đúng $2^k$ xâu nhị phân có độ dài bằng $k$ và $m>2^k$ nên trong bảng này có ít nhất hai hàng chứa hai xâu giống nhau. Và điều này trái với giả thiết tối giản. Vậy $m\leq 2^k$.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]