PUMaC 2015 · 个人决赛（A 组） · 第 1 题
PUMaC 2015 — Individual Finals (Division A) — Problem 1
题目详情
- Alice is placing bishops on a 2015-by-2015 chessboard such that no two can attack one another. (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. ∏ α i If there are p , with α > 0 and p > 0 prime for all i , ways Alice could have placed her i i i ∑ bishops, find p + α . i i
解析
- 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.) (a) Find, with proof, the maximum possible value of n . (b) For this maximal n , find, with proof, the number of ways she could place her bishops on the chessboard. 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). 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 since we wish to maximize the number of bishops, there will be at most two unoccupied corner squares. Thus, 2 if there are k bishops, the number of possible attacks is 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 equality holds iff each bishop can attack exactly ( n − 1) squares, which means all the bishops must be on the outer boundary of the chessboard. We can divide these square into groups: for any i , the squares (1 , i ) , ( i, 1) , (2015 , 2015 − i +1) , (2015 − i +1 , 2015) form a group. Clearly, at most half of the squares in each group can be occupied, so to achieve equality, half the squares in each group must be occupied. It is easy to see that there is exactly two ways to select the occupied squares within each group. Furthermore, the bishops in a group cannot attack those in another group. Thus, the selections are independent. 2015 Since there are 2015 groups, one for each 1 ≤ i ≤ 2015, there are a total of 2 ways to place the bishops, so our answer is 2 + 2015 = 2017 . Author: Bill Huang