Chủ đề này có 1 trả lời

[tranquocluat_ht]

Cho bảng $A$ kích thước $6 \times 6$ (đã được chia thành 36 ô vuông nhỏ). Ta thực hiện điền các số thuộc tập $\{1,2,3,4\}$ vào các ô của bảng $A$ (ô nào cũng được điền 1 số và các ô khác nhau có thể được điền số giống nhau). Gọi $X_i$ là tập hợp các số trong hàng thứ $i$ và $Y_j$ là tập hợp các số trong cột thứ $j$ với $1 \le i, j \le 6$) (các số xuất hiện nhiều lần trong tập hợp thì chỉ tính 1 lần). Bảng $A$ được gọi là bảng đẹp nếu các tập $X_1,X_2,...,X_6,Y_1,Y_2,...,Y_6$ đôi một phân biệt. Chứng minh rằng $A$ không thể là bảng đẹp.

[Karl Heinrich Marx]

Lời giải:

Giả sử tồn tại bảng đẹp theo như đề bài mô tả, ta xét $1$ bảng đẹp như thế.

 

Đầu tiên ta nhân thấy trong $12$ tập $X_i , Y_i$  thì không có tập rỗng và từ các số từ $1$ đến $4$, có thể lập $15$ tập con khác rỗng ( $ = 2^4-1$),  trong đó có $4$ tập con có $1$ phần tử. Vì vậy trong $12$ tập $X_i , Y_i$ tập sẽ có ít nhất $1$ tập chỉ có $1$ phần tử, và do đó sẽ có $1$ cột hoặc $1$ hàng, trong đó chỉ  điền cùng $1$ số, ta có thể giả sử đó là $1$ hàng toàn số $1$. Ta có thể đổi chỗ các hàng vì vậy có thể xem hàng đầu tiên là hàng gồm toàn số $1$.

 

Ta xét trường hợp ngoài hàng thứ $1$ thì còn $1$ hàng nữa mà trong hàng đó cũng chỉ điền đúng $1$ con số. Điều này không thỏa mãn vì chỉ có $4$ tập hợp chứa $2$ phần tử này ($=2^2$), trong khi đó $6$ cột là $6$ tập khác nhau. Vì vậy ngoài hàng đầu tiên thì không có hàng nào chỉ điền $1$ số cả. Tức là trong $12$ tập $X_i , Y_i$
có duy nhất $1$ tập có 1 phần tử. Như vậy trong $15$  tập con ta loại $3$ tập có $1$ phần tử,  còn lại đó chính là tập hợp các tập $\{ X_1,X_2,...,X_6,Y_1,...,Y_6 \}$.

 

Có $8$ tập hợp chứa số $1$ vì vậy ngoài $6$ cột và hàng đầu tiên ra sẽ có đúng $1$ hàng nữa chứa số $1$, ta có thể xem nó là hàng cuối cùng ( chú ý là nếu đổi chỗ các hàng hay đổi chỗ các cột chẳng ảnh hưởng gì đến cách điền cả). Với $4$ hàng ở giữa chỉ chứa các số $2,3,4$ thì các tập ứng với nó chỉ có thể là $\{ 2,3 \}, \{2,4 \}, \{3,4 \}, \{2,3,4 \}$.

 

Bây giờ ta quan tâm đến cách điền $3$ hàng có tập hợp tương ứng là $\{2,3 \}, \{2,4 \}$ và $\{3,4 \}$. $3$ hàng này mỗi hàng chứa đúng $2$ số. Ta xem như chỉ đang xét một hình chữ nhật $3 \times 6$ thì mỗi cột chứa ít nhất $2 $số khác nhau (vì trong $3$ hàng mỗi số chỉ xuất hiện ở đúng $2$ hàng). Như vậy tập hợp của mỗi cột hình $6 \times 6$ có ít nhất $3$ phần tử ($2$ phần tử ở  cùng $1$ cột trong hình  $3 \times 6$ kết hợp với số $1$ ở trên cùng). Trong khi tập $\{1,2,3,4 \}$  chỉ có $5$ tập con là có ít nhất $3$ phần tử. Điều này mâu thuẫn!

 

Mâu thuẫn này chứng tỏ không tồn tại bảng đẹp thỏa yêu cầu bài toán (đpcm).

Bài viết đã được chỉnh sửa nội dung bởi supermember: 10-11-2014 - 13:01