Câu 4. (5,0 điểm) Bảng 21×24 (21 hàng, 24 cột) được chia thành 21×24 ô vuông đơn vị. Người ta muốn tô một số ô vuông đơn vị của bảng bởi một trong các màu: xanh, đỏ, vàng (có thể có vài ô vuông đơn vị không được tô màu) sao cho hai điều kiện (i) và (ii) dưới đây đồng thời xảy ra:

(i) Trong các ô vuông đơn vị cùng hàng với mỗi ô vuông đơn vị được tô màu, có không quá 1 ô khác màu với ô đó;

(ii) Trong các ô vuông đơn vị cùng cột với mỗi ô vuông đơn vị được tô màu, có không quá 1 ô khác màu với ô đó.

a) Gọi $x_1$, $x_2$ theo thứ tự là số hàng, số cột của bảng mà trên mỗi hàng/cột đó có ít nhất 2 ô vuông đơn vị được tô xanh; $d_1$, $d_2$ theo thứ tự là số hàng, số cột của bảng mà trên mỗi hàng/cột đó có ít nhất 2 ô vuông đơn vị được tô đỏ; $v_1$, $v_2$ theo thứ tự là số hàng, số cột của bảng mà trên mỗi hàng/cột đó có ít nhất 2 ô vuông đơn vị được tô vàng. Chứng minh rằng

$$x_1+x_2+d_1+d_2+v_1+v_2\le 45.$$

b) Gọi $x$, $d$, $v$ theo thứ tự là số ô vuông đơn vị được tô bởi các màu xanh, đỏ, vàng và đặt $m=\min \{x,d,v\}$. Tìm giá trị lớn nhất của $m$.

a) (2,0 điểm) Ta gọi một hàng là "xanh" nếu trên đó có ít nhất 2 ô tô xanh. Nếu trên hàng đó có ô tô màu đỏ thì xét điều kiện (i) cho ô màu đỏ này, ta có ngay điều vô lý vì trên hàng đó có nhiều hơn 1 ô xanh là khác màu với nó. Như thế, trên hàng xanh sẽ không có ô đỏ nào, và tương tự cũng không có ô vàng nào. (1,0 điểm)

Định nghĩa tương tự với cột "xanh" và hàng/cột "vàng", "đỏ". Như thế, các hàng xanh, đỏ, vàng là đôi một rời nhau nên $x_1+d_1+v_1\le 21$. Tương tự, ta cũng có $x_2+d_2+v_2\le 24$ và cộng lại thì được $x_1+x_2+d_1+d_2+v_1+v_2\le 21+24=45$. (1,0 điểm)

b) (3,0 điểm) Đặt $X=x_1+x_2$, $D=d_1+d_2$, $V=v_1+v_2$ và $a$ là tổng số hàng/cột còn lại, không thuộc các nhóm trên, gọi là hàng/cột "thường". Ta có $X+D+V+a=45$. (0,5 điểm)

Ta thấy rằng một ô được tô xanh thì có thể thuộc về một hàng xanh, một cột xanh hoặc hàng/cột thường (mỗi hàng/cột thường cũng chỉ chứa không quá 1 ô xanh). Do có $x_1$ hàng xanh, $x_2$ cột xanh nên chúng giao nhau tại $x_1{x}_2$ ô, kéo theo số ô được tô xanh tối đa là $x_1{x}_2+a$. (1,0 điểm)

Theo bất đẳng thức AM-GM, $x\le x_1{x}_2+a\le \frac{(x_1+x_2{)}^2}{4}+a=\frac{X^2}{4}+a$. Không mất tính tổng quát, giả sử $X=\min \{X,D,V\}$ thì $45-a=X+D+V\ge 3X$. Suy ra
$$\frac{X^2}{4}+a\le \frac{(45-a{)}^2}{4\cdot 9}+a=56+\frac{a(a-54)+9}{36}\le 56+\frac{9}{36}=56+\frac{1}{4},$$
đánh giá cuối đúng vì $0\le a\le 45$. (1,0 điểm)

Vì thế nên $m\le x\le \frac{X^2}{4}+a\le 56+\frac{1}{4}$. Giá trị lớn nhất cần tìm là 56.

Ta xét ví dụ xây dựng trong hình bên dưới (theo thứ tự xanh, đỏ, vàng):

(0,5 điểm)

Lưu ý. Các bài toán ở trên đây có thể có nhiều cách giải. Ban giám khảo căn cứ tình hình cụ thể để cho điểm nếu thí sinh làm khác cách giải của hướng dẫn chấm thi.