Given positive integers $k,n$ and a real number $\ell$, where $k,n \geq 1$. Given are also pairwise different positive real numbers $a_1,a_2,\ldots, a_k$. Let $S = \{a_1,a_2,\ldots,a_k, -a_1, -a_2,\ldots, -a_k\}$. Let $A$ be the number of solutions of the equation $$x_1 + x_2 + \ldots + x_{2n} = 0,$$where $x_1,x_2,\ldots, x_{2n} \in S$. Let $B$ be the number of solutions of the equation $$x_1 + x_2 + \ldots + x_{2n} = \ell,$$where $x_1,x_2,\ldots,x_{2n} \in S$. Prove that $A \geq B$. Solutions of an equation with only difference in the permutation are different.
Problem
Source: Polish Math Olympiad 2023 2nd stage P3
Tags: equations, number of solutions, algebra, linear equation
Tintarn
10.02.2023 20:39
By direct computation,
\[A=\int_0^1 \left(\sum_{s \in S} e^{2\pi is\alpha }\right)^{2n}d\alpha\]and
\[B=\int_0^1 \left(\sum_{s \in S} e^{2\pi is\alpha }\right)^{2n} e^{-2\pi i\ell\alpha} d\alpha\]and the claim follows from the triangle inequality, using that $\sum_{s \in S} e^{2\pi is\alpha}=2\sum_{j=1}^k \cos(2\pi a_j)$ is real so that the integrand is nonnegative (because of the even exponent).
R8kt
11.02.2023 18:48
Does there exist a combinatoric solution?
China_BW
15.02.2023 14:06
R8kt wrote: Does there exist a combinatoric solution? I think there probably have one, but I haven't found it yet www.
Hanser-Ling
26.02.2023 15:07
Tintarn wrote:
By direct computation,
\[A=\int_0^1 \left(\sum_{s \in S} e^{2\pi is\alpha }\right)^{2n}d\alpha\]and
\[B=\int_0^1 \left(\sum_{s \in S} e^{2\pi is\alpha }\right)^{2n} e^{-2\pi i\ell\alpha} d\alpha\]and the claim follows from the triangle inequality, using that $\sum_{s \in S} e^{2\pi is\alpha}=2\sum_{j=1}^k \cos(2\pi a_j)$ is real so that the integrand is nonnegative (because of the even exponent).
Shift! How did you come up with the idea?
Tintarn
27.02.2023 14:11
Hanser-Ling wrote: Shift! How did you come up with the idea? To be honest, I have just seen a lot of similar things before. But if you want to read more about this kind of method, you might want to google Fourier Analysis/Fourier series which is essentially the theory behind this method. Another good keyword might be to check out the Hardy-Littlewood Circle Method which is a powerful analytic method to count solutions to diophantine equations, based on exactly this type of identity (it is e.g. what the proof of the Ternary Goldbach Problem was based on).
MR_D33R
13.03.2023 16:12
Tintarn wrote:
By direct computation,
\[A=\int_0^1 \left(\sum_{s \in S} e^{2\pi is\alpha }\right)^{2n}d\alpha\]and
\[B=\int_0^1 \left(\sum_{s \in S} e^{2\pi is\alpha }\right)^{2n} e^{-2\pi i\ell\alpha} d\alpha\]and the claim follows from the triangle inequality, using that $\sum_{s \in S} e^{2\pi is\alpha}=2\sum_{j=1}^k \cos(2\pi a_j)$ is real so that the integrand is nonnegative (because of the even exponent).
R u sure that this works? I understand that the integrals would count the number of solutions to the equations if all elements in $S$ were integers. I have checked when $S=\{x,-x\}$ for some irrational $x$ and for $n=1$ and the first integral isn't even an integer. Can you check if this is correct and if yes show why?
Tintarn
15.03.2023 22:46
This is an important subtlety which I had overlooked previously, so thanks for pointing it out. There is however an easy way around this issue (which in fact works usually in such situations): First of all, it is clear that we can do it not only for integers but also for rationals, by just scaling with the denominator. Next, we can generalize to vectors of rational/integer numbers, or equivalently, systems of linear equations, by integrating over $[0,1]^k$ instead of $[0,1]$. Finally, this allows us to treat the case of general real numbers by choosing a basis for the finitely many elements of $S$ over $\mathbb{Q}$ and then noting that the equation just becomes a rational system of linear equations, which we dealt with above.
M11100111001Y1R
28.06.2023 23:52
The official solution doesn't need college math. If someone here is from Poland please write the official solution if not, I'll write it but it takes time.