Câu hỏi 149
Một triệu con hươu đực ("buck") nằm ở các ô khác nhau của một bảng ô vuông $1000 \times 1000$. Sau đó cạnh trái và cạnh phải của bảng được dán lại với nhau, và cạnh trên và cạnh dưới của bảng cũng được dán lại với nhau, để bảng tạo thành một hình xuyến (hình bánh donut). Hơn nữa, một số con hươu là hươu trung thực, luôn nói thật, và những con còn lại là hươu không trung thực, không bao giờ nói thật. Mỗi con trong một triệu con hươu đều khẳng định rằng "nhiều nhất một trong các con hươu kề với tôi là hươu trung thực." Một cặp hươu kề nhau được gọi là cặp "buckaroo" nếu đúng một trong hai con là hươu trung thực. Số cặp buckaroo nhỏ nhất có thể trong bảng là bao nhiêu?
Chú ý: Hai con hươu được coi là kề nhau nếu các ô $\left(x_{1}, y_{1}\right)$ và $\left(x_{2}, y_{2}\right)$ của chúng thỏa mãn: hoặc $x_{1}=x_{2}$ và $y_{1}-y_{2} \equiv \pm 1(\bmod 1000)$, hoặc $x_{1}-x_{2} \equiv \pm 1(\bmod 1000)$ và $y_{1}=y_{2}$.
Chú ý: Hai con hươu được coi là kề nhau nếu các ô $\left(x_{1}, y_{1}\right)$ và $\left(x_{2}, y_{2}\right)$ của chúng thỏa mãn: hoặc $x_{1}=x_{2}$ và $y_{1}-y_{2} \equiv \pm 1(\bmod 1000)$, hoặc $x_{1}-x_{2} \equiv \pm 1(\bmod 1000)$ và $y_{1}=y_{2}$.