HMMT 十一月 2017 · GEN 赛 · 第 6 题

HMMT November 2017 — GEN Round — Problem 6

A positive integer n is magical if ⌊√ ⌋ ⌈√ ⌉ ⌈ ⌉ ⌊ ⌋ √ √ n = n , where b·c and d·e represent the floor and ceiling function respectively. Find the number of magical integers between 1 and 10 , 000, inclusive.

解析

A positive integer n is magical if ⌊√ ⌋ ⌈√ ⌉ ⌈ √ ⌉ ⌊ √ ⌋ n = n , where b·c and d·e represent the floor and ceiling function respectively. Find the number of magical integers between 1 and 10 , 000, inclusive. Proposed by: Yuan Yao Answer: 1330 √ √ √ √ First of all, we have b n c = d n e when n is a perfect square and b n c = d n e − 1 otherwise. √ Therefore, in the first case, the original equation holds if and only if n is a perfect square itself, i.e., √ √ √ n is a fourth power. In the second case, we need m = b n c to satisfy the equation b m + 1 c = d m e , 2 which happens if and only if either m or m + 1 is a perfect square k . Therefore, n is magical if and 2 2 2 2 2 2 2 2 2 only if ( k − 1) < n < ( k + 1) for some (positive) integer k . There are ( k + 1) − ( k − 1) = 4 k − 1 integers in this range. The range in the problem statement includes k = 1 , 2 , . . . , 9 and the interval 2 2 (99 , 100 ], so the total number of magical numbers is 9 · (9 + 1) · (18 + 1) 2 2 2 2 2 4(1 + 2 + · · · + 9 ) − 9 + (100 − 99 ) = 4 · + 190 = 1330 . 6