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

[kienvuhoang]

1.Cho hình chữ nhật có 3x7 ô vuông.Mỗi ô vuông sơn màu trắng hoặc đen.

CMR:luôn tồn tại hình chữ nhật có bốn ô góc sơn cùng màu .

[IHateMath]

Ta đánh số các cột (từ trái sang phải) lần lượt là $1,\ \dots ,\ 7$, các hàng (từ trên xuống dưới) là $1,\ 2,\ 3$. Đặt $S=\{ 1,\ \dots ,\ 7 \}$ và với mỗi $i=1,\ 2,\ 3$, đặt $S_i$ là tập con của $S$ gồm các số $j$ sao cho ô vuông hàng $i$, cột $j$ được sơn đen. 

Nếu có hai số $m,\ n$ mà $|S_m\cap S_n|\geq 2$, thì ta có đ.p.c.m. (có một hình chữ nhật với bốn góc sơn đen).

Bây giờ, giả sử với mọi $a,\ b$ thì $|S_a\cap S_b|\leq 1$. Ta sẽ chứng minh rằng tồn tại $m,\ n$ sao cho 

$|(S\setminus S_m)\cap (S\setminus S_n)|\geq 2.\ (*)$ (tồn tại một hình chữ nhật với bốn góc sơn trắng)

Thật vậy, trước hết điều này tương đương với tồn tại $m,\ n$ sao cho $|S_m\cup S_n|\leq 5$ (do ta có $(S\setminus S_m)\cap (S\setminus S_n)=S\setminus (S_m\cup S_n)\ (**)$). Ta sẽ chứng minh bằng phản chứng. Giả sử với mọi $a,\ b$: $|S_a\cup S_b|\geq 6$. Khi đó với mọi $S_i$ thì $|S_i|\leq 3$. Thật vậy, giả sử $|S_1|\geq 4$ thì

$$|S_1\cup S_2\cup S_3|=|S_1|+|S_2\cup S_3|-|S_1\cap (S_2\cup S_3)|\geq 4+6-2=8\ (***),$$

vô lý. Ta có đ.p.c.m. Bây giờ, ta lại có

$$6\leq |S_1\cup S_2|=|S_1|+|S_2|-|S_1\cap S_2|\leq 6.$$

Dấu bằng phải xảy ra. Điều đó có nghĩa là $S_a\cap S_b=\varnothing$ và $|S_i|=3$. Nhưng điều này dẫn đến vô lý vì khi đó

$$|S_1\cup S_2\cup S_3|=|S_1|+|S_2|+|S_3|=3+3+3=9>7.$$

Mâu thuẫn nói trên cho ta đ.p.c.m. Bài toán được giải quyết.

$(*)$ Kí hiệu $S\setminus A$ ($A\subset S$) chỉ phần bù của $A$ trong $S$ (là tập các phần tử thuộc $S$ mà không thuộc $A$).

$(**)$ Định luật De Morgan.

$(***)$ Nguyên lí bù trừ (hay bao hàm - loại trừ)

Bài viết đã được chỉnh sửa nội dung bởi IHateMath: 21-02-2017 - 23:15