PUMaC 2017 · 团队赛 · 第 9 题
PUMaC 2017 — Team Round — Problem 9
题目详情
- (6) The set 2 { ( x, y ) ∈ R | b x + y c · d x + y e = ( b x c + d y e ) ( d x e + b y c ) , 0 ≤ x, y ≤ 100 } can be thought of as a collection of line segments in the plane. If the total length of those line √ segments is a + b c for c squarefree, find a + b + c . ( b z c is the greatest integer less than or equal to z , and d z e is the least integer greater than or equal to z , for z ∈ R .) 1943
解析
- Let n = 100. First, we will figure out what solutions to b x + y c·d x + y e = ( b x c + d y e )( d x e + b y c ) 2 look like in R . Let { z } = z − b z c . Call a = b x c , b = b y c . Case 1 : { x } 6 = 0 6 = { y } 2 In this case, d x e = a + 1 and d y e = b + 1, so the right hand side becomes ( a + b + 1) . The multiplicands on the left differ by at most one and are in the range [ a + b, a + b + 2], so they must both be a + b + 1; this means that x + y = a + b + 1, i.e. { x } + { y } = 1, or x + y ∈ Z . Case 2 a : { x } = 0 6 = { y } In this case, d x e = a and d y e = b + 1, so the right hand side becomes ( a + b )( a + b + 1). The multiplicands on the left differ by at most one and are in the range [ a + b, a + b + 2], so they must be a + b and a + b + 1. Therefore, any y ∈ R is valid. Case 2 b : { x } 6 = 0 = { y } By symmetry with Case 2 a , any x ∈ R is valid. Note that the case when { x } = 0 = { y } consists of isolated points, and so does not contribute any added length. 2 In the subset of R consisting of points ( x, y ) with 0 ≤ x, y ≤ n , the solutions from Case 1 consist of diagonal segments satisfying x + y = k for integers 1 ≤ k ≤ 2 n − 1 (minus some isolated points that do not affect the length). These have total length ( ) √ √ √ n ( n − 1) 2 2(1 + 2 + · · · + ( n − 1) + n + ( n − 1) + · · · + 2 + 1) = 2 2 · + n = n 2 . 2 3 The solutions from Cases 2 a and 2 b consist of ( n + 1) vertical segments and ( n + 1) horizontal segments, respectively, each of which has length n . The total length of these segments is 2 n ( n + 1), so the final length is √ √ 2 2 n ( n + 1) + n 2 = 20200 + 10000 2 , which gives an answer of 30202 . Problem written by Zack Stier 232 1943 232 8 87