Cfrgtkky

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}$.

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}/74mathbb{Z}$ of integers modulo $74$.) Now the formula $s_i = a_{i-1} + a_i + a_{i+1}$ holds for all $iinmathbb{Z}/74mathbb{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 $iin 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_{iin I} s_i : = : 3cdot sum_{k=1}^{74} k : = : 3cdot 2775 : = : 8325, $$
by double counting, so that we find
$$ 8325 : = : sum_{iin I} s_i : leq : 113cdot |A| + 112cdot |B|.tag*{$(1)$} $$
Since we have $|A| + |B| = 74$, it follows that
$$ 113cdot big(74 - |B|big) + 112cdot |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 $iin 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 $iin I$. No idea about 114 though...