Natural numbers in a circle, combinatorics, existence
$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}$.
combinatorics permutations
$endgroup$
add a comment |
$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}$.
combinatorics permutations
$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
add a comment |
$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}$.
combinatorics permutations
$endgroup$
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}$.
combinatorics permutations
combinatorics permutations
edited Dec 8 '18 at 19:01
Jam
4,95021431
4,95021431
asked Apr 9 '16 at 20:44
AxiomAxiom
32
32
$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
add a comment |
$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
$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$
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$
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$
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
$begingroup$
Not homework, merely curiosity. Feel free to leave a full solution.
$endgroup$
– Axiom
Apr 9 '16 at 23:51
add a comment |
1 Answer
1
active
oldest
votes
$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}/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...
$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
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1735130%2fnatural-numbers-in-a-circle-combinatorics-existence%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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}/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...
$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
add a comment |
$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}/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...
$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
add a comment |
$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}/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...
$endgroup$
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...
answered Apr 10 '16 at 0:18
Josse van Dobben de BruynJosse van Dobben de Bruyn
3,808824
3,808824
$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
add a comment |
$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
$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
$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
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1735130%2fnatural-numbers-in-a-circle-combinatorics-existence%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$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