HMMT 二月 2002 · 冲刺赛 · 第 41 题

HMMT February 2002 — Guts Round — Problem 41

[9] For any integer n , define b n c as the greatest integer less than or equal to n . For any positive integer n , let ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ n n n f ( n ) = b n c + + + · · · + . 2 3 n For how many values of n, 1 ≤ n ≤ 100, is f ( n ) odd?

解析

For any integer n , define b n c as the greatest integer less than or equal to n . For any positive integer n , let ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ n n n f ( n ) = b n c + + + · · · + . 2 3 n For how many values of n, 1 ≤ n ≤ 100, is f ( n ) odd? Solution: 55 Notice that, for fixed a , b n/a c counts the number of integers b ∈ { 1 , 2 , . . . , n } which are divisible by a ; hence, f ( n ) counts the number of pairs ( a, b ) , a, b ∈ { 1 , 2 , . . . , n } with b divisible by a . For any fixed b , the number of such pairs is d ( b ) (the number of divisors of b ), so the total number of pairs f ( n ) equals d (1)+ d (2)+ · · · + d ( n ). But d ( b ) is odd precisely when b is a square, so f ( n ) is odd precisely when there are an odd num- ber of squares in { 1 , 2 , . . . , n } . This happens for 1 ≤ n < 4; 9 ≤ n < 16; . . . ; 81 ≤ n < 100. Adding these up gives 55 values of n . 10