Problem:
For distinct positive integers a,b<2012, define f(a,b) to be the number of integers k with 1≤k<2012 such that the remainder when ak divided by 2012 is greater than that of bk divided by 2012. Let S be the minimum value of f(a,b), where a and b range over all pairs of distinct positive integers less than 2012. Determine S.
Solution:
For simplicity, we will define g(n) to be n(mod2012). Note that g(ak)+g(a(2012−k)) is either 0 or 2012 ; it is 0 exactly when 2012 divides ak. This means that for 1≤k≤1005, the number of elements i in {k,2012−k} such that ai (mod2012)>bi(mod2012) is
⎩⎪⎪⎨⎪⎪⎧​021​ if g(ak)=0 or g(ak)=g(bk) if g(bk)=0 and g(ak)î€ =0 otherwise. ​
Let T={1,2,…,1005}. Note that the condition g(ak)=g(bk) is equivalent to g((a− b)k)=0. We will try to choose a,b so as to maximize the number of numbers k in T such that the first of the three cases occurs. From the prime factorization 2012=2⋅2⋅503, the proper divisors of 2012 are 1,2,4,503, and 1006. We shall choose a and a−b to be multiples of some of these numbers. It is not hard to verify that we can choose a to be a multiple of 1006 and a−b to be a multiple of 4 . We will take a=1006 and b=1002.
With this choice of a and b, the second of the three cases (i.e. g(bk)=0 and g(ak)î€ =0 ) never occurs, hence minimizing the number of elements i in T−{1006} such that ai (mod2012)>bi(mod2012). Moreover, g(1006a)=0, meaning that g(1006a)>g(1006b) does not hold. This means that our choice of a and b minimizes f(a,b).
Note that g(1006k)=0 occurs for 502 values in T, and g(1006k)=g(1002k) occurs for 1 value in T. No value in T satisfies both condition. Hence S=1005−502−1=502.
Note: Similarly, we can solve the problem in which 2012 is replaced by any positive integer n≥3. The answer is
⎩⎪⎨⎪⎧​2n​(1−p1​)2n​(1−p1​1​)(1−p2​1​)​ if n=pk for some prime p otherwise, where p1​ and p2​ are the two smallest prime divisors of n​
It is worth noting that the answer depends on no more than two prime divisors of n. Hence it might be interesting to ask the question for a value of n with at least three distinct prime divisors, or for all n.
This problem and solution were suggested by Warut Suksompong.
The problems on this page are the property of the MAA's American Mathematics Competitions