Câu hỏi 100
Một lưới gồm $n\times n$ điểm, với $n$ là số nguyên dương. Tại một số điểm có đặt lính gác. Mỗi lính gác chọn hai hướng vuông góc nhau trong các hướng dọc theo hàng và cột của lưới, rồi quan sát mọi điểm nằm theo hai hướng đã chọn. Mỗi lính gác cũng quan sát điểm mình đứng. Tùy theo các hướng đã chọn, lính gác ở biên có thể nhìn ra phía không có điểm nào.
Chẳng hạn, trong hình dưới với năm lính gác trên lưới $4\times4$, các lính gác tại $A,B,C,D,E$ lần lượt quan sát $1,3,4,5,7$ điểm. Mỗi điểm $D,E$ được một lính gác quan sát, điểm $C$ được hai lính gác quan sát, còn mỗi điểm $A,B,F$ được ba lính gác quan sát.
Phần a. Chứng minh rằng có thể đặt mười hai lính gác trên lưới $4\times4$ sao cho mỗi điểm của lưới được nhiều nhất hai lính gác quan sát.
Phần b. Gọi $S(n)$ là số lính gác lớn nhất có thể đặt trên lưới $n\times n$ sao cho mỗi điểm của lưới được nhiều nhất hai lính gác quan sát. Chứng minh rằng $3n\le S(n)\le4n$ với mọi $n\ge3$.
Chẳng hạn, trong hình dưới với năm lính gác trên lưới $4\times4$, các lính gác tại $A,B,C,D,E$ lần lượt quan sát $1,3,4,5,7$ điểm. Mỗi điểm $D,E$ được một lính gác quan sát, điểm $C$ được hai lính gác quan sát, còn mỗi điểm $A,B,F$ được ba lính gác quan sát.
Phần a. Chứng minh rằng có thể đặt mười hai lính gác trên lưới $4\times4$ sao cho mỗi điểm của lưới được nhiều nhất hai lính gác quan sát.
Phần b. Gọi $S(n)$ là số lính gác lớn nhất có thể đặt trên lưới $n\times n$ sao cho mỗi điểm của lưới được nhiều nhất hai lính gác quan sát. Chứng minh rằng $3n\le S(n)\le4n$ với mọi $n\ge3$.