Let $n>2$ be a positive integer and let $p$ be a prime. Suppose that the nonzero integers are colored in $n$ colors. Let $a_1,a_2,\ldots,a_{n}$ be integers such that for all $1\le i\le n$, $p^i\nmid a_i$ and $p^{i-1}\mid a_i$. In terms of $n$, $p$, and $\{a_i\}_{i=1}^{n}$, determine if there must exist integers $x_1,x_2,\ldots,x_{n}$ of the same color such that $a_1x_1+a_2x_2+\cdots+a_{n}x_{n}=0$. Ravi Jagadeesan.
Problem
Source: ELMO Shortlist 2012, N5
Tags: modular arithmetic, number theory proposed, number theory
math154
04.02.2013 23:13
Here's a hint à la Ravi Jagadeesan.
There do not exist $n,p,\{a_i\}$ the answer to this problem is yes for.
hyperbolictangent
26.03.2013 21:33
The answer is no for all $n$, $p$, and $\{a_i\}_{i = 1}^{n}$. Label the colors $c_0, c_2, \dots, c_{n - 1}$, and consider the coloring of the non-zero integers which assigns to an integer $x$ the color $c_{v_p(x) \pmod{n}}$. Suppose, for the sake of contradiction, there existed monochromatic $x_1, x_2, \dots, x_n$ satisfying \[ a_1x_1+a_2x_2+\cdots+a_{n}x_{n}=0 \; \; \; \; (1) \] Set $v_i = v_p(x_i)$. There exists a minimum $m = \min(v_i)$ and a smallest index $j$ with $v_j = m$. Dividing $(1)$ by $p^{m + j - 1}$ and taking modulo $p$ gives a contradiction (since by construction numbers of the same color with distinct $p$-adic valuations have their $p$-adic valuations differ by at least $n \ge m$ and using the fact that $p^{i - 1} || a_i$).