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.

Solution 1:

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

Solution 2:

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<j_2<j_3<j_4$ 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.