1 reply to this topic

[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).

Edited by supermember, 10-11-2014 - 13:01.