Problem:
For each integer n≥2, let A(n) be the area of the region in the coordinate plane defined by the inequalities 1≤x<n and 0≤y≤x⌊x⌋, where ⌊x⌋ is the greatest integer not exceeding x. Find the number of values of n with 2≤n≤1000 for which A(n) is an integer.
Solution:
For positive integer k, if 1≤k2≤x<(k+1)2, then x⌊x⌋=kx. The inequalities n≤x<n+1 and 0≤y≤x⌊x⌋ define a trapezoid with height 1 and average of the bases 2(2n+1)k. The area of this trapezoid, which is A(n+ 1) −A(n), is an integer if k is even and a half-integer if k is odd. Hence for even values of k,A(n+1) is an integer if and only if A(n) is an integer, and for odd values of k,A(n+1) is an integer if and only if A(n) is not an integer.
For k≥1, let Ik be the set of the 2k+1 integers n such that k2<n≤(k+1)2. If k is even, the values of A(n) for n∈Ik are either all integers or all non-integers, according to whether A(k2) is or is not an integer. Furthermore, if k is odd, the values of A(n) for n∈Ik alternate between integers and non-integers, beginning with an integer if A(k2) is a non-integer and vice versa. Because A(2) is not an integer, the number of integer values of A(n) for elements of each set Ik can be calculated by considering k modulo 4:k=4j−3,4j−2,4j−1,4j.
Because A((4j−3)2) is an integer, the values of A(n) for n∈I4j−3 alternate between integers and non-integers, beginning and ending with a non-integer. Thus there are 4j−3 integer values of A(n) for n∈I4j−3.
Because A((4j−2)2) is not an integer, there are no integer values of A(n) for n∈I4j−2.
Because A((4j−1)2) is not an integer, the values of A(n) for n∈I4j−1 alternate between integers and non-integers, beginning and ending with an integer. Thus there are 4j integer values of A(n) for n∈I4j−1.
Because A((4j)2) is an integer, all 8j+1 values of A(n) for n∈I4j are integers.
Thus for j≥1, there are 16j−2 integer values of A(n) for (4j−3)2<n≤(4j+1)2. The number of integer values of A(n) for 2≤n≤292 is
j=1∑7(16j−2)=16(27⋅8)−7⋅2=434
There are additionally 29 integer values of A(n) for 292<n≤302, none for 302<n≤312, and 20 for 312<n≤1000, for a total of 434+29+20=483 integer values of A(n).