Sorry, but which one is "for any" and " there exist"? The $a,b,c$ or the $x,y,z$? Thanks a lot!

MathPanda1 wrote: Sorry, but which one is "for any" and " there exist"? The $a,b,c$ or the $x,y,z$? Thanks a lot! for any $a,b,c$ there exist $x,y,z$ See also here

Let $A=\{ax+by+cz:x,y,z\in\mathbb Z\cap [-n,n]\}$. Then $\min A=-3n^3-4n^2$ and $\max A=3n^3+4n^2$. So the interval $[\min A,\max A]$ contains $6n^3+8n^2+1<(2n+1)^3$ integers. So by the pigeonhole principle there must be distinct $(x,y,z)$ and $(x',y',z')$ in $(\mathbb Z\cap [-n,n])^3$ such that $ax+by+cz=ax'+by'+cz'$, i.e. $a(x-x')+b(y-y')+c(z-z')=0$. Since $x-x',y-y',z-z'\in[-2n,2n]$ are not all zero, we are done.

I see your last post was in 2012. Welcome back to AoPS

Thanks! I'm just too busy with other things these days, but it always feels good to solve some olympiad problems This one in particular was related to something I've been working on lately so I thought of giving it a shot.

Another approach: WLOG $a$ is the largest among $a,b,c$. Clearly if $a=b$ or $c$ (WLOG $b$) we are done as we can set $(x,y,z)=(1,-1,0)$, hence $a>b,c$. Consider the remainder of $by+cz$ when divided by $a$ for $(y,z)$ satisfying $n\leq y+z\leq 3n+1$, $2n\geq y,z\geq 0$. As there are $3n^2+4n+1$ such pairs, two pairs (say $(Y,Z)\neq (Y',Z')$) give the same remainder when divided by $a$. Hence we have that $a$ divides $b(Y-Y')+c(Z-Z')$. Clearly, $-2n\leq (Y-Y')+(Z-Z')\leq 2n$. Since $-a(2n+1)<b(Y-Y')+c(Z-Z')<a(2n+1)$, an $x$ within the bounds can also be chosen.

@nayel: unfortunately $ n(3n^2 + 4n) + n(3n^2 + 4n) + n(3n^2 + 4n) = 9n^3 + 12n^2 $ so that number is the maximum of set $ A. $ This kind of solution almost certainly fails. @yugrey: at the beginning of your proof, I think you mean $ x^2 + y^2 \ne 0 $ If $ |(a - b)(b - c)(c - a)| > 0 $ then some permutation of $ (x, y, z) = (1, -1, 0) $ will be a solution. Otherwise, assume WLOG that $ c > a, b. $ Consider all numbers of the form $ ax + by $ where $ (x, y) \in \mathbb{N}^2 \cap [0, 2n]^2 $ and $ n \le x + y \le 3n + 1. $ We can easily count that there are $ ((n + 1) + (n + 2) + \dots + (2n + 1)) + (2n + 1) + (2n + (2n - 1) + \dots + (n + 2)) = 3n^2 + 4n + 1 $ such pairs. Because $ c < 3n^2 + 4n + 1, $ by the pigeonhole principle there exist two such pairs $ (x_1, y_1) $ and $ (x_2, y_2) $ such that $ ax_1 + by_1 \equiv ax_2 + by_2 \pmod{c}. $ Therefore $ a(x_1 - x_2) + b(y_1 - y_2) \equiv 0 \pmod{c}. $ By the conditions on $ x_1, x_2, y_1, y_2 $ we have that $ |x_1 - x_2|, |y_1 - y_2| \le 2n $ and $ |a(x_1 - x_2) + b(y_1 - y_2)| < |c((x_1 + y_1) - (x_2 + y_2))| \le (2n + 1)c $ which implies that $ (x, y, z) = \left(x_1 - x_2, y_1 - y_2, \frac{a(x_2 - x_1) + b(y_2 - y_1)}{c}\right) $ is a solution so we are done. How does one come up with this? Well, problems like this are often done by considering $ ax + by \pmod{c}. $ We want to look at a bunch of pairs $ (x, y) $ and get two numbers of the form $ ax + by $ to be equivalent $ \mod{c} $ - then we can subtract them and win. However, there are conditions that need to be met: First, we need there to be at least $ 3n^2 + 4n + 1 $ pairs so we can use pigeonhole. Second, we need for any two pairs $ (x_1, y_1) $ and $ (x_2, y_2) $ that $ |x_1 - y_1|, |y_1 - y_2| \le 2n. $ And third, because we need $ |a(x_1 - x_2) + b(y_1 - y_2)| < (2n + 1)c, $ we want $ |(x_1 + y_1) - (x_2 + y_2)| \le 2n + 1. $ The second condition can easily be handled by restricting $ 0 \le x, y \le 2n. $ To handle the third condition, we need to force $ a \le x + y \le 2n + 1 + a $ for some $ a. $ We want to choose an $ a $ so that the number of possible pairs is maximized - now by treating $ x $ and $ y $ as discrete random variables we have that $ E[x + y] = 2n $ so it is natural to try and make the interval $ [a, 2n + 1 + a] $ centered around $ 2n $ which can be achieved by letting $ a = n $ or $ n - 1. $ This finished the problem.

Well, I think it is silmilar to maybe some problem in Miklos Schweitzer 2000. I don't remember the exact number.

WLOG $a < b < c$ (if two of them are equal then we are done). Note that for any $(x,y)$ already chosen, $|ax + by + cz|$ is minimized for one unique $z$, and such $z$ exists iff $c | ax+ by$. Our goal is to construct a multiset of the form $S:= \{ax + by: (x,y) \in T \subseteq [0,2n]\otimes [0,2n]\}$ so that if two elements of $S$ are congruent mod $c$ and $\max S - \min S < (2n+1)c$ then we are done. In the case $a = b = c$, $|S|$ is optimal when $T$ is chosen to be $\{(x,y): n \ le x+y \le 3n\}$. It is easy to verify that this choice of $T$ works in general and results in $|S| = 3n^2 + 3n + 1$. However, since we assumed $a < b < c$, the equality $\max S - \min S = (2n+1)c$ cannot be achieved when we add another $n$ points $(0,n-1),(1,n-2),\dots, (n-1,0)$ to $T$, hence $|S| = 3n^2 + 4n + 1$ can be achieved, as desired.