Mixing
Smallest size of set of real numbers such that the sum of any seven is strictly positive, and the sum of any...
So I just got asked a question that riddled me.
If you have a set of real numbers, such that the sum of any 7 numbers from this set is strictly positive and the sum of any 11 numbers from this set is strictly negative, then what is the smallest possible size of this set?
I've managed to prove that the size can't be 11 but beyond that I'm bamboozled. (I'm not even sure if this is possible, I was asked this question in an interview)
puzzle
edited Nov 21 '18 at 23:51
Blue
47.7k870151
asked Nov 21 '18 at 17:10
Rich
211
add a comment |
So I just got asked a question that riddled me.
If you have a set of real numbers, such that the sum of any 7 numbers from this set is strictly positive and the sum of any 11 numbers from this set is strictly negative, then what is the smallest possible size of this set?
I've managed to prove that the size can't be 11 but beyond that I'm bamboozled. (I'm not even sure if this is possible, I was asked this question in an interview)
puzzle
edited Nov 21 '18 at 23:51
Blue
47.7k870151
asked Nov 21 '18 at 17:10
Rich
211
add a comment |
So I just got asked a question that riddled me.
If you have a set of real numbers, such that the sum of any 7 numbers from this set is strictly positive and the sum of any 11 numbers from this set is strictly negative, then what is the smallest possible size of this set?
I've managed to prove that the size can't be 11 but beyond that I'm bamboozled. (I'm not even sure if this is possible, I was asked this question in an interview)
puzzle
edited Nov 21 '18 at 23:51
Blue
47.7k870151
asked Nov 21 '18 at 17:10
Rich
211
So I just got asked a question that riddled me.
If you have a set of real numbers, such that the sum of any 7 numbers from this set is strictly positive and the sum of any 11 numbers from this set is strictly negative, then what is the smallest possible size of this set?
I've managed to prove that the size can't be 11 but beyond that I'm bamboozled. (I'm not even sure if this is possible, I was asked this question in an interview)
puzzle
puzzle
edited Nov 21 '18 at 23:51
Blue
47.7k870151
asked Nov 21 '18 at 17:10
Rich
211
edited Nov 21 '18 at 23:51
Blue
47.7k870151
asked Nov 21 '18 at 17:10
Rich
211
edited Nov 21 '18 at 23:51
Blue
47.7k870151
edited Nov 21 '18 at 23:51
Blue
47.7k870151
edited Nov 21 '18 at 23:51
Blue
47.7k870151
47.7k870151
asked Nov 21 '18 at 17:10
Rich
211
asked Nov 21 '18 at 17:10
Rich
211
asked Nov 21 '18 at 17:10
Rich
211
211
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
Are you sure that is the correct version of the question? The simple answer seems to be 0, as for the empty set both conditions are fullfilled (if no 7/11-element subsets exists, than making any statement about all of them will always be true).
Note that this seems to be related/derived from to a question from 1977 International Mathematical Olympiad:
In a finite sequence of real numbers the sum of any seven successive
terms is negative, and the sum of any eleven successive terms is
positive. Determine the maximum number of terms in the sequence.
Notice however the important differences: Sequence instead of set and the maximum number is sought instead of the minimum. The positive/negative exchange seems to be unimportant, one can just exchange the sign of any set/sequence member to get from one formulation to the other.
answered Nov 21 '18 at 19:28
Ingix
3,344145
add a comment |
Let $A=text{a_1, a_2, ...}$ be the set you're looking for.
Since the sum of any 11 numbers from this set is strictly negative, it must contain at least 11 elements, so suppose this is the case
$$sum_{n=1}^{11} {(a_n)}<0$$
$$Rightarrow7*sum_{n=1}^{11} {(a_n)}<0$$
Denote now by $$FBiggl(sum_{n=8}^{3} {(a_n)}Biggr)$$the sum $$a_8+a_9+a_{10}+a_{11}+a_1+a_2+a_3$$ (Note that after the element $a_{11}$ we start again with ${a_1}$)
Thus
$$sum_{n=1}^{7} {(a_n)}>0$$
$$FBiggl(sum_{n=8}^{3} {(a_n)}Biggr)>0$$
$$sum_{n=4}^{10} {(a_n)}>0$$
$$FBiggl(sum_{n=11}^{6} {(a_n)}Biggr)>0$$
$$FBiggl(sum_{n=7}^{2} {(a_n)}Biggr)>0$$
$$sum_{n=3}^{9} {(a_n)}>0$$
$$FBiggl(sum_{n=10}^{5} {(a_n)}Biggr)>0$$
$$FBiggl(sum_{n=6}^{1} {(a_n)}Biggr)>0$$
$$sum_{n=2}^{8} {(a_n)}>0$$
$$FBiggl(sum_{n=9}^{4} {(a_n)}Biggr)>0$$
$$FBiggl(sum_{n=5}^{11} {(a_n)}Biggr)>0$$
(Note that they all the sums contain 7 members; they are all therefore strictly positive).
Adding the eleven inequalities
$$0<sum_{n=1}^{7} {(a_n)}+
FBiggl(sum_{n=8}^{3} {(a_n)}Biggr)+
sum_{n=4}^{10} {(a_n)}+
FBiggl(sum_{n=11}^{6} {(a_n)}Biggr)+
FBiggl(sum_{n=7}^{2} {(a_n)}Biggr)+
sum_{n=3}^{9} {(a_n)}+
FBiggl(sum_{n=10}^{5} {(a_n)}Biggr)+
FBiggl(sum_{n=6}^{1} {(a_n)}Biggr)+
sum_{n=2}^{8} {(a_n)}+
FBiggl(sum_{n=9}^{4} {(a_n)}Biggr)+
FBiggl(sum_{n=5}^{11} {(a_n)}Biggr)=7*sum_{n=1}^{11} {(a_n)}<0$$
Which is obviously a contradiction.
Summing up, what we've done is adding seven times $sum_{n=1}^{11} {(a_n)}$. This should be strictly negative since all "$sum_{n=1}^{11} {(a_n)}$" are negative. We can, nevertheless, divide all the summands into groups of seven elements, which should be (all of them) positive, leading to the required contradiction. Note that you can repeat this process for all possible $n$.
So if your maximal $n$ is $n_{max}$, you'll have to write $d=lcm(11*7,n_{max})=lcm(77,n_{max})$ elements in order $(a_1,a_2,...,a_{n_{max}-1},a_{n–{max}},a_1,a_2,...)$ and then group them in $frac{d}{11}$ gruops with 11 elements respectively (recall that these groups have to be negative). Group them afterwares in $frac{d}{7}$ groups, such that each of them contains exactly 7 elements (these groups will be hence positive). Howver the $d$ elements can't sum a negative and a positive number at the same time (required contradiction).
$mathbf {Remark}$
This problem reminds me of the second problem of the IMO in the year 1977:
In a finite sequence of real numbers the sum of any seven successive terms is negative, and the sum of any eleven successive terms is positive. Determine the maximum number of terms in the sequence.
If you're looking for a solution, there's an easy one you might like...
Let's begin grouping the elements of the succession as follows
$$a_1quad a_2quad a_3quad a_4quad a_5quad a_6quad a_7$$
$$a_2quad a_3quad a_4quad a_5quad a_6quad a_7quad a_8$$
$$..quad ..quad ..quad ..quad ..quad ..quad ..$$
$$a_{10}quad a_{11}quad a_{12}quad a_{13}quad a_{14}quad a_{15}quad a_{16}$$
$$a_{11}quad a_{12}quad a_{13}quad a_{14}quad a_{15}quad a_{16}quad a_{17}$$
Having a closer look at this representation you might note that every line is made out of seven elements (and is hence negative) and every column is made out of eleven elements (and is therefore positive). However, the total sum can't be positive and negative at the same time, so the sequence can not contain the 17th element. It is, however, possible to form a sequence with 16 elements satisfying the conditions. For instance
$$5,5,-13,5,5,5,-13,5,5,-13,5,5,5,-13,5,5$$
In the book "International Mathematical Olympiads 1959-1977" Samuel Greitzer shows a procedure (different from the simple guessing) in order to find the given example (which was published later by the Mathematical Association of America in 1978).
However, just as Arthur Engel criticizes in his book "Problem Solving Strategies" (pg. 85 and following) "[i]deally an IMO problem should be unknown to all students. Even a similar problem should never have been discussed in any country." He claims, that the problem 118 of "Dynkin–Molchanov–Rosental– Tolpygo": Mathematical Problems, 1971, 3rd edition with 200,000 copies sold, was almost identic to this one.
Now, back to the solution, in the book "The IMO compendium" the authors offer the following solution generalizing the problem
We shall prove a stronger statement: If 7 and 11 in the question are replaced by any positive integers $m,n$ then the maximum number of terms is $m+n−(m,n)−1$.
Let $a_1,a_2,...,a_l$ be a sequence of real numbers, and let us define $s_0 = 0$ and $s_k = a_1 +···+a_k quad (k = 1,...,l)$. The given conditions are equivalent to $s_k >s_{k+m}$ for $0≤k≤l−m$ and $s_k <s_{k+n}$ for $0≤k≤l−n$.
Let $d = (m,n)$ and $m = m'd,; n = n'd$. Suppose that there exists a sequence $(a_k )$ of length greater than or equal to $l = m + n − d$ satisfying the required conditions. Then the $m' +n'$ numbers $s_0,s_d,...,s_{(m'+n'−1)d}$ satisfy $n'$ inequalities $s_{k+m} < s_{k}$ and $m'$ inequalities $s_{k} < s_{k+n}$. Moreover, each term $s_{kd}$ appears twice in these inequalities: once on the left-hand and once on the right-hand side. It follows that there exists a ring of inequalities $s_{i_1} < s_{i_2} < · · · < s_{i_k}< s_{i_1}$ , giving a contradiction.
On the other hand, suppose that such a ring of inequalities can be made also for $l=m+n−d−1$, say $s_{i_1} <s_{i_2} <···<s_{i_k} <s_{i_1}$. If there are $p$ inequalities of the form $a_{k+m} < a_{k}$ and $q$ inequalities of the form $a_{k+n} >a_k$ in the ring,then $qn=rm$, which implies $m'mid q,quad n'mid p$ and thus $k = p + q ≥ m' + n'$. But since all $i_1,i_2,...,i_k$ are congruent modulo $d$, we have $k ≤ m' + n' − 1$, a contradiction. Hence there exists a sequence of length $m + n − d − 1$ with the required property.
This second solution was offered in the IMO by John Rickard, from the UK, who received a special price for such an original approach.
answered Nov 21 '18 at 20:19
Dr. Mathva
921316
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%2f3008035%2fsmallest-size-of-set-of-real-numbers-such-that-the-sum-of-any-seven-is-strictly%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
Are you sure that is the correct version of the question? The simple answer seems to be 0, as for the empty set both conditions are fullfilled (if no 7/11-element subsets exists, than making any statement about all of them will always be true).
Note that this seems to be related/derived from to a question from 1977 International Mathematical Olympiad:
In a finite sequence of real numbers the sum of any seven successive
terms is negative, and the sum of any eleven successive terms is
positive. Determine the maximum number of terms in the sequence.
Notice however the important differences: Sequence instead of set and the maximum number is sought instead of the minimum. The positive/negative exchange seems to be unimportant, one can just exchange the sign of any set/sequence member to get from one formulation to the other.
answered Nov 21 '18 at 19:28
Ingix
3,344145
add a comment |
Are you sure that is the correct version of the question? The simple answer seems to be 0, as for the empty set both conditions are fullfilled (if no 7/11-element subsets exists, than making any statement about all of them will always be true).
Note that this seems to be related/derived from to a question from 1977 International Mathematical Olympiad:
In a finite sequence of real numbers the sum of any seven successive
terms is negative, and the sum of any eleven successive terms is
positive. Determine the maximum number of terms in the sequence.
Notice however the important differences: Sequence instead of set and the maximum number is sought instead of the minimum. The positive/negative exchange seems to be unimportant, one can just exchange the sign of any set/sequence member to get from one formulation to the other.
answered Nov 21 '18 at 19:28
Ingix
3,344145
add a comment |
Are you sure that is the correct version of the question? The simple answer seems to be 0, as for the empty set both conditions are fullfilled (if no 7/11-element subsets exists, than making any statement about all of them will always be true).
Note that this seems to be related/derived from to a question from 1977 International Mathematical Olympiad:
In a finite sequence of real numbers the sum of any seven successive
terms is negative, and the sum of any eleven successive terms is
positive. Determine the maximum number of terms in the sequence.
Notice however the important differences: Sequence instead of set and the maximum number is sought instead of the minimum. The positive/negative exchange seems to be unimportant, one can just exchange the sign of any set/sequence member to get from one formulation to the other.
answered Nov 21 '18 at 19:28
Ingix
3,344145
Are you sure that is the correct version of the question? The simple answer seems to be 0, as for the empty set both conditions are fullfilled (if no 7/11-element subsets exists, than making any statement about all of them will always be true).
Note that this seems to be related/derived from to a question from 1977 International Mathematical Olympiad:
In a finite sequence of real numbers the sum of any seven successive
terms is negative, and the sum of any eleven successive terms is
positive. Determine the maximum number of terms in the sequence.
Notice however the important differences: Sequence instead of set and the maximum number is sought instead of the minimum. The positive/negative exchange seems to be unimportant, one can just exchange the sign of any set/sequence member to get from one formulation to the other.
answered Nov 21 '18 at 19:28
Ingix
3,344145
edited Nov 22 '18 at 7:47
answered Nov 21 '18 at 19:28
Ingix
3,344145
answered Nov 21 '18 at 19:28
Ingix
3,344145
answered Nov 21 '18 at 19:28
Ingix
3,344145
3,344145
add a comment |
add a comment |
Let $A=text{a_1, a_2, ...}$ be the set you're looking for.
Since the sum of any 11 numbers from this set is strictly negative, it must contain at least 11 elements, so suppose this is the case
$$sum_{n=1}^{11} {(a_n)}<0$$
$$Rightarrow7*sum_{n=1}^{11} {(a_n)}<0$$
Denote now by $$FBiggl(sum_{n=8}^{3} {(a_n)}Biggr)$$the sum $$a_8+a_9+a_{10}+a_{11}+a_1+a_2+a_3$$ (Note that after the element $a_{11}$ we start again with ${a_1}$)
Thus
$$sum_{n=1}^{7} {(a_n)}>0$$
$$FBiggl(sum_{n=8}^{3} {(a_n)}Biggr)>0$$
$$sum_{n=4}^{10} {(a_n)}>0$$
$$FBiggl(sum_{n=11}^{6} {(a_n)}Biggr)>0$$
$$FBiggl(sum_{n=7}^{2} {(a_n)}Biggr)>0$$
$$sum_{n=3}^{9} {(a_n)}>0$$
$$FBiggl(sum_{n=10}^{5} {(a_n)}Biggr)>0$$
$$FBiggl(sum_{n=6}^{1} {(a_n)}Biggr)>0$$
$$sum_{n=2}^{8} {(a_n)}>0$$
$$FBiggl(sum_{n=9}^{4} {(a_n)}Biggr)>0$$
$$FBiggl(sum_{n=5}^{11} {(a_n)}Biggr)>0$$
(Note that they all the sums contain 7 members; they are all therefore strictly positive).
Adding the eleven inequalities
$$0<sum_{n=1}^{7} {(a_n)}+
FBiggl(sum_{n=8}^{3} {(a_n)}Biggr)+
sum_{n=4}^{10} {(a_n)}+
FBiggl(sum_{n=11}^{6} {(a_n)}Biggr)+
FBiggl(sum_{n=7}^{2} {(a_n)}Biggr)+
sum_{n=3}^{9} {(a_n)}+
FBiggl(sum_{n=10}^{5} {(a_n)}Biggr)+
FBiggl(sum_{n=6}^{1} {(a_n)}Biggr)+
sum_{n=2}^{8} {(a_n)}+
FBiggl(sum_{n=9}^{4} {(a_n)}Biggr)+
FBiggl(sum_{n=5}^{11} {(a_n)}Biggr)=7*sum_{n=1}^{11} {(a_n)}<0$$
Which is obviously a contradiction.
Summing up, what we've done is adding seven times $sum_{n=1}^{11} {(a_n)}$. This should be strictly negative since all "$sum_{n=1}^{11} {(a_n)}$" are negative. We can, nevertheless, divide all the summands into groups of seven elements, which should be (all of them) positive, leading to the required contradiction. Note that you can repeat this process for all possible $n$.
So if your maximal $n$ is $n_{max}$, you'll have to write $d=lcm(11*7,n_{max})=lcm(77,n_{max})$ elements in order $(a_1,a_2,...,a_{n_{max}-1},a_{n–{max}},a_1,a_2,...)$ and then group them in $frac{d}{11}$ gruops with 11 elements respectively (recall that these groups have to be negative). Group them afterwares in $frac{d}{7}$ groups, such that each of them contains exactly 7 elements (these groups will be hence positive). Howver the $d$ elements can't sum a negative and a positive number at the same time (required contradiction).
$mathbf {Remark}$
This problem reminds me of the second problem of the IMO in the year 1977:
In a finite sequence of real numbers the sum of any seven successive terms is negative, and the sum of any eleven successive terms is positive. Determine the maximum number of terms in the sequence.
If you're looking for a solution, there's an easy one you might like...
Let's begin grouping the elements of the succession as follows
$$a_1quad a_2quad a_3quad a_4quad a_5quad a_6quad a_7$$
$$a_2quad a_3quad a_4quad a_5quad a_6quad a_7quad a_8$$
$$..quad ..quad ..quad ..quad ..quad ..quad ..$$
$$a_{10}quad a_{11}quad a_{12}quad a_{13}quad a_{14}quad a_{15}quad a_{16}$$
$$a_{11}quad a_{12}quad a_{13}quad a_{14}quad a_{15}quad a_{16}quad a_{17}$$
Having a closer look at this representation you might note that every line is made out of seven elements (and is hence negative) and every column is made out of eleven elements (and is therefore positive). However, the total sum can't be positive and negative at the same time, so the sequence can not contain the 17th element. It is, however, possible to form a sequence with 16 elements satisfying the conditions. For instance
$$5,5,-13,5,5,5,-13,5,5,-13,5,5,5,-13,5,5$$
In the book "International Mathematical Olympiads 1959-1977" Samuel Greitzer shows a procedure (different from the simple guessing) in order to find the given example (which was published later by the Mathematical Association of America in 1978).
However, just as Arthur Engel criticizes in his book "Problem Solving Strategies" (pg. 85 and following) "[i]deally an IMO problem should be unknown to all students. Even a similar problem should never have been discussed in any country." He claims, that the problem 118 of "Dynkin–Molchanov–Rosental– Tolpygo": Mathematical Problems, 1971, 3rd edition with 200,000 copies sold, was almost identic to this one.
Now, back to the solution, in the book "The IMO compendium" the authors offer the following solution generalizing the problem
We shall prove a stronger statement: If 7 and 11 in the question are replaced by any positive integers $m,n$ then the maximum number of terms is $m+n−(m,n)−1$.
Let $a_1,a_2,...,a_l$ be a sequence of real numbers, and let us define $s_0 = 0$ and $s_k = a_1 +···+a_k quad (k = 1,...,l)$. The given conditions are equivalent to $s_k >s_{k+m}$ for $0≤k≤l−m$ and $s_k <s_{k+n}$ for $0≤k≤l−n$.
Let $d = (m,n)$ and $m = m'd,; n = n'd$. Suppose that there exists a sequence $(a_k )$ of length greater than or equal to $l = m + n − d$ satisfying the required conditions. Then the $m' +n'$ numbers $s_0,s_d,...,s_{(m'+n'−1)d}$ satisfy $n'$ inequalities $s_{k+m} < s_{k}$ and $m'$ inequalities $s_{k} < s_{k+n}$. Moreover, each term $s_{kd}$ appears twice in these inequalities: once on the left-hand and once on the right-hand side. It follows that there exists a ring of inequalities $s_{i_1} < s_{i_2} < · · · < s_{i_k}< s_{i_1}$ , giving a contradiction.
On the other hand, suppose that such a ring of inequalities can be made also for $l=m+n−d−1$, say $s_{i_1} <s_{i_2} <···<s_{i_k} <s_{i_1}$. If there are $p$ inequalities of the form $a_{k+m} < a_{k}$ and $q$ inequalities of the form $a_{k+n} >a_k$ in the ring,then $qn=rm$, which implies $m'mid q,quad n'mid p$ and thus $k = p + q ≥ m' + n'$. But since all $i_1,i_2,...,i_k$ are congruent modulo $d$, we have $k ≤ m' + n' − 1$, a contradiction. Hence there exists a sequence of length $m + n − d − 1$ with the required property.
This second solution was offered in the IMO by John Rickard, from the UK, who received a special price for such an original approach.
answered Nov 21 '18 at 20:19
Dr. Mathva
921316
add a comment |
Let $A=text{a_1, a_2, ...}$ be the set you're looking for.
Since the sum of any 11 numbers from this set is strictly negative, it must contain at least 11 elements, so suppose this is the case
$$sum_{n=1}^{11} {(a_n)}<0$$
$$Rightarrow7*sum_{n=1}^{11} {(a_n)}<0$$
Denote now by $$FBiggl(sum_{n=8}^{3} {(a_n)}Biggr)$$the sum $$a_8+a_9+a_{10}+a_{11}+a_1+a_2+a_3$$ (Note that after the element $a_{11}$ we start again with ${a_1}$)
Thus
$$sum_{n=1}^{7} {(a_n)}>0$$
$$FBiggl(sum_{n=8}^{3} {(a_n)}Biggr)>0$$
$$sum_{n=4}^{10} {(a_n)}>0$$
$$FBiggl(sum_{n=11}^{6} {(a_n)}Biggr)>0$$
$$FBiggl(sum_{n=7}^{2} {(a_n)}Biggr)>0$$
$$sum_{n=3}^{9} {(a_n)}>0$$
$$FBiggl(sum_{n=10}^{5} {(a_n)}Biggr)>0$$
$$FBiggl(sum_{n=6}^{1} {(a_n)}Biggr)>0$$
$$sum_{n=2}^{8} {(a_n)}>0$$
$$FBiggl(sum_{n=9}^{4} {(a_n)}Biggr)>0$$
$$FBiggl(sum_{n=5}^{11} {(a_n)}Biggr)>0$$
(Note that they all the sums contain 7 members; they are all therefore strictly positive).
Adding the eleven inequalities
$$0<sum_{n=1}^{7} {(a_n)}+
FBiggl(sum_{n=8}^{3} {(a_n)}Biggr)+
sum_{n=4}^{10} {(a_n)}+
FBiggl(sum_{n=11}^{6} {(a_n)}Biggr)+
FBiggl(sum_{n=7}^{2} {(a_n)}Biggr)+
sum_{n=3}^{9} {(a_n)}+
FBiggl(sum_{n=10}^{5} {(a_n)}Biggr)+
FBiggl(sum_{n=6}^{1} {(a_n)}Biggr)+
sum_{n=2}^{8} {(a_n)}+
FBiggl(sum_{n=9}^{4} {(a_n)}Biggr)+
FBiggl(sum_{n=5}^{11} {(a_n)}Biggr)=7*sum_{n=1}^{11} {(a_n)}<0$$
Which is obviously a contradiction.
Summing up, what we've done is adding seven times $sum_{n=1}^{11} {(a_n)}$. This should be strictly negative since all "$sum_{n=1}^{11} {(a_n)}$" are negative. We can, nevertheless, divide all the summands into groups of seven elements, which should be (all of them) positive, leading to the required contradiction. Note that you can repeat this process for all possible $n$.
So if your maximal $n$ is $n_{max}$, you'll have to write $d=lcm(11*7,n_{max})=lcm(77,n_{max})$ elements in order $(a_1,a_2,...,a_{n_{max}-1},a_{n–{max}},a_1,a_2,...)$ and then group them in $frac{d}{11}$ gruops with 11 elements respectively (recall that these groups have to be negative). Group them afterwares in $frac{d}{7}$ groups, such that each of them contains exactly 7 elements (these groups will be hence positive). Howver the $d$ elements can't sum a negative and a positive number at the same time (required contradiction).
$mathbf {Remark}$
This problem reminds me of the second problem of the IMO in the year 1977:
In a finite sequence of real numbers the sum of any seven successive terms is negative, and the sum of any eleven successive terms is positive. Determine the maximum number of terms in the sequence.
If you're looking for a solution, there's an easy one you might like...
Let's begin grouping the elements of the succession as follows
$$a_1quad a_2quad a_3quad a_4quad a_5quad a_6quad a_7$$
$$a_2quad a_3quad a_4quad a_5quad a_6quad a_7quad a_8$$
$$..quad ..quad ..quad ..quad ..quad ..quad ..$$
$$a_{10}quad a_{11}quad a_{12}quad a_{13}quad a_{14}quad a_{15}quad a_{16}$$
$$a_{11}quad a_{12}quad a_{13}quad a_{14}quad a_{15}quad a_{16}quad a_{17}$$
Having a closer look at this representation you might note that every line is made out of seven elements (and is hence negative) and every column is made out of eleven elements (and is therefore positive). However, the total sum can't be positive and negative at the same time, so the sequence can not contain the 17th element. It is, however, possible to form a sequence with 16 elements satisfying the conditions. For instance
$$5,5,-13,5,5,5,-13,5,5,-13,5,5,5,-13,5,5$$
In the book "International Mathematical Olympiads 1959-1977" Samuel Greitzer shows a procedure (different from the simple guessing) in order to find the given example (which was published later by the Mathematical Association of America in 1978).
However, just as Arthur Engel criticizes in his book "Problem Solving Strategies" (pg. 85 and following) "[i]deally an IMO problem should be unknown to all students. Even a similar problem should never have been discussed in any country." He claims, that the problem 118 of "Dynkin–Molchanov–Rosental– Tolpygo": Mathematical Problems, 1971, 3rd edition with 200,000 copies sold, was almost identic to this one.
Now, back to the solution, in the book "The IMO compendium" the authors offer the following solution generalizing the problem
We shall prove a stronger statement: If 7 and 11 in the question are replaced by any positive integers $m,n$ then the maximum number of terms is $m+n−(m,n)−1$.
Let $a_1,a_2,...,a_l$ be a sequence of real numbers, and let us define $s_0 = 0$ and $s_k = a_1 +···+a_k quad (k = 1,...,l)$. The given conditions are equivalent to $s_k >s_{k+m}$ for $0≤k≤l−m$ and $s_k <s_{k+n}$ for $0≤k≤l−n$.
Let $d = (m,n)$ and $m = m'd,; n = n'd$. Suppose that there exists a sequence $(a_k )$ of length greater than or equal to $l = m + n − d$ satisfying the required conditions. Then the $m' +n'$ numbers $s_0,s_d,...,s_{(m'+n'−1)d}$ satisfy $n'$ inequalities $s_{k+m} < s_{k}$ and $m'$ inequalities $s_{k} < s_{k+n}$. Moreover, each term $s_{kd}$ appears twice in these inequalities: once on the left-hand and once on the right-hand side. It follows that there exists a ring of inequalities $s_{i_1} < s_{i_2} < · · · < s_{i_k}< s_{i_1}$ , giving a contradiction.
On the other hand, suppose that such a ring of inequalities can be made also for $l=m+n−d−1$, say $s_{i_1} <s_{i_2} <···<s_{i_k} <s_{i_1}$. If there are $p$ inequalities of the form $a_{k+m} < a_{k}$ and $q$ inequalities of the form $a_{k+n} >a_k$ in the ring,then $qn=rm$, which implies $m'mid q,quad n'mid p$ and thus $k = p + q ≥ m' + n'$. But since all $i_1,i_2,...,i_k$ are congruent modulo $d$, we have $k ≤ m' + n' − 1$, a contradiction. Hence there exists a sequence of length $m + n − d − 1$ with the required property.
This second solution was offered in the IMO by John Rickard, from the UK, who received a special price for such an original approach.
answered Nov 21 '18 at 20:19
Dr. Mathva
921316
add a comment |
Let $A=text{a_1, a_2, ...}$ be the set you're looking for.
Since the sum of any 11 numbers from this set is strictly negative, it must contain at least 11 elements, so suppose this is the case
$$sum_{n=1}^{11} {(a_n)}<0$$
$$Rightarrow7*sum_{n=1}^{11} {(a_n)}<0$$
Denote now by $$FBiggl(sum_{n=8}^{3} {(a_n)}Biggr)$$the sum $$a_8+a_9+a_{10}+a_{11}+a_1+a_2+a_3$$ (Note that after the element $a_{11}$ we start again with ${a_1}$)
Thus
$$sum_{n=1}^{7} {(a_n)}>0$$
$$FBiggl(sum_{n=8}^{3} {(a_n)}Biggr)>0$$
$$sum_{n=4}^{10} {(a_n)}>0$$
$$FBiggl(sum_{n=11}^{6} {(a_n)}Biggr)>0$$
$$FBiggl(sum_{n=7}^{2} {(a_n)}Biggr)>0$$
$$sum_{n=3}^{9} {(a_n)}>0$$
$$FBiggl(sum_{n=10}^{5} {(a_n)}Biggr)>0$$
$$FBiggl(sum_{n=6}^{1} {(a_n)}Biggr)>0$$
$$sum_{n=2}^{8} {(a_n)}>0$$
$$FBiggl(sum_{n=9}^{4} {(a_n)}Biggr)>0$$
$$FBiggl(sum_{n=5}^{11} {(a_n)}Biggr)>0$$
(Note that they all the sums contain 7 members; they are all therefore strictly positive).
Adding the eleven inequalities
$$0<sum_{n=1}^{7} {(a_n)}+
FBiggl(sum_{n=8}^{3} {(a_n)}Biggr)+
sum_{n=4}^{10} {(a_n)}+
FBiggl(sum_{n=11}^{6} {(a_n)}Biggr)+
FBiggl(sum_{n=7}^{2} {(a_n)}Biggr)+
sum_{n=3}^{9} {(a_n)}+
FBiggl(sum_{n=10}^{5} {(a_n)}Biggr)+
FBiggl(sum_{n=6}^{1} {(a_n)}Biggr)+
sum_{n=2}^{8} {(a_n)}+
FBiggl(sum_{n=9}^{4} {(a_n)}Biggr)+
FBiggl(sum_{n=5}^{11} {(a_n)}Biggr)=7*sum_{n=1}^{11} {(a_n)}<0$$
Which is obviously a contradiction.
Summing up, what we've done is adding seven times $sum_{n=1}^{11} {(a_n)}$. This should be strictly negative since all "$sum_{n=1}^{11} {(a_n)}$" are negative. We can, nevertheless, divide all the summands into groups of seven elements, which should be (all of them) positive, leading to the required contradiction. Note that you can repeat this process for all possible $n$.
So if your maximal $n$ is $n_{max}$, you'll have to write $d=lcm(11*7,n_{max})=lcm(77,n_{max})$ elements in order $(a_1,a_2,...,a_{n_{max}-1},a_{n–{max}},a_1,a_2,...)$ and then group them in $frac{d}{11}$ gruops with 11 elements respectively (recall that these groups have to be negative). Group them afterwares in $frac{d}{7}$ groups, such that each of them contains exactly 7 elements (these groups will be hence positive). Howver the $d$ elements can't sum a negative and a positive number at the same time (required contradiction).
$mathbf {Remark}$
This problem reminds me of the second problem of the IMO in the year 1977:
In a finite sequence of real numbers the sum of any seven successive terms is negative, and the sum of any eleven successive terms is positive. Determine the maximum number of terms in the sequence.
If you're looking for a solution, there's an easy one you might like...
Let's begin grouping the elements of the succession as follows
$$a_1quad a_2quad a_3quad a_4quad a_5quad a_6quad a_7$$
$$a_2quad a_3quad a_4quad a_5quad a_6quad a_7quad a_8$$
$$..quad ..quad ..quad ..quad ..quad ..quad ..$$
$$a_{10}quad a_{11}quad a_{12}quad a_{13}quad a_{14}quad a_{15}quad a_{16}$$
$$a_{11}quad a_{12}quad a_{13}quad a_{14}quad a_{15}quad a_{16}quad a_{17}$$
Having a closer look at this representation you might note that every line is made out of seven elements (and is hence negative) and every column is made out of eleven elements (and is therefore positive). However, the total sum can't be positive and negative at the same time, so the sequence can not contain the 17th element. It is, however, possible to form a sequence with 16 elements satisfying the conditions. For instance
$$5,5,-13,5,5,5,-13,5,5,-13,5,5,5,-13,5,5$$
In the book "International Mathematical Olympiads 1959-1977" Samuel Greitzer shows a procedure (different from the simple guessing) in order to find the given example (which was published later by the Mathematical Association of America in 1978).
However, just as Arthur Engel criticizes in his book "Problem Solving Strategies" (pg. 85 and following) "[i]deally an IMO problem should be unknown to all students. Even a similar problem should never have been discussed in any country." He claims, that the problem 118 of "Dynkin–Molchanov–Rosental– Tolpygo": Mathematical Problems, 1971, 3rd edition with 200,000 copies sold, was almost identic to this one.
Now, back to the solution, in the book "The IMO compendium" the authors offer the following solution generalizing the problem
We shall prove a stronger statement: If 7 and 11 in the question are replaced by any positive integers $m,n$ then the maximum number of terms is $m+n−(m,n)−1$.
Let $a_1,a_2,...,a_l$ be a sequence of real numbers, and let us define $s_0 = 0$ and $s_k = a_1 +···+a_k quad (k = 1,...,l)$. The given conditions are equivalent to $s_k >s_{k+m}$ for $0≤k≤l−m$ and $s_k <s_{k+n}$ for $0≤k≤l−n$.
Let $d = (m,n)$ and $m = m'd,; n = n'd$. Suppose that there exists a sequence $(a_k )$ of length greater than or equal to $l = m + n − d$ satisfying the required conditions. Then the $m' +n'$ numbers $s_0,s_d,...,s_{(m'+n'−1)d}$ satisfy $n'$ inequalities $s_{k+m} < s_{k}$ and $m'$ inequalities $s_{k} < s_{k+n}$. Moreover, each term $s_{kd}$ appears twice in these inequalities: once on the left-hand and once on the right-hand side. It follows that there exists a ring of inequalities $s_{i_1} < s_{i_2} < · · · < s_{i_k}< s_{i_1}$ , giving a contradiction.
On the other hand, suppose that such a ring of inequalities can be made also for $l=m+n−d−1$, say $s_{i_1} <s_{i_2} <···<s_{i_k} <s_{i_1}$. If there are $p$ inequalities of the form $a_{k+m} < a_{k}$ and $q$ inequalities of the form $a_{k+n} >a_k$ in the ring,then $qn=rm$, which implies $m'mid q,quad n'mid p$ and thus $k = p + q ≥ m' + n'$. But since all $i_1,i_2,...,i_k$ are congruent modulo $d$, we have $k ≤ m' + n' − 1$, a contradiction. Hence there exists a sequence of length $m + n − d − 1$ with the required property.
This second solution was offered in the IMO by John Rickard, from the UK, who received a special price for such an original approach.
answered Nov 21 '18 at 20:19
Dr. Mathva
921316
Let $A=text{a_1, a_2, ...}$ be the set you're looking for.
Since the sum of any 11 numbers from this set is strictly negative, it must contain at least 11 elements, so suppose this is the case
$$sum_{n=1}^{11} {(a_n)}<0$$
$$Rightarrow7*sum_{n=1}^{11} {(a_n)}<0$$
Denote now by $$FBiggl(sum_{n=8}^{3} {(a_n)}Biggr)$$the sum $$a_8+a_9+a_{10}+a_{11}+a_1+a_2+a_3$$ (Note that after the element $a_{11}$ we start again with ${a_1}$)
Thus
$$sum_{n=1}^{7} {(a_n)}>0$$
$$FBiggl(sum_{n=8}^{3} {(a_n)}Biggr)>0$$
$$sum_{n=4}^{10} {(a_n)}>0$$
$$FBiggl(sum_{n=11}^{6} {(a_n)}Biggr)>0$$
$$FBiggl(sum_{n=7}^{2} {(a_n)}Biggr)>0$$
$$sum_{n=3}^{9} {(a_n)}>0$$
$$FBiggl(sum_{n=10}^{5} {(a_n)}Biggr)>0$$
$$FBiggl(sum_{n=6}^{1} {(a_n)}Biggr)>0$$
$$sum_{n=2}^{8} {(a_n)}>0$$
$$FBiggl(sum_{n=9}^{4} {(a_n)}Biggr)>0$$
$$FBiggl(sum_{n=5}^{11} {(a_n)}Biggr)>0$$
(Note that they all the sums contain 7 members; they are all therefore strictly positive).
Adding the eleven inequalities
$$0<sum_{n=1}^{7} {(a_n)}+
FBiggl(sum_{n=8}^{3} {(a_n)}Biggr)+
sum_{n=4}^{10} {(a_n)}+
FBiggl(sum_{n=11}^{6} {(a_n)}Biggr)+
FBiggl(sum_{n=7}^{2} {(a_n)}Biggr)+
sum_{n=3}^{9} {(a_n)}+
FBiggl(sum_{n=10}^{5} {(a_n)}Biggr)+
FBiggl(sum_{n=6}^{1} {(a_n)}Biggr)+
sum_{n=2}^{8} {(a_n)}+
FBiggl(sum_{n=9}^{4} {(a_n)}Biggr)+
FBiggl(sum_{n=5}^{11} {(a_n)}Biggr)=7*sum_{n=1}^{11} {(a_n)}<0$$
Which is obviously a contradiction.
Summing up, what we've done is adding seven times $sum_{n=1}^{11} {(a_n)}$. This should be strictly negative since all "$sum_{n=1}^{11} {(a_n)}$" are negative. We can, nevertheless, divide all the summands into groups of seven elements, which should be (all of them) positive, leading to the required contradiction. Note that you can repeat this process for all possible $n$.
So if your maximal $n$ is $n_{max}$, you'll have to write $d=lcm(11*7,n_{max})=lcm(77,n_{max})$ elements in order $(a_1,a_2,...,a_{n_{max}-1},a_{n–{max}},a_1,a_2,...)$ and then group them in $frac{d}{11}$ gruops with 11 elements respectively (recall that these groups have to be negative). Group them afterwares in $frac{d}{7}$ groups, such that each of them contains exactly 7 elements (these groups will be hence positive). Howver the $d$ elements can't sum a negative and a positive number at the same time (required contradiction).
$mathbf {Remark}$
This problem reminds me of the second problem of the IMO in the year 1977:
In a finite sequence of real numbers the sum of any seven successive terms is negative, and the sum of any eleven successive terms is positive. Determine the maximum number of terms in the sequence.
If you're looking for a solution, there's an easy one you might like...
Let's begin grouping the elements of the succession as follows
$$a_1quad a_2quad a_3quad a_4quad a_5quad a_6quad a_7$$
$$a_2quad a_3quad a_4quad a_5quad a_6quad a_7quad a_8$$
$$..quad ..quad ..quad ..quad ..quad ..quad ..$$
$$a_{10}quad a_{11}quad a_{12}quad a_{13}quad a_{14}quad a_{15}quad a_{16}$$
$$a_{11}quad a_{12}quad a_{13}quad a_{14}quad a_{15}quad a_{16}quad a_{17}$$
Having a closer look at this representation you might note that every line is made out of seven elements (and is hence negative) and every column is made out of eleven elements (and is therefore positive). However, the total sum can't be positive and negative at the same time, so the sequence can not contain the 17th element. It is, however, possible to form a sequence with 16 elements satisfying the conditions. For instance
$$5,5,-13,5,5,5,-13,5,5,-13,5,5,5,-13,5,5$$
In the book "International Mathematical Olympiads 1959-1977" Samuel Greitzer shows a procedure (different from the simple guessing) in order to find the given example (which was published later by the Mathematical Association of America in 1978).
However, just as Arthur Engel criticizes in his book "Problem Solving Strategies" (pg. 85 and following) "[i]deally an IMO problem should be unknown to all students. Even a similar problem should never have been discussed in any country." He claims, that the problem 118 of "Dynkin–Molchanov–Rosental– Tolpygo": Mathematical Problems, 1971, 3rd edition with 200,000 copies sold, was almost identic to this one.
Now, back to the solution, in the book "The IMO compendium" the authors offer the following solution generalizing the problem
We shall prove a stronger statement: If 7 and 11 in the question are replaced by any positive integers $m,n$ then the maximum number of terms is $m+n−(m,n)−1$.
Let $a_1,a_2,...,a_l$ be a sequence of real numbers, and let us define $s_0 = 0$ and $s_k = a_1 +···+a_k quad (k = 1,...,l)$. The given conditions are equivalent to $s_k >s_{k+m}$ for $0≤k≤l−m$ and $s_k <s_{k+n}$ for $0≤k≤l−n$.
Let $d = (m,n)$ and $m = m'd,; n = n'd$. Suppose that there exists a sequence $(a_k )$ of length greater than or equal to $l = m + n − d$ satisfying the required conditions. Then the $m' +n'$ numbers $s_0,s_d,...,s_{(m'+n'−1)d}$ satisfy $n'$ inequalities $s_{k+m} < s_{k}$ and $m'$ inequalities $s_{k} < s_{k+n}$. Moreover, each term $s_{kd}$ appears twice in these inequalities: once on the left-hand and once on the right-hand side. It follows that there exists a ring of inequalities $s_{i_1} < s_{i_2} < · · · < s_{i_k}< s_{i_1}$ , giving a contradiction.
On the other hand, suppose that such a ring of inequalities can be made also for $l=m+n−d−1$, say $s_{i_1} <s_{i_2} <···<s_{i_k} <s_{i_1}$. If there are $p$ inequalities of the form $a_{k+m} < a_{k}$ and $q$ inequalities of the form $a_{k+n} >a_k$ in the ring,then $qn=rm$, which implies $m'mid q,quad n'mid p$ and thus $k = p + q ≥ m' + n'$. But since all $i_1,i_2,...,i_k$ are congruent modulo $d$, we have $k ≤ m' + n' − 1$, a contradiction. Hence there exists a sequence of length $m + n − d − 1$ with the required property.
This second solution was offered in the IMO by John Rickard, from the UK, who received a special price for such an original approach.
answered Nov 21 '18 at 20:19
Dr. Mathva
921316
edited Nov 21 '18 at 22:22
answered Nov 21 '18 at 20:19
Dr. Mathva
921316
answered Nov 21 '18 at 20:19
Dr. Mathva
921316
answered Nov 21 '18 at 20:19
Dr. Mathva
921316
921316
add a comment |
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3008035%2fsmallest-size-of-set-of-real-numbers-such-that-the-sum-of-any-seven-is-strictly%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
