Danny's subsets

$\quad$ We will find the maximum size of $B$ such that no pairs of elements sum to a multiple of $61.$ Consider the residues mod $61$ of all elements of $A$ : $0, 1, 2, \ldots, 60, 61.$ We have $2013/61 = 33,$ so there are $33$ elements of each residue in $A.$

$\quad$ First consider the elements of $A$ that are $0 \pmod{61}.$ We can't include more than one of these elements, since then pairs of those elements would sum to a multiple of $61.$

$\quad$ Next consider the $60$ residues not including $0.$ We can't include both a residue of $1$ and a residue of $60,$ because $1 + 60 \equiv 0.$ Similarly, we can't include both a $2$ and a $59,$ a $3$ and a $58, ...,$ a $30$ and a $31.$ So, we can include at most half of the $60$ residues in $B,$ because including one residue rules out another. That means we can include all of $33$ numbers of $30$ residues, so we can include at most $33 \cdot 30 = 990$ of these elements of $A.$

$\quad$ Therefore, the maximum possible size of $B$ such that no pairs sum to multiples of $61$ is $1 + 990 = 991.$ All sets $B$ with size $\boxed{992}$ or more must contain a pair whose sum is a multiple of $61.$

The answer to the problem is one more than the answer to this question, which we will consider instead: Find the largest integer $n$ such that any subset $B \subset A$ with $|B| \ge n$ contains at least one pair of distinct numbers whose sum is a multiple of $61$ .

We would then try to maximise the cardinality of B without having two that have sum of 61.

Since $2013=(61)(33)$ , there are $31$ elements in $A$ that are congruent to $0 mod 61, 1 mod 61, ..., 60 mod 61$ .

If we have $2$ elements in $A$ such that one is congruent to $n mod 61$ while the other is congruent to $61-n mod 61$ , their sum would be a multiple of $61$ .

We separate the elements of $A$ that are multiples of $61$ then group them such that each group has all of the elements that are congruent to $n mod 61$ and $(61-n) mod 61$ for $1 \le n \le 30$ . In each set, there are at most $33$ that could be put into B without having two whose sum is a multiple of 61, because we cannot have at least one of both remainders.

Also, there is at most 1 multiple of 61, otherwise the sum of the 2 multiples of 61 would be a multiple of 61.

Hence there are at most $(33)(30)+1=991$ elements. Since the answer to this problem is 1 more than the answer to the question I gave, the answer is $\boxed{992}$ .

We will show that the answer is $n = \fbox{992} = 30\cdot 33 + 2$ . We will do that by first showing that any set $B$ that does not have the desired property must contain at most 991 elements, and then showing such a set $B$ with exactly 991 elements.

We have $2013 = 61 \cdot 33$ , so for each possible remainder modulo 61 the set $A$ contains 33 such integers. Let $A_i = \{ x : x\in A \land x\bmod 61 = i \}$ .

Suppose that $B$ does not contain a pair of distinct numbers whose sum is a multiple of 61.

For each $i$ from 1 to 30, inclusive, we can make the following argument: If $B \cap A_i$ is nonempty, $B\cap A_{61-i}$ must be empty and vice versa. Thus $B$ may contain at most 33 elements from $A_i \cup A_{61-i}$ .

Additionally (and this is a small catch in the task!) the set $B$ may contain at most one element from $A_0$ : two such elements form a contradiction, but one does not.

The above upper bound on the size of $B$ can now easily be extended to find such a set $B$ of maximum size. For example, the set $B = \{61\} \cup A_1 \cup \dots \cup A_{30}$ has $1 + 30\cdot 33 = 991$ elements and it clearly does not contain two distinct numbers that sum up to a multiple of 61, q.e.d.

Note that $\lvert A \rvert = 2013$ and $2013 = 61 \cdot 33$ , so for any $m \in \mathbb{Z}_{61}$ , there are exactly $33$ elements $k$ of $A$ that satisfy

$k \equiv m \pmod{61}.$

Note that if $B$ contains all elements $k$ of $A$ that satisfy

$k \equiv m \pmod{61} \quad \text{ with } 1 \leq m \leq 30$

and one element that is divisible by $61$ , then there is no pair of elements of $B$ of which the sum is divisible by $61$ . So, $n > 33 \cdot 30 + 1 = 991$ .

Let's assume there is a subset $B$ of $A$ with $\lvert B \rvert = 992$ that does not contain a pair of numbers whose sum is a multiple of $61$ . Divide $A$ into disjoint subsets $C_0, C_1, C_2, \dots, C_{60}$ such that $C_i$ contains all elements $k$ of $A$ such that

$k \equiv i \pmod{61}.$

Note that $\lvert C_i \rvert = 33$ for all $i \in \mathbb{Z}_{61}$ . $B$ can only contain one element of $C_0$ , because if it would contain more, two of those form a pair whose sum is a multiple of $61$ as well.

Let $D$ be the set such that

$D = \{ C_1, C_2, \dots, C_{60} \}.$

$B$ contains $991$ elements of the sets in $D$ . $991 > 30 \cdot 33$ , so by the pigeonhole principle, at least $31$ of the sets in $D$ contain at least one element that is also an element of $B$ . Now, let $E$ be the set such that

$E = \{ (C_1,C_{60}),(C_2,C_{59}),(C_3,C_{58}), \dots ,(C_{30},C_{31}) \}.$

We know that $\lvert E \rvert = 30$ , so again by the pigeonhole principle, there is at least one pair $(C_a,C_{61-a})$ in $E$ such that $C_a$ and $C_{61-a}$ both contain at least one number that is also an element of $B$ . The sum of those numbers $p,q$ is

$p+q \equiv a + (61 - a) \equiv 61 \equiv 0 \pmod{61},$

so the sum of these two numbers is a multiple of $61$ . Therefore, the assumption that there exists a subset $B$ of $A$ with $\lvert B \rvert = 992$ that does not contain a pair of numbers whose sum is a multiple of $61$ was wrong, hence $n = \boxed{992}$ .

I will call a collision a pair adding to a multiple of 61.

We consider modulo 61. There are 30 pairs of distinct residues that add to 61.

1--60,2--59,3--58,...,30--31

Since $61\cdot 33=2013$ , we can choose 33 numbers with each of 30 residues (say choose those 1-30) and still not have a collision. This is 990 numbers. However, we can also include one multiple of 61, since only if we include two will they cause a collision.

Adding in the extra number to force a collision, the answer is $\boxed{992}$ .

Dividing all 2013 numbers by 61, we see that there are 33 numbers for each quantity of remainder ( mod 1, mod 2, mod 3, mod 4, etc)

The questions asks for any subset B⊆A with ∣B∣≥n contains at least one pair of distinct numbers whose sum is a multiple of 61. So we can simply pick all the numbers from mod 1 to mod 30 to ensure that none of them will add up to form mod 0, giving us 990 numbers, then just add another one more mod 0 because pairing a mod 0 number with another number with a different remainder will never give a mod 0 number again. Then just add one more number to ensure that it is impossible to find no pairs which add up to forma multiple of 61. So the answer is 992.