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

[hovutenha]

Cho bảng ô vuông $n\times n$ được tô màu trắng xám trước ví dụ với $n=7$ như sau:

Tức là đầu tiên tô xám các ô ở đường chéo chính từ góc trên bến trái xuống góc dưới bên phải

rồi ở nửa phía trên (giống hình bậc thang) ta cũng tô xám.

Điền số thứ tự $1,2,3,...,n$ cho các hàng từ trên xuống dưới và cho các cột từ trái sang phải và gọi ô ở hàng $i$ cột $j$ là ô $(i,j)$ . Ta sẽ tô vàng các ô màu trắng trên bảng  với điều kiện nếu ô $(i,j)$ được tô vàng thì tất cả các ô ở hàng $j$ và tất cả các ô ở cột $i$ đều không được tô vàng. Tìm số ô được tô vàng lớn nhất có thể.

Bài viết đã được chỉnh sửa nội dung bởi hovutenha: 29-11-2023 - 13:59

[perfectstrong]

Hình này là màu "trắng/xám" hay có màu vàng thế

[chanhquocnghiem]

Cho bảng ô vuông $n\times n$ được tô màu trước như sau:

bảng vuông.png

Điền số thứ tự $1,2,3,...,n$ cho các hàng từ trên xuống dưới và cho các cột từ trái sang phải và gọi ô ở hàng $i$ cột $j$ là ô $(i,j)$ . Ta sẽ tô vàng các ô trên bảng trừ các ô đã có màu với điều kiện nếu ô $(i,j)$ được tô vàng thì tất cả các ô ở hàng $j$ và tất cả các ô ở cột $i$ đều không được tô vàng. Tìm số ô được tô vàng lớn nhất có thể.

Sorry, mình đọc nhầm.
 

Bài viết đã được chỉnh sửa nội dung bởi chanhquocnghiem: 29-11-2023 - 16:00

[hovutenha]

Ta thấy cách tô màu vàng vào $6$ ô $(2,1),(3,2),(4,3),(5,4),(6,5),(7,6)$ thỏa mãn điều kiện đề bài.

Giả sử tồn tại cách tô khác vào $7$ ô mà vẫn thỏa mãn điều kiện đề bài.

$7$ ô đó nằm trong các cột từ $1$ đến $6$, suy ra có ít nhất $2$ ô cùng một cột được tô vàng $\rightarrow$ mâu thuẫn

Vậy số ô được tô vàng lớn nhất có thể là $6$.
 

với $n = 7$ Tô các ô $(4,1);(4,2);(4,3);(5,1);(5,2);(5,3);(6,1);(6,2);(6,3);(7,1);(7,2),(7,3)$ vẫn được ạ

[hovutenha]

• Xét $G=(V,E)$ $V\leftrightarrow i(i=\overline{1,n})$ và một cạnh nối hai đỉnh $i>j$ có nghĩa là ô $(i,j)$ được tô vàng, để ý rằng với $i<j$ thì ô $(i,j)$ được tô xám.

Do đó đây là đồ thị đơn vô hướng.

• Ta sẽ chứng minh rằng  không chứa tam giác tức là không tồn tại 3 đỉnh đôi một nối nhau.

Thật vậy phản chứng rằng vẫn tồn tại tam giác, gọi 3 đỉnh được nối là $x>y>z$ khi đó các ô được tô vàng lần lượt là ô $(x,y),(x,z),(y,z)$

• Để ý điều kiện đề bài là nếu ô $(i,j)$ được tô vàng thì tất cả các ô ở hàng $j$ và cột $i$ đều không được tô vàng và ở trên ta thấy ô $(x,y),(y,z)$ đều được tô vàng tức có mâu thuẫn ở đây suy ra giả sử phản chứng sai. Suy ra rằng $G$ không chứa tam giác.
• Áp dụng định lý Mantel-Turan ta có: $\left | E \right |\leq \left \lfloor \frac{n}{2} \right \rfloor\left \lceil \frac{n}{2} \right \rceil$
• Đễ dàng chỉ ra dấu bằng nên bài toán được giải quyết.

Vậy số ô tô vàng lớn nhất là $\left \lfloor \frac{n}{2} \right \rfloor\left \lceil \frac{n}{2} \right \rceil$

 

ps: Đây là bài mình tự nghĩ ra nên có khi còn khá dễ

Bài viết đã được chỉnh sửa nội dung bởi hovutenha: 30-11-2023 - 22:54