0
$\begingroup$

I need help with a problem whose solution I'm unaware of. The first $74$ natural numbers are arranged in a circle. Does an arrangement exist such that every sum of three consecutively arranged numbers is at most $113$?

I can prove that in every arrangement one of the sums must be greater than or equal to $113$ but not whether it is the maximum.

Formally, I suppose: let $a_1, a_2, ..., a_{74}$ be a permutation of $1, 2, ... 74$
let $s_1 = a_{74} + a_1 + a_2$, $s_{74} = a_{73}+a_{74}+a_1$
otherwise, let $s_i = a_{i-1} + a_i + a_{i+1}$

Prove or disprove that there exist $a_1, ..., a_{74}$ such that $s_i \leq 113, \forall i \in \{1, 2, ... 74\}$.

$\endgroup$
  • $\begingroup$ If you can prove that in every arrangement one of the sums must be greater than or equal to 113, that makes it impossible for there to be an arrangement such that all sums are at most 113. $\endgroup$ – M47145 Apr 9 '16 at 21:17
  • $\begingroup$ Those two statements are not equivalent - for example, a configuration with some 113s and some 112s would satisfy the condition - if such a configuration exists. $\endgroup$ – Axiom Apr 9 '16 at 21:31
  • $\begingroup$ Do you want a full solution or do you prefer a hint? (Is this homework?) $\endgroup$ – Josse van Dobben de Bruyn Apr 9 '16 at 23:18
  • $\begingroup$ Not homework, merely curiosity. Feel free to leave a full solution. $\endgroup$ – Axiom Apr 9 '16 at 23:51
0
$\begingroup$

Unfortunately, no such arrangement exists.

Notation. Let us assume that the indices are cyclical. (For instance, we may assume that the sequences $\{a_i\}_{i=1}^{74}$ and $\{s_i\}_{i=1}^{74}$ are indexed not by the set $\{1,\ldots,74\} \subseteq \mathbb{N}$ but by the set $\mathbb{Z}/74\mathbb{Z}$ of integers modulo $74$.) Now the formula $s_i = a_{i-1} + a_i + a_{i+1}$ holds for all $i\in\mathbb{Z}/74\mathbb{Z}$, because the index $74 + 1$ is understood to be the same as the index $1$.

Furthermore, for the sake of convenience, let us denote the index set by $I$.

Suppose, for the sake of contradiction, that a permutation $a_1,\ldots,a_{74}$ is given such that $s_i \leq 113$ holds for all $i\in I$. Let us partition the index set $I$ into two sets $A$ and $B$ given by \begin{align} A &= \{i \in I \: : \: s_i = 113\};\\[1ex] B &= \{i \in I \: : \: s_i \leq 112\}. \end{align} Note that the same estimate you used gives us a conditions on the sizes of $A$ and $B$: we have $$ \sum_{i\in I} s_i \: = \: 3\cdot \sum_{k=1}^{74} k \: = \: 3\cdot 2775 \: = \: 8325, $$ by double counting, so that we find $$ 8325 \: = \: \sum_{i\in I} s_i \: \leq \: 113\cdot |A| + 112\cdot |B|.\tag*{$(1)$} $$ Since we have $|A| + |B| = 74$, it follows that $$ 113\cdot \big(74 - |B|\big) + 112\cdot |B| \: \geq \: 8325, $$ which simplifies to $|B| \leq 37$. Therefore we have $|A| = 74 - |B| \geq 37 \geq |B|$. In words: at least half of the consecutive triples should have sum $113$. (Intuitively, this is because $\frac{8325}{74} = 112.5$ holds, so every triple with sum $\leq 112$ should be balanced by at least one triple with sum $113$.)

On the other hand, suppose that $i \in A$ is given, so that we have $a_{i-1} + a_i + a_{i+1} = 113$. By assumption we have $a_{i-1} \neq a_{i+2}$. Now it follows that we cannot have $a_{i+2} > a_{i-1}$, for that would imply $$ s_{i+1} \: = \: a_i + a_{i+1} + a_{i+2} \: > \: a_i + a_{i+1} + a_{i-1} \: = \: 113, $$ contrary to the assumption that $s_{i+1} \leq 113$ must hold. Thus, we must have $a_{i+2} < a_{i-1}$, from which it follows that $$ s_{i+1} \: = \: a_i + a_{i+1} + a_{i+2} \: < \: a_i + a_{i=1} + a_{i-1} \: = \: 113. $$ Thus, we have the following important observation:

Observation. For every $i \in A$ we have $i + 1 \in B$.

Therefore we have an injective function $f : A \to B$ given by $i \mapsto i + 1$, which shows that $|A| \leq |B|$ holds. Combining this with earlier findings, we see that $|A| = |B|$ must hold. Of course now the equality $|A| + |B| = 74$ fixes the sizes of $A$ and $B$ at $37$ elements each. Now we have equality in (1), from which we can deduce that $s_i = 112$ must hold for every $i\in B$. (In other words, no consecutive triple has sum $\leq 111$.) Furthermore, since every element of $A$ is succeeded by an element of $B$, it follows that the sequence $s_1,\ldots,s_{74}$ must in fact alternate between $113$ and $112$.

Now we assume without loss of generality that $s_2 = 113$ holds (shift the solution if necessary). Note that the entire sequence $a_1,\ldots,a_{74}$ is fixed by the values of $a_1$ and $a_2$, since we know the exact values of $s_1,\ldots,s_{74}$. Specifically, we have \begin{align} a_3 \: &= \: 113 - a_1 - a_2;\\[1ex] a_4 \: &= \: 112 - a_2 - a_3 \: = \: a_1 - 1;\\[1ex] a_5 \: &= \: 113 - a_3 - a_4 \: = \: a_2 + 1;\\[1ex] a_6 \: &= \: 112 - a_4 - a_5 \: = \: a_3 - 1;\\[1ex] a_7 \: &= \: 113 - a_5 - a_6 \: = \: a_4 + 1 \: = \: a_1. \end{align} This contradicts the assumption that all $a_i$ are distinct. Hence there is no solution with $s_i \leq 113$ for all $i\in I$. No idea about 114 though...

$\endgroup$
  • $\begingroup$ Thank you! I got to the first set of bounds on A and B on my own before going to sleep, but no further. It's quite a bit of work just to increase the bound by $1$. $\endgroup$ – Axiom Apr 10 '16 at 9:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.