PUMaC 2015 · 个人决赛（B 组） · 第 1 题

PUMaC 2015 — Individual Finals (Division B) — Problem 1

Alice places down n bishops on a 2015 × 2015 chessboard such that no two bishops are attacking each other. (Bishops attack each other if they are on a diagonal.) Her friend Bob notices that he is not able to place down a larger number of bishops such that any two still cannot attack one another. Find, with proof, n . 2

解析

Alice places down n bishops on a 2015 × 2015 chessboard such that no two bishops are attacking each other. (Bishops attack each other if they are on a diagonal.) Her friend Bob notices that he is not able to place down a larger number of bishops such that any two still cannot attack one another. Find, with proof, n . Solution: We claim that the maximum number of bishops that can be placed in this fashion on an n -by- n chessboard is 2( n − 1) when n ≤ 2. First, notice that in any unoccupied squares, no more than two bishops can attack that square, or else by pigeonhole, two bishops can attack one another. Furthermore, a corner square can be attacked by at most one bishop, and there will be at most two unoccupied corner squares. Thus, if there are k bishops, the number of possible attacks is 2 at most 2( n − k ) − 2 Now, each bishop can attack at least n − 1 squares, with equality holding iff the bishop lies on the outer boundary of the chessboard. Thus, if there are k bishops, then we have the inequality: 2 k ( n − 1) ≤ 2( n − k ) − 2 2 2 n − 2 k ≤ n + 1 = 2( n − 1) As desired. Now, note that we may put bishops on (1 , i ) with i = 1 , 2 , . . . n and ( n, j ) with j = 2 , 3 . . . n − 1. There are 2 n − 2 bishops and no two of them can attack each other. So the answer is 2 · 2015 − 2 = 4028 . Author: Xiaoyu Xu, Bill Huang 2