# How many numbers can we select from $\{1,2,…2016\}$ such that sum of any four of them cannot be divided by $11$

How many numbers can we select from $$\{1,2, \ldots, 2016\}$$ such that sum of any four of them cannot be divided by $$11$$

It's not hard to come up with some combinations, but the question is how to prove it's the largest set.

For example if we select numbers in forms of $$11N+1,11N+4,11N+9$$ will yield us $$184 + 183 + 183$$ numbers.

it looks like proof will be somewhat of an inequalities problem. Let $$a_{i_0}, a_{i_1}, \ldots, a_{i_k} > 0$$ be the count of numbers we select from each modulo class, and we want to maximize $$a_{i_0} + a_{i_1} + \cdots + a_{i_k}$$ But how to express the constraint is tricky.

• Why do you stop at 2016? – Ed Pegg Jan 1 at 3:35
• @EdPegg that's just how the problem is given to me. Don't mind any other numbers.. doubt it makes a difference. – Vlad Zkov Jan 1 at 3:36
• @EdPegg the problem was most likely from a competition held in 2016. – Soham Konar Jan 1 at 3:37
• The forms of this problem that I see in math competitions usually ask for the sum of only two elements instead of four, so I'm not sure how to do this one other than meticulous casework. – Soham Konar Jan 1 at 3:39
• Is there really a product of the numbers $184, 183,183$ (and of the $a$-numbers)...?! – dan_fulea Jan 1 at 3:59

We already have a solution with $$184+183+183$$ numbers. We only search a better solution. Let $$S$$ be such a solution, a subset of $$\{1,2,\dots,2016\}$$. We will place the numbers in $$S$$ in bins w.r.t. the congruence modulo $$11$$. There will be at least $$3$$ bins with more than four numbers. (Else we have at most $$184+184+9\cdot 3$$ numbers in $$S$$, not a better solution.) Let us make a choice of three such bins (among a potentially bigger number of them), and denote them by $$a,b,c\in\Bbb Z/11$$, according to the congruence modulo eleven of the numbers in them, respectively. Let us search for all possible such triples $$(a,b,c)$$, ordered w.r.t. to the order inherited from the natural order of $$0,1,2,3,4,5,6,7,8,9,10,11$$. We know that $$ka+lb+mc\ne 0\in\Bbb Z/11\ ,\qquad\text{ for all }k,l,m\in\{0,1,2,3,4\}\ ,\ k+l+m=4\ .$$ So $$a,b,c\ne0$$. After a multiplication with $$a^{-1}$$ modulo $$11$$ we obtain a triple $$A,B,C$$ with the same property, but $$A=1$$ is normed. Which are the possibilities for $$B,C$$? The values $$7,8,10$$ are forbidden. (Since $$3\cdot 1+8=11\equiv 0$$, and $$2\cdot 1+2\cdot 10=22\equiv 0$$, and $$3\cdot 7+1=22\equiv 0$$, congruences being here and below modulo eleven.)

There remain only the cases $$B,C\in\{2,3,4,5,6,9\}$$. We assume $$B\le C$$.

• If $$B=2$$, then we can not find a convenient $$\color{red}C$$, since $$0 \equiv 0\cdot 1+1\cdot 2+3\cdot \color{red}3 \equiv 1\cdot 1+1\cdot 2+2\cdot \color{red}4 \equiv 0\cdot 1+3\cdot 2+1\cdot \color{red}5 \equiv 1\cdot 1+2\cdot 2+1\cdot \color{red}6 \equiv 0\cdot 1+2\cdot 2+2\cdot \color{red}9$$.

• If $$B=3$$, then $$\color{red}C=5$$ is only possible, since $$0 \equiv 1\cdot 1+2\cdot 3+1\cdot \color{red}4 \equiv 2\cdot 1+1\cdot 3+1\cdot \color{red}6 \equiv 1\cdot 1+1\cdot 3+2\cdot \color{red}9$$.

• If $$B=4$$, then $$\color{red}C=9$$ is only possible, since $$0 \equiv 2\cdot 1+1\cdot 4+1\cdot \color{red}5 \equiv 0\cdot 1+1\cdot 4+3\cdot \color{red}6$$.

• If $$B=5$$, then $$\color{red}C=9$$ is only possible, since $$0 \equiv 0\cdot 1+2\cdot 5+2\cdot \color{red}6$$.

• If $$B=6$$, then there is no suitable $$\color{red}C$$, since $$0 \equiv 0\cdot 1+1\cdot 6+3\cdot \color{red}9$$.

So far we have only the possible values for $$(A,B,C)$$ from the list: $$(1,3,5)\ ,\ (1,4,9)\ ,\ (1,5,9)\ .$$ In fact, the three cases are up to multiplication with an element in $$(\Bbb Z/11)^\times$$ one case, since

• $$4\cdot (1,3,5)=(4,12,20)\equiv (4,1,9)$$ corresponding to the case $$(A,B,C)=(1,4,9)$$, and
• $$9\cdot (1,3,5)=(9,27,45)\equiv (9,5,1)$$ corresponding to the case $$(A,B,C)=(1,5,9)$$.

Let us observe now that we cannot add one more non-empty bin, and still have no contradiction, except for the case of the $$10$$-bin containing at most one element. It is enough to do this with the triple $$(1,3,5)$$.

• adding $$\color{blue}0$$: Use $$0\equiv1\cdot\color{blue}0 + 0\cdot 1+2\cdot 3+1\cdot 5$$.
• adding $$\color{blue}2$$: Use $$0\equiv1\cdot\color{blue}2 + 0\cdot 1+3\cdot 3+0\cdot 5$$.
• adding $$\color{blue}4$$: Use $$0\equiv1\cdot\color{blue}4 + 1\cdot 1+2\cdot 3+0\cdot 5$$.
• adding $$\color{blue}6$$: Use $$0\equiv1\cdot\color{blue}6 + 2\cdot 1+1\cdot 3+0\cdot 5$$.
• adding $$\color{blue}7$$: Use $$0\equiv1\cdot\color{blue}7 + 0\cdot 1+0\cdot 3+3\cdot 5$$.
• adding $$\color{blue}8$$: Use $$0\equiv1\cdot\color{blue}8 + 3\cdot 1+0\cdot 3+0\cdot 5$$.
• adding $$\color{blue}9$$: Use $$0\equiv1\cdot\color{blue}9 + 0\cdot 1+1\cdot 3+2\cdot 5$$.
• adding $$\color{green}10$$: Does not lead to a contradiction. But note that we cannot have more than one number in this bin. Else $$0\equiv2\cdot\color{blue}{10} + 2\cdot 1+0\cdot 3+0\cdot 5$$.

Now all ten cases $$(a,b,c)$$ that can be obtained from $$(A,B,C)=(1,3,5)$$ by multiplying with a unit modulo $$11$$, and rearranging, are: \begin{aligned} &(1, 3, 5)\\ &(1, 4, 9)\\ &(1, 5, 9)\\ &(2, 6, 10)\\ &(2, 7, 8)\\ &(2, 7, 10)\\ &(3, 4, 5)\\ &(3, 4, 9)\\ &(6, 7, 8)\\ &(6, 8, 10)\ . \end{aligned} Let us see how we can profit from them, given that $$2013/11=183$$, so there are $$184$$ elements in the classes $$1,2,3$$, and $$183$$ elements in the classes $$4,5,6,7,8,9,10,0$$ among the numbers from $$1$$ to $$2016$$.

Only one case, the case $$(1,3,5)$$ contains two classes from the "richer" classes, so this is our optimal choice. There is also the possibility to add one element of the class $$10$$. So one optimal $$S$$ is realized for $$S=S^*_{10}$$ with $$S^*_{10}= \underbrace{\{1,12,\dots,2014\}}_{184\text{ elements}}\cup \underbrace{\{3,15,\dots,2016\}}_{184\text{ elements}}\cup \underbrace{\{5,16,\dots,2007\}}_{183\text{ elements}}\cup \{10\} \ .$$ All other optimal possibilities are obtained from the above by replacing the $$10$$ with an element $$k$$ in its class.

Here are some compute checks using sage:

First of all, the given solution is a solution (in a lazy implementation):

R = IntegerModRing(11)
a, b, c, d = R(1), R(3), R(5), R(10)
def test_solution():
for k, l, m, n in cartesian_product([[0..4], [0..4], [0..4], [0..1]]):
if k + l + m + n != 4:
continue
if k*a + l*b + m*c + n*d == R(0):
print "*** No solution: ", k, l, m, n
return
print "OK"

test_solution()


It delivers the wanted OK.

Here is also a piece of code delivering all possible triples $$(a,b,c)$$:

R = IntegerModRing(11)

def test_triple(a, b, c):
for k, l, m in cartesian_product([[0..4], [0..4], [0..4]]):
if k + l + m != 4:
continue
if k*a + l*b + m*c == R(0):
# print "*** No solution: ", k, l, m
return False
return True

for a, b, c in Combinations(R, 3):
if test_triple(a, b, c):
print a, b, c


And we get:

1 3 5
1 4 9
1 5 9
2 6 10
2 7 8
2 7 10
3 4 5
3 4 9
6 7 8
6 8 10


You can solve the problem via integer linear programming as follows. For $$j \in \{1,\dots,2016\}$$, let binary decision variable $$x_j$$ indicate whether $$j$$ is selected. The problem is to maximize $$\sum_j x_j$$ subject to linear constraints: $$x_{j_1} + x_{j_2} + x_{j_3} + x_{j_4} \le 3$$ for all quadruples $$j_1 with $$j_1+j_2+j_3+j_4 \equiv 0 \pmod{11}$$. That is too large to solve directly, but maybe you can reduce the problem size by aggregating variables from the same equivalence class.

Edit: An alternative integer linear programming formulation uses binary variables $$y_{k,c}$$ to indicate whether equivalence class $$k\in\{0,\dots,10\}$$ has $$c$$ members selected. The objective is to maximize $$\sum_{k,c} c\cdot y_{k,c}$$, and the constraints are $$\sum_c y_{k,c} = 1$$ for each $$k$$, and 91 others of the form $$\sum_{k,c} y_{k,c} \le b,$$ where $$b \in \{0,1,2,3\}$$. For example, forbidden quadruple $$(2,6,6,8)$$ of equivalence classes corresponds to linear constraint $$\sum_{c \ge 1} y_{2,c} + \sum_{c \ge 2} y_{6,c} + \sum_{c \ge 1} y_{8,c} \le 2.$$ Equivalently, $$y_{2,0} + \sum_{c=0}^1 y_{6,c} + y_{8,0} \ge 1.$$ The resulting problem has 2027 variables and 102 constraints, and the optimal objective value is 552, in agreement with @dan_fulea.