HMMT 十一月 2018 · THM 赛 · 第 10 题

HMMT November 2018 — THM Round — Problem 10

One million bucks (i.e. one million male deer) are in different cells of a 1000 × 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 ( x , y ) and ( x , y ) satisfy either: 1 1 2 2 x = x and y − y ≡ ± 1 (mod 1000), or x − x ≡ ± 1 (mod 1000) and y = y . 1 2 1 2 1 2 1 2

解析

One million bucks (i.e. one million male deer) are in different cells of a 1000 × 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 ( x , y ) and ( x , y ) satisfy either: 1 1 2 2 x = x and y − y ≡ ± 1 (mod 1000), or x − x ≡ ± 1 (mod 1000) and y = y . 1 2 1 2 1 2 1 2 Proposed by: James Lin Answer: 1200000 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 K honest bucks and B buckaroo pairs, we get B ≥ 3 K . From the dishonest buck condition we get B ≥ 2(1000000 − K ), so we conclude that B ≥ 1200000. To find equality, partition the grid into five √ different parts with side 5, and put honest bucks on every cell in two of the parts.