Một khu vườn trồng cam có dạng bảng ô vuông kích thước $2025\times 2026$ được chia thành các ô vuông đơn vị. Để chiếu sáng khu vườn về ban đêm, ta đặt các bóng điện ở các đỉnh của các ô vuông đơn vị, mỗi đỉnh đặt không quá một bóng điện. Biết rằng mỗi bóng điện chỉ có thể chiếu sáng toàn bộ các ô vuông đơn vị có chung đỉnh có đặt bóng điện đó.
a) Hỏi cần dùng ít nhất bao nhiêu bóng điện để có thể chiếu sáng toàn bộ khu vườn, trong trường hợp các bóng điện hoạt động bình thường?
b) Hỏi cần dùng ít nhất bao nhiêu bóng điện để có thể chiếu sáng toàn bộ khu vườn, kể cả trong trường hợp không may có một bóng điện bất kì bị cháy (mà ta không biết cụ thể là bóng nào)?
c) Trong quá trình trồng cam, chủ vườn quyết định mở rộng khu vườn thành bảng ô vuông có kích thước $2026\times 2026$. Hỏi cần dùng ít nhất bao nhiêu bóng điện để điều kiện ở câu b) vẫn được thỏa mãn?

Đầu tiên ta có bổ đề sau:
Bổ đề: Trong một bảng $r\times s$ gồm các số $0,1$, giả sử mọi bảng con $2\times 2$ gồm hai hàng liên tiếp và hai cột liên tiếp đều có tổng ít nhất bằng 2. Khi đó số các số 1 trong bảng không nhỏ hơn
$$\min \left\{s\lfloor \frac{r}{2}\rfloor ,r\lfloor \frac{s}{2}\rfloor \right\}.$$
Chứng minh. Trước hết, xét một bảng $2\times s$. Với $1\le j\le s$, gọi $c_j$ là tổng các phần tử của cột thứ $j$. Theo giả thiết, ta có $c_j+c_{j+1}\ge 2$ với mọi $1\le j\le s-1$.
Ghép các cột thành các cặp liên tiếp $(1,2),(3,4),\dots$ ta được $$\sum _{j=1}^s{c}_j\ge 2\lfloor \frac{s}{2}\rfloor .$$
Do đó một bảng $2\times s$ như trên có ít nhất $2\lfloor s/2\rfloor$ số 1.
Trong trường hợp $s$ lẻ, giả sử $s=2k+1$ và bảng có đúng $2k$ số 1. Khi đó
$$(c_1+c_2)+(c_3+c_4)+\cdots +(c_{2k-1}+c_{2k})+c_{2k+1}=2k.$$
Mỗi tổng trong $k$ dấu ngoặc đều không nhỏ hơn 2, nên bắt buộc
$$c_{2k+1}=0,c_{2i-1}+c_{2i}=2$$
với mọi $1\le i\le k$. Từ $c_{2k}+c_{2k+1}\ge 2$ và $c_{2k+1}=0$, suy ra $c_{2k}=2$, do đó $c_{2k-1}=0$. Do đó
$$(c_1,c_2,\dots ,c_{2k+1})=(0,2,0,2,\dots ,0,2,0).$$
Vì mỗi cột chẵn chứa hai số 1, còn mỗi cột lẻ chỉ chứa các số 0, nên mỗi hàng của bảng có đúng $k$ số 1.
Bây giờ trở lại bảng $r\times s$ ban đầu. Nếu $r$ chẵn, ta ghép các hàng thành các cặp liên tiếp. Mỗi cặp hàng tạo thành một bảng $2\times s$, nên chứa ít nhất $2\lfloor s/2\rfloor$ số 1. Vì có $r/2$ cặp hàng, toàn bảng có ít nhất
$$\frac{r}{2}\cdot 2\lfloor \frac{s}{2}\rfloor =r\lfloor \frac{s}{2}\rfloor$$
số 1. Tương tự, nếu $s$ chẵn thì ghép các cột thành từng cặp liên tiếp, ta được ít nhất $s\lfloor \frac{r}{2}\rfloor$ số 1.
Như vậy, bổ đề đúng nếu $r$ hoặc $s$ chẵn.
Ta chỉ còn xét trường hợp $r=2h+1$, $s=2k+1$.
Không mất tính tổng quát, giả sử $h\le k$. Khi đó $\min \{(2k+1)h,(2h+1)k\}=(2k+1)h$.
Ta sẽ chứng minh bằng quy nạp theo $h$ rằng bảng có ít nhất $h(2k+1)$ số 1.
Với $h=0$, khẳng định hiển nhiên. Giả sử $h\ge 1$ và khẳng định đã đúng với $h-1$.
Gọi $t$ là số các số 1 trên hàng đầu tiên.
Nếu $t\ge h$, ta bỏ hàng đầu tiên. Phần còn lại là một bảng $2h\times (2k+1)$. Theo trường hợp số hàng chẵn đã chứng minh, bảng này có ít nhất $2h\lfloor \frac{2k+1}{2}\rfloor =2hk$ số 1.
Vì thế bảng ban đầu có ít nhất $2hk+h=h(2k+1)$ số 1.
Nếu $t\le h-1$, xét bảng $2\times (2k+1)$ tạo bởi hai hàng đầu tiên.
Theo kết quả ở đầu chứng minh, hai hàng này có ít nhất $2k$ số 1.
Nếu chúng có đúng $2k$ số 1, thì theo trường hợp đầu bảng đã xét, mỗi hàng phải có đúng $k$ số 1. Đặc biệt, hàng đầu tiên có đúng $k$ số 1, mâu thuẫn với $t\le h-1<k$ do $h\le k$. Vì vậy, hai hàng đầu tiên phải chứa ít nhất $2k+1$ số 1.
Bỏ hai hàng đầu tiên, ta còn lại một bảng
$$(2h-1)\times (2k+1)=(2(h-1)+1)\times (2k+1).$$
Vì $h-1\le k$, theo giả thiết quy nạp, bảng còn lại có ít nhất $(h-1)(2k+1)$ số 1. Do đó toàn bảng có ít nhất $(2k+1)+(h-1)(2k+1)=h(2k+1)$ số 1.
Cuối cùng, ta chứng minh cận dưới này đạt được. Nếu điền số 1 vào toàn bộ các vị trí thuộc các hàng có chỉ số chẵn và điền số 0 vào các vị trí còn lại, thì mỗi cặp hàng liên tiếp chứa đúng một hàng toàn số 1. Vì vậy, mỗi bảng con $2\times 2$ gồm hai hàng liên tiếp và hai cột liên tiếp có đúng hai số 1. Tổng số các số 1 trong cách điền này là $s\lfloor \frac{r}{2}\rfloor$.
Tương tự, nếu điền số 1 vào toàn bộ các cột có chỉ số chẵn và điền số 0 vào các vị trí còn lại, ta thu được một bảng thỏa mãn giả thiết và có $r\lfloor \frac{s}{2}\rfloor$ số 1. Chọn cách điền tương ứng với số nhỏ hơn trong hai số trên, ta thấy cận dưới đạt được. Vậy số các số 1 ít nhất là
$$\min \left\{s\lfloor \frac{r}{2}\rfloor ,r\lfloor \frac{s}{2}\rfloor \right\}.$$

Trở lại bài toán ban đầu:
Một khu vườn gồm $m\times n$ ô vuông đơn vị có $(m+1)\times (n+1)$ đỉnh. Ta xem các đỉnh này như một bảng gồm các số 0, 1, số 1 biểu thị đỉnh có đặt bóng điện, còn số 0 biểu thị đỉnh không đặt bóng điện. Khi đó bốn đỉnh của mỗi ô vuông đơn vị tạo thành một bảng con $2\times 2$ gồm hai hàng liên tiếp, hai cột liên tiếp.
a) Khu vườn có $2025\times 2026$ ô vuông đơn vị.
Xét các ô vuông nằm trên các hàng $1,3,5,\dots ,2025$ và các cột $1,3,5,\dots ,2025$, có tất cả
$$1013\cdot 1013=1013^2$$
ô vuông như vậy. Hai ô bất kỳ trong số này không có đỉnh chung. Vì mỗi ô phải có ít nhất một đỉnh được đặt bóng điện, nên các bóng điện chiếu sáng các ô trên phải đôi một khác nhau.
Do đó cần ít nhất $1013^2$ bóng điện.
Ta chứng minh cận dưới này đạt được. Đánh số các hàng đỉnh từ 1 đến 2026 và các cột đỉnh từ 1 đến 2027. Đặt bóng tại tất cả các đỉnh là giao điểm của một hàng đỉnh chẵn và một cột đỉnh chẵn.
Trong hai hàng đỉnh liên tiếp có đúng một hàng chẵn, và trong hai cột đỉnh liên tiếp có đúng một cột chẵn nên mỗi ô vuông đơn vị có đúng một đỉnh được đặt bóng điện, nên toàn bộ khu vườn được chiếu sáng. Số hàng đỉnh chẵn và số cột đỉnh chẵn bằng 1013, nên số bóng điện được dùng là $1013^2$.
Vậy số bóng điện ít nhất cần dùng là $1013^2$.
b) Để khu vườn vẫn được chiếu sáng khi một bóng điện bất kỳ bị cháy, mỗi ô vuông đơn vị phải có ít nhất hai đỉnh được đặt bóng điện. Thật vậy, nếu một ô chỉ có đúng một bóng điện thì khi bóng điện đó bị cháy, ô ấy sẽ không còn được chiếu sáng. Ngược lại, nếu mỗi ô có ít nhất hai bóng điện thì sau khi một bóng bất kỳ bị cháy, mỗi ô vẫn còn ít nhất một bóng hoạt động.
Bảng các đỉnh của khu vườn có kích thước $2026\times 2027$.
Điều kiện trên tương đương với việc mọi bảng con $2\times 2$ gồm hai hàng liên tiếp và hai cột liên tiếp đều có tổng ít nhất bằng 2.
Áp dụng bổ đề với $r=2026$ và $s=2027$, số bóng điện không nhỏ hơn
$$\min \left\{2027\lfloor \frac{2026}{2}\rfloor ,2026\lfloor \frac{2027}{2}\rfloor \right\}=2026\cdot 1013=2\cdot 1013^2$$
Theo trường hợp dấu bằng trong bổ đề, cận này đạt được bằng cách đặt bóng điện tại toàn bộ các đỉnh thuộc các cột đỉnh có chỉ số chẵn.
Vậy số bóng điện ít nhất cần dùng là $2\cdot 1013^2$.
c) Khi mở rộng khu vườn thành bảng $2026\times 2026$, bảng các đỉnh có kích thước $2027\times 2027$.
Tương tự câu trên và áp dụng bổ đề với $r=s=2027$, số bóng điện không nhỏ hơn
$$\min \left\{2027\lfloor \frac{2027}{2}\rfloor ,2027\lfloor \frac{2027}{2}\rfloor \right\}=2027\cdot 1013.$$
Theo trường hợp dấu bằng trong bổ đề, cận này đạt được bằng cách đặt bóng điện tại toàn bộ các đỉnh thuộc các hàng đỉnh có chỉ số chẵn hoặc toàn bộ các đỉnh thuộc các cột đỉnh có chỉ số chẵn.
Vậy số bóng điện ít nhất cần dùng là $2027\cdot 1013$.