HMMT 二月 2010 · 冲刺赛 · 第 35 题
HMMT February 2010 — Guts Round — Problem 35
题目详情
- [ 25 ] Call an positive integer almost-square if it can be written as a · b , where a and b are integers and 4 a ≤ b ≤ a . How many almost-square positive integers are less than or equal to 1000000? Your score 3 | A − C | will be equal to 25 − 65 . min( A,C )
解析
- [ 25 ] Call an positive integer almost-square if it can be written as a · b , where a and b are integers and 4 a ≤ b ≤ a . How many almost-square positive integers are less than or equal to 1000000? Your score 3 | A − C | will be equal to 25 − 65 . min( A,C ) Answer: 130348 To get a good estimate for the number of almost-square integers, note that any 4 number of the form a · b , with b ≤ a , will be by definition almost-square. Let’s assume that it’s 3 relatively unlikely that a number is almost-square in more than one way. Then the number of almost- square numbers less than n will be approximately √ √ 4 a n n 3 ∑ ∑ ∑ √ ( √ ) 1 1 1 = a = n n + 1 , 3 6 a =1 a =1 b = a n n which is about . So, will be a fairly good estimate for the number of almost-square numbers less 6 6 than n , making 160000 a reasonable guess. √ a We can do better, though. For example, we summed all the way up to n , but we are really 3 √ n overcounting here because when a is close to n , a · b will be less than n only when b ≤ , as opposed a 4 a to b ≤ . So we should really be taking the sum 3 7 See http://en.wikipedia.org/wiki/Chernoff_bound . Guts Round √ √ 3 n 4 a n n 4 3 a ∑ ∑ ∑ ∑ 1 + 1 √ a =1 b = a 3 n b = a a = 4 √ √ 3 n n 4 ( ) ∑ ∑ a n = + − a 3 a √ a =1 3 n a = 4 ( ) √ ( ) √ 1 3 n 3 n n 3 n ≈ + n log( n ) − log( ) − − 6 4 4 2 8 n log(4) − log(3) n = + n − 8 2 8 log(4) − log(3) = n . 2 n n In the process of taking the sum, we saw that we had something between and , so we could also 8 6 guess something between 166000 and 125000, which would give us about 145000, an even better answer. log(4) − log(3) If we actually calculate , we see that it’s about 0 . 14384, so 143840 would be the best guess 2 if we were to use this strategy. In reality, we would want to round down a bit in both cases, since we are overcounting (because numbers could be square-free in multiple ways), so we should probably answer something like 140000. A final refinement to our calculation (and perhaps easier than the previous one), is to assume that the products a · b that we consider are randomly distributed between 1 and n , and to compute the expected number of distinct numbers we end up with. This is the same type of problem as number 31 on this contest, and we compute that if we randomly distribute k numbers between 1 and n then we expect ( ) ( ) k log(4) − log(3) 1 to end up with n 1 − 1 − distinct numbers. When k = n , we get that this equals n 2 log(4) − log(3) (( ) ) n ( ) √ 2 1 log(3) − log(4) n 1 − 1 − = n 1 − e n ( ) √ 3 = n 1 − 4 ( ) √ 3 = n 1 − 2 ≈ 0 . 134 n, Giving us an answer of 134000, which is very close to the correct answer. The actual answer was found by computer, using the following C++ program: #include <stdio.h> using namespace std; bool isAlmostSquare(int n){ for(int k=1;kk<=n;k++) if(n%k==0 && 3(n/k) <= 4*k) return true; return false; } Guts Round int main(){ int c = 0; for(int n=1;n<=1000000;n++) if(isAlmostSquare(n)) c++; printf("%d\n",c); return 0; }