We call a $5$-tuple of integers arrangeable if its elements can be labeled $a, b, c, d, e$ in some order so that $a-b+c-d+e=29$. Determine all $2017$-tuples of integers $n_1, n_2, . . . , n_{2017}$ such that if we place them in a circle in clockwise order, then any $5$-tuple of numbers in consecutive positions on the circle is arrangeable. Warut Suksompong, Thailand
Problem
Source: APMO 2017, problem 1
Tags: combinatorics, APMO
14.05.2017 18:37
Here are two very different solutions. I came up with the complicated solution on the test.
14.05.2017 19:06
Answer: the only $2017$-tuple which is valid is $\underbrace{(29, 29, \dots, 29)}_{2017}$. (Proof) Shift the numbers by $x \mapsto x-29$, so for every $5$-tuple of consecutive numbers, there exists a permutation $\{a, b, c, d, e\}$ such that $a-b+c-d+e=0$. Observe that $$(a+c+e)-(b+d) \equiv (a+b+c+d+e) \pmod{2},$$so all sums of five consecutive numbers on the circle are even. Thus, the $(i+5k)$-th number has the same parity as the $i$-th. Since $\gcd(5, 2017)=1$ all the numbers on the circle have the same parity, so they must be all even. Dividing by $2$, we reduce the sum of absolute values of the numbers; giving an infinite descent, contradiction; unless all the numbers are zero; so the answer is valid. $\blacksquare$
14.05.2017 22:15
14.05.2017 23:06
Notably, the answer to this problem was also the sequence of US scores on the 2017 APMO.
16.05.2017 12:16
I have heard from my country's team leader that this problem is proposed by Warut Suksompong, Thailand.
18.05.2017 13:31
a1267ab wrote: \[ \Delta= \begin{vmatrix} \varepsilon_{1, 1} & \varepsilon_{1, 2} & \varepsilon_{1, 3} & \varepsilon_{1, 4} & \varepsilon_{1, 5} & 0 & \hdots & 0 \\ 0 & \varepsilon_{2, 1} & \varepsilon_{2, 2} & \varepsilon_{2, 3} & \varepsilon_{2, 4} & \varepsilon_{2, 5} & \hdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots &\ddots & \vdots \\ \varepsilon_{2017, 2} & \varepsilon_{2017, 3} & \varepsilon_{2017, 4} & \varepsilon_{2017, 5} & 0 & 0 & \hdots & \varepsilon_{2017, 1} \end{vmatrix}. \]$\Delta$ has the same parity as \[ \Delta_0= \begin{vmatrix} 1 & 1 & 1 & 1 & 1 & 0 & \hdots & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & \hdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots &\ddots & \vdots \\ 1 & 1 & 1 & 1 & 0 & 0 & \hdots & 1 \end{vmatrix}, \]because the determinant is a multilinear function, and changing each $\varepsilon_{ij}$ to 1 has no effect modulo 2. To evaluate this determinant, we look more generally at any $2017\times 2017$ circulant matrix, defining \[ f(a_0, a_1, \ldots, a_{2016})= \begin{vmatrix} a_0 & a_1 & a_2 & \hdots & a_{2016} \\ a_{2016} & a_0 & a_1 & \hdots & a_{2015} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_1 & a_2 & a_3 & \hdots & a_{0} \end{vmatrix}. \]Let $\omega=e^{\frac{2\pi i}{2017}}$ be a primitive $2017$th root of unity, and $P(x)=a_0+a_1x+\ldots + a_{2016}x^{2016}$. For any integer $0\leq k\leq 2016$, we perform the row operation of adding $\omega^k$ times the $2016$th row to the first, $\omega^{2k}$ times the $2015$th row to the first, etc. The first row is then $(P(\omega^k), \omega^{-k}P(\omega^k), \ldots, \omega^{-2016k}P(\omega^k))$, so $P(\omega^k)$ is a factor of $f(a_0, a_1, \ldots, a_{2016})$. Since $f$ is a degree $2017$ function, we must have \[ f(a_0, a_1, \ldots, a_{2016})=cP(1)P(\omega)\cdots P(\omega^{2016}) \]for some constant $c$. Comparing the $a_0^{2016}$ term of both sides, we conclude that $c=1$. For the case of $\Delta_0$, we have $P(x)=1+x+x^2+x^3+x^4=\frac{x^5-1}{x-1}$. Therefore \[ \Delta_0=5\frac{(\omega^5-1)(\omega^{10}-1)\cdots(\omega^{10080}-1)}{(\omega-1)(\omega^2-1)\cdots(\omega^{2016}-1)}=5 \]because the fraction's numerator and denominator are permutations of each other. $\Delta_0$ is odd, so $\Delta$ is odd and therefore nonzero. Hence we have the unique solution, as desired. Actually, to show that $\Delta_0$ is odd, you just have to show that the matrix is invertible over $\mathbb{Z}/2\mathbb{Z}$, which is true since $(5,2017)=1$.
22.05.2017 05:57
This problem is easily generalizable over rational numbers, but does a similar result hold true over real numbers?
23.05.2017 21:44
muhammad-alhafi1 wrote: my solution: The condition is that $a-b+c-d+e=29$ in some order, not necessarily clockwise order, so your solution fails.
23.05.2017 22:11
InCtrl wrote: This problem is easily generalizable over rational numbers, but does a similar result hold true over real numbers? Yes, the linear algebra solutions above (e.g. showing the determinant is odd) imply the result holds over any (characteristic zero) field.
24.05.2017 03:19
20.02.2018 20:32
Here's a purely combinatorial solution. Do point to any possible errors. As has been mentioned above, it suffices to show that the determinant \[ \Delta_0= \begin{vmatrix} 1 & 1 & 1 & 1 & 1 & 0 & \hdots & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & \hdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots &\ddots & \vdots \\ 1 & 1 & 1 & 1 & 0 & 0 & \hdots & 1 \end{vmatrix}, \] is odd. Notice that an $n \times n$ determinant is composed of $n!$ terms, each term a perfect matching of the entries of the determinant. In our case, majority of these terms are $0$. The only relevant terms are the ones which are products of $1$ 's. These terms can be bijected to permutations $P$ of the set $\{1,2,\cdots 2017\}$ so that $$P(i) \in \{i,i+1,i+2,i+3,i+4\} \pmod {2017}$$(the bijection is simply that the $i$-th term of the permutation is the index of the entry in the $i$-th row of the determinant). So now we have a completely combinatorial problem. Problem. Show that the number of permutations $P$ of $\{1,2,\cdots 2017\}$ with $P(i) \in \{i,i+1,i+2,i+3,i+4\} \pmod {2017}$ is odd. Proof: Call all such permutations valid. Notice that you can pair up each valid permutation $P$ with the permutation $P'$ with $P'(2018-i)=5-P(i) \pmod {2017} $. It's easy to see that $P'$ is also valid. Note that this is an invalid pairing iff $P$ and $P'$ are the same permutation, which happens only in the case $P(i)=i+2$ for all $i$. Thus only one permutation remains unpaired, hence the number of valid permutations is odd, proving the claim.
05.08.2018 00:09
super cool problem
03.09.2018 06:56
Consider the n tuples are arranged in a circle. Then, fix one of the terms as the first term say a. Then let the next four terms be b,c,d,e respectively. If we go on computing the 6th,7th... terms in terms of a,b,c,d,e we observe that the sequence starts repeating from the 11th term. That is the 11th term is a, 12th term is b and so on the sequence again starts repeating. Now, since the numbers are arranged in a circle so the 2018th term should also be a. But, going in the similar way as said above, we get the 2018th term as a different number in terms of a,b,c,d,e. Similarly on using the same fact we compare the 2019th,2020th terms to get two more equations. So, on solving these equations we get (a,b,c,d,e)=(29,29,29,29,29). Now we also find that the 6th,7th,8th,9th, and 10th terms are also 29. Now we already found that the sequence has a periodicity of 10. Hence, the 2017 tuple is (29,29,..........,29).
07.10.2019 20:44
Call a $5$-tuple leeky if it can be rearranged such that $a+c+e=b+d$. If the arrangement $(a_1,\ldots,a_{2017})$ satisfies the condition, then subtracting $29$ from each number makes all consecutive $5$-tuples leeky, so it suffices to find all leeky constructions. Clearly, we need $2|a+b+c+d+e$, so $a_i\equiv a_{i+5}\pmod 2$, and we get that all numbers are the same parity. Also, they can't all be odd, so we can divide all of them by $2$, and get another leeky arrangement. Similarly, they are still all even, and we can continue dividing by $2$ infinitely, implying that the only leeky arrangement is $(0,0,\ldots,0)$, and our answer is $(29,29,\ldots,29)$.
25.02.2020 23:46
Quote: Actually, to show that $\Delta_0$ is odd, you just have to show that the matrix is invertible over $\mathbb{Z}/2\mathbb{Z}$, which is true since $(5,2017)=1$. Can you please explain a bit?
13.10.2020 10:12
BartSimpsons wrote: We call a $5$-tuple of integers arrangeable if its elements can be labeled $a, b, c, d, e$ in some order so that $a-b+c-d+e=29$. Determine all $2017$-tuples of integers $n_1, n_2, . . . , n_{2017}$ such that if we place them in a circle in clockwise order, then any $5$-tuple of numbers in consecutive positions on the circle is arrangeable. Warut Suksompong, Thailand Infinite Descent FTW. Take $a' \mapsto a - 29$ and so on. Observe that $a'-b'+c'-d'+e'=0$, and similarly $a'+b'+c'+d'+e'=2(b'+d')$ and so, parity of every $k+5^{\mathrm{th}}$ term is same as $k^{\mathrm{th}}$ term. But since $2017$ is odd, eventually you get that all numbers are even, since sum of five odd numbers aren't even. But if all numbers aren't the same, we do $\nu _2$ reduction of all terms. Eventually you'll get few odd few even configuration or all odd configuration, a contradiction unless the numbers never changed since the $\nu _2$ reduction, that is all numbers are $0$. Hence, the only valid or legal tuple is set of all $29$. TL;DR : Infinite Descent gives you wings!
14.02.2021 10:28
Let $k_i=n_i-29$, take all indices mod 2017. Then for all $k_i,k_{i+1},...,k_{i+4}$ we can be labelled $a,b,c,d,e$ in some order such that $$a-b+c-d+e=0$$Notice that if there exists some number $d$ divisible by all $k_i$ then dividing all numbers by $d$ will preserve this property. Therefore we may assume the nonzero numbers have g.c.d. 1. Claim. $a_i\equiv a_{i+5}\pmod 2$ for all $i$ Proof. Notice that the number of odd numbers among $k_i,k_{i+1},...,k_{i+4}$ must be even. Hence if $k_i$ and $k_{i+5}$ have different parity then the number of odd numbers among $$(k_i,k_{i+1},...,k_{i+4})\text{ and }(k_{i+1},...,k_{i+5})$$will be differed by $1$, contradiction. $\blacksquare$ Therefore, all numbers are congruent modulo $5$ since $(5,2017)=1$. Now obivously they can't all be odd, so they must all be even. From our assumption we have $k_i\equiv 0$. Therefore $n_i\equiv 29$ is the only solution.
14.04.2021 00:08
Claim: The answer $n_i=29$ is the only solution. Send $n_i\to n_i-29$ and note that the condition transforms to to \[a-b+c-d+e=0.\]Take mod $2$ and note \[a+b+c+d+e\equiv 0\pmod{2}\]\[b+c+d+e+f\equiv 0\pmod{2}\]\[a\equiv f\pmod{2}.\]Since $5\nmid 2017$ this proves all $n_i$ are congruent mod $2.$ But $5\not\equiv 0\pmod{2}$ so we must have $2\mid n_i$. Infinite descent shows all $n_i$ must be $0,$ so after reversing our transformation we just get $n_i=29.$
21.04.2021 22:39
Solution. Let $x\rightarrow x-29$, then $a-b+c-d+e=29$ transforms to $a+c+e=b+d$, now note that $a+b+c+d+e=2(b+d)$, hence $a+b+c+d$ is even. Now since: $$a_1+a_2+a_3+a_4\equiv a_2+a_3+a_4+a_5+a_6\pmod 2\implies a_1\equiv a_6\pmod 2$$So, $a_i\equiv a_{i+5}\pmod 2$ and since $\gcd(2017, 5)=1$, we have that all numbers are even or odd. Suppose all numbers are odd we have that $a+c+e$ is odd and $b+d$ is even, therefore contradiction since $a+c+e=b+d$. Hence all number are even. Now we can again divide by $2$ and we again get a solution, also similarly we have that all numbers are even, now by infinite descent we have that all these numbers must be $0$. So the only solution is $(a_1, a_2,..., a_{2017})=(29, 29, ..., 29)$.$\blacksquare$
07.06.2022 17:54
The answer is $n_i=29$ for every $i$ only. Let $a_i = n_i-29$ for every $i$, and $P(a_i)$ be the assertion on the terms $a_i, a_{i+1}, \cdots, a_{i+5}$. As $P(a_i)$ and $P(a_{i+5})$ imply $a_i \equiv a_{i+5} \pmod 2$ for all indices $i$ taken modulo 2017, it follows that all $a_i$ are congruent modulo 2 by CRT. Hence, one can just construct an infinite descent, which finishes.
09.03.2023 22:58
Answer is only if all are equal to $29$. Proof is simple: Notice given a condition $P(c) := a+b+c+d+e \equiv c \pmod 2$, so $a \equiv f \pmod 2$, so all numbers are equivalent $\pmod 2$, so we can write $a = 2a' + 1$ for all cases and reduce to the equation $P(\lfloor \frac{c}{2} \rfloor)$. Now notice $P(29) \Longrightarrow P(14) \Longrightarrow P(7) \Longrightarrow P(3) \Longrightarrow P(1) \Longrightarrow P(0)$, whereupon we obtain $v_2(a) = \infty$ for any $a$ by repeating the reduction. Hence in $P(0)$ we must have all terms equal to $0$, so backpropagating up the chain we have the requirement that all elements are equal.
15.07.2023 06:57
Shift everything down by 29, and replace 29 by 0. Take indices mod 2017. Claim: Every number in the circle is even. Note that the condition implies that any 5 consecutive terms have an even sum. Summing this over all 2017 cyclic variants, 5 times the sum of everything is even, so the sum of all terms is even. Now, assume FTSOC assume $a_i$ is odd. Partition the circle into $a_i$, $a_{i+1}$ and the remaining 2015 numbers into 403 groups of 5. The sum of the groups of 5 is of course even, and the total sum is even, so $a_{i+1}$ is also odd. Continuing in this fashion, $a_{i+2},a_{i+3},a_{i+4}$ are also odd. However, $a_i+a_{i+1}+a_{i+2}+a_{i+3}+a_{i+4}$ is odd, contradiction. Thus, all numbers are even. However, we can then divide out the factor of 2 and everything will stay the same (as the condition is 0 so dividing by 2 is still 0), so by infinite descent all numbers in the circle are 0. Hence, back to the original problem, the only solution is all 29s.
21.07.2023 00:08
Let $n_1,n_2,...,n_{2017}$ satisify this.We can easily see that $n_1 \equiv n_2 \equiv ... \equiv n_{2017} \equiv 1 (mod 2)$ because $(5,2017)=1$. If $a,b,c,d,e$ are arrangeable, then $\frac{a+29}{2},\frac{b+29}{2},\frac{c+29}{2},\frac{d+29}{2},\frac{e+29}{2}$ are also arrangeable.(Also they are integers) \[\frac{a+29}{2}-\frac{b+29}{2}+\frac{c+29}{2}-\frac{d+29}{2}+\frac{e+29}{2}=\frac{a-b+c-d+e}{2}+\frac{29}{2}=29\]We know that $\frac{n_1+29}{2}$ is also odd. $n_1,n_2,...,n_{2017} \implies \frac{n_1+29}{2},\frac{n_2+29}{2},...,\frac{n_{2017}+29}{2}$ $\implies \frac{\frac{n_1+29}{2}+29}{2},\frac{\frac{n_2+29}{2}+29}{2},...,\frac{\frac{n_{2017}+29}{2}+29}{2}$ $\frac{n_1+3.29}{4}$ is also odd. We can generalize this to $n_1,n_2,...,n_{2017} \implies\frac{n_1+(2^k-1).29}{2^k},\frac{n_2+(2^k-1).29}{2^k},...,\frac{n_{2017}+(2^k-1).29}{2^k}$ by induction. So $2^k||n_1-29|,|n_2-29|,...,|n_{2017}-29|$ for all $k$ positive integers. Let's choose $k$ such that $2^k>|n_i-29|$. We have $2^k|n_i-29$ but the left hand side is larger. So $|n_i-29|=0$. $\implies n_1=n_2=...=n_{2017}=29$
01.01.2025 19:45
Let us suppose we have $a_1, \ldots, a_{2017}$ satisfying this that is arrangled clockwise on the circle with $a_{2017}$ adjacent to $a_1$. Then we consider $(a_{2017}, a_1, a_2, a_3,a_4)$ and $(a_1,a_2,a_3,a_4,a_5)$. Suppose they are arranged in a way such that both evaluate to 29, then note that if we subtract them, $a_i$ will cancel out with the same $a_i$ if they have different signs and $a_i$ will turn into $\pm 2a_i$ if they have the same sign. Thus we get that $2X=\pm a_{2017} \pm a_5$ where $X$ is some expression involving $a_1,a_2,a_3,a_4$. Thus, $a_{2017} \equiv a_5 \mod{2}$. In fact repeating this argument we can see that all $a_{5k}$ are of the same parity, since $\gcd(5,2017)=1$, we can cover the entire modulo system of $2017$ with $5k$. Thus every element is of the same parity, clearly they must be all odd. Now, if we subtract 1 and divide 2 to all elements we end up with the same condition but with 29 replaced with 14 and by a similar argument all must be even. If we divide 2 to all elements we replace 14 with 7 and all must be odd, subtract 1 and divide 2 we replace 7 with 3 and all must be odd, subtract 1 and divide 2 we replace 3 with 1 and all must be odd, subtract 1 we replace 1 with 0 and all must be even. At this point we note that for any arrangeable $(a_1,a_2,a_3,a_4,a_5)$, $(a_1/2, a_2/2,a_3/2,a_4/2, a_5/2)$ is also arrangeable to 0 and all must be even. Thus by infinite descent since $\nu_2(x)<\infty$ for $x \neq 0$ we must have that all $a_i$ is 0 at this point. Reversing all the modifications we did we get that all $a_i$ must be 29. Thus $(29,\ldots,29)$ is the only possible solution and it is clear that it is indeed a solution.