Maths Olympiad Prep

Library / /353 of 520

Number theory Difficulty 7.1 National olympiad, round 2 Find the answer

Given a prime pp, let d(a,b)d(a,b) be the number of integers cc such that 1c<p1 \leq c < p, and the remainders when acac and bcbc are divided by pp are both at most p3\frac{p}{3}. Determine the maximum value of a=1p1b=1p1d(a,b)(xa+1)(xb+1)a=1p1b=1p1d(a,b)xaxb\sqrt{\sum_{a=1}^{p-1}\sum_{b=1}^{p-1}d(a,b)(x_a + 1)(x_b + 1)} - \sqrt{\sum_{a=1}^{p-1}\sum_{b=1}^{p-1}d(a,b)x_ax_b} over all (p1)(p-1)-tuples (x1,x2,,xp1)(x_1,x_2,\ldots,x_{p-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) d(a, b) :**
Given a prime p p , let d(a,b) d(a, b) be the number of integers c c such that 1c<p 1 \leq c < p , and the remainders when ac ac and bc bc are divided by p p are both at most p3 \frac{p}{3} .

2. Express the given expression in terms of vectors:
Let va v_a be a vector in Rp1 \mathbb{R}^{p-1} such that the c c -th term of va v_a is:
va(c)={xa+1if the remainder of ac is at most p3,0otherwise. v_a(c) = \begin{cases} x_a + 1 & \text{if the remainder of } ac \text{ is at most } \frac{p}{3}, \\ 0 & \text{otherwise}. \end{cases}
Similarly, let ua u_a be a vector in Rp1 \mathbb{R}^{p-1} such that the c c -th term of ua u_a is:
ua(c)={xaif the remainder of ac is at most p3,0otherwise. u_a(c) = \begin{cases} x_a & \text{if the remainder of } ac \text{ is at most } \frac{p}{3}, \\ 0 & \text{otherwise}. \end{cases}

3. Rewrite the sums using these vectors:
The given expression can be rewritten as:
a=1p1b=1p1d(a,b)(xa+1)(xb+1)=a=1p1b=1p1va,vb \sqrt{\sum_{a=1}^{p-1}\sum_{b=1}^{p-1} d(a, b) (x_a + 1)(x_b + 1)} = \sqrt{\sum_{a=1}^{p-1} \sum_{b=1}^{p-1} \langle v_a, v_b \rangle}
and
a=1p1b=1p1d(a,b)xaxb=a=1p1b=1p1ua,ub. \sqrt{\sum_{a=1}^{p-1}\sum_{b=1}^{p-1} d(a, b) x_a x_b} = \sqrt{\sum_{a=1}^{p-1} \sum_{b=1}^{p-1} \langle u_a, u_b \rangle}.

4. Apply the triangle inequality:
By the triangle inequality for vectors, we have:
vaua+1, \| v_a \| \leq \| u_a \| + \| \mathbf{1} \|,
where 1 \mathbf{1} is the vector with all entries equal to 1. Since 1=p1 \| \mathbf{1} \| = \sqrt{p-1} , we get:
a=1p1b=1p1va,vba=1p1b=1p1ua,ub+p1. \sqrt{\sum_{a=1}^{p-1} \sum_{b=1}^{p-1} \langle v_a, v_b \rangle} \leq \sqrt{\sum_{a=1}^{p-1} \sum_{b=1}^{p-1} \langle u_a, u_b \rangle} + \sqrt{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=1p1b=1p1va,vba=1p1b=1p1ua,ub=p1. \sqrt{\sum_{a=1}^{p-1} \sum_{b=1}^{p-1} \langle v_a, v_b \rangle} - \sqrt{\sum_{a=1}^{p-1} \sum_{b=1}^{p-1} \langle u_a, u_b \rangle} = \sqrt{p-1}.

The final answer is p1\boxed{\sqrt{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.