14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why do you stop at 2016? $\endgroup$ – Ed Pegg Jan 1 at 3:35
  • 1
    $\begingroup$ @EdPegg that's just how the problem is given to me. Don't mind any other numbers.. doubt it makes a difference. $\endgroup$ – Vlad Zkov Jan 1 at 3:36
  • $\begingroup$ @EdPegg the problem was most likely from a competition held in 2016. $\endgroup$ – Soham Konar Jan 1 at 3:37
  • $\begingroup$ 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. $\endgroup$ – Soham Konar Jan 1 at 3:39
  • $\begingroup$ Is there really a product of the numbers $184, 183,183$ (and of the $a$-numbers)...?! $\endgroup$ – dan_fulea Jan 1 at 3:59
8
$\begingroup$

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
$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.