Htykuut

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)

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.

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.