Number theoryDifficulty 7.1National olympiad, round 2Find the answer
Given a prime p, let d(a,b) be the number of integers c such that 1≤c<p, and the remainders when ac and bc are divided by p are both at most 3p. Determine the maximum value of a=1∑p−1b=1∑p−1d(a,b)(xa+1)(xb+1)−a=1∑p−1b=1∑p−1d(a,b)xaxb over all (p−1)-tuples (x1,x2,…,xp−1) of real numbers.
[i]Brian Hamrick.[/i]
A number or a short expression. Spacing and $ signs are ignored.
Solution
1. **Define the function d(a,b):** Given a prime p, let d(a,b) be the number of integers c such that 1≤c<p, and the remainders when ac and bc are divided by p are both at most 3p.
2. Express the given expression in terms of vectors: Let va be a vector in Rp−1 such that the c-th term of va is: va(c)={xa+10if the remainder of ac is at most 3p,otherwise. Similarly, let ua be a vector in Rp−1 such that the c-th term of ua is: ua(c)={xa0if the remainder of ac is at most 3p,otherwise.
3. Rewrite the sums using these vectors: The given expression can be rewritten as: a=1∑p−1b=1∑p−1d(a,b)(xa+1)(xb+1)=a=1∑p−1b=1∑p−1⟨va,vb⟩ and a=1∑p−1b=1∑p−1d(a,b)xaxb=a=1∑p−1b=1∑p−1⟨ua,ub⟩.
4. Apply the triangle inequality: By the triangle inequality for vectors, we have: ∥va∥≤∥ua∥+∥1∥, where 1 is the vector with all entries equal to 1. Since ∥1∥=p−1, we get: a=1∑p−1b=1∑p−1⟨va,vb⟩≤a=1∑p−1b=1∑p−1⟨ua,ub⟩+p−1.
5. Determine the maximum value: The maximum value of the given expression is achieved when the difference between the two square roots is maximized. This occurs when: a=1∑p−1b=1∑p−1⟨va,vb⟩−a=1∑p−1b=1∑p−1⟨ua,ub⟩=p−1.
The final answer is p−1.
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.