Maths Olympiad Prep

Library / /616 of 740

, 2018

Combinatorics Difficulty 5.3 AIME, harder Prove it United States

Problem:

One million bucks (i.e. one million male deer) are in different cells of a 1000×10001000 \times 1000 grid. The left and right edges of the grid are then glued together, and the top and bottom edges of the grid are glued together, so that the grid forms a doughnut-shaped torus. Furthermore, some of the bucks are honest bucks, who always tell the truth, and the remaining bucks are dishonest bucks, who never tell the truth. Each of the million bucks claims that "at most one of my neighboring bucks is an honest buck." A pair of neighboring bucks is said to be buckaroo if exactly one of them is an honest buck. What is the minimum possible number of buckaroo pairs in the grid?

Note: Two bucks are considered to be neighboring if their cells (x1,y1)\left(x_{1}, y_{1}\right) and (x2,y2)\left(x_{2}, y_{2}\right) satisfy either: x1=x2x_{1}=x_{2} and y1−y2≡±1( mod 1000)y_{1}-y_{2} \equiv \pm 1(\bmod 1000), or x1−x2≡±1( mod 1000)x_{1}-x_{2} \equiv \pm 1(\bmod 1000) and y1=y2y_{1}=y_{2}.

Solution

Solution:

Note that each honest buck has at most one honest neighbor, and each dishonest buck has at least two honest neighbors. The connected components of honest bucks are singles and pairs. Then if there are KK honest bucks and BB buckaroo pairs, we get B≥3KB \geq 3K. From the dishonest buck condition we get B≥2(1000000−K)B \geq 2(1000000-K), so we conclude that B≥1200000B \geq 1200000. To find equality, partition the grid into five different parts with side 5\sqrt{5}, and put honest bucks on every cell in two of the parts.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.