Number theoryDifficulty 6.6National olympiadFind the answer
For each positive integer p, let b(p) denote the unique positive integer k such that ∣k−p∣<21. For example, b(6)=2 and b(23)=5. If S=∑p=12007b(p), find the remainder when S is divided by 1000.
A number or a short expression. Spacing and $ signs are ignored.
Solution
1. **Understanding the function b(p)**: - The function b(p) is defined such that b(p)=k where k is the unique positive integer satisfying ∣k−p∣<21. - This implies k−21<p<k+21. - Squaring all parts of the inequality, we get: (k−21)2<p<(k+21)2 - Simplifying the squared terms: k2−k+41<p<k2+k+41 - Since p is an integer, we can ignore the fractional parts: k2−k+1≤p≤k2+k
2. **Counting the number of p values for each k**: - For each k, the number of integers p in the range k2−k+1≤p≤k2+k is: (k2+k)−(k2−k+1)+1=2k - Therefore, there are 2k values of p for which b(p)=k.
3. **Summing b(p) for p from 1 to 2007**: - We need to find the sum S=∑p=12007b(p). - We observe that b(p)=k for 2k values of p. - We need to determine the largest k such that k2+k≤2007: k2+k−2007≤0 - Solving the quadratic equation k2+k−2007=0 using the quadratic formula: k=2−1±1+4⋅2007=2−1±8029 - Approximating 8029≈89.6: k≈2−1+89.6≈44.3 - Thus, the largest integer k is 44.
4. **Calculating the sum S**: - For k=1 to 44, each k contributes 2k⋅k=2k2 to the sum. - The sum of squares of the first 44 integers is: k=1∑442k2=2k=1∑44k2=2⋅644⋅45⋅89=2⋅29370=58740 - For p from 1981 to 2007 (27 values), b(p)=45: 27⋅45=1215 - Adding these contributions: S=58740+1215=59955
5. **Finding the remainder when S is divided by 1000**: - Calculating 59955mod1000: 59955≡955(mod1000)
The final answer is 955.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: NuminaMath-1.5,
licensed Apache-2.0.
Statement and solution reproduced as published; topic and difficulty added by this site.