$1, 2, 3, 4 ,\ldots, 300$, from this series, you need to erase some numbers and create a new series so that any two numbers’ sum is not divisible by $7$. What is the number of maximum terms that could be in the new series?

I guess some are confused regarding the wording of this question. It was originally written in another language and I've simply translated it. The questions asks to make a new sequence from the above sequence which is $1,2,3,4, \ldots,300$. You will remove numbers from this sequence such that if you choose any two numbers from your new sequence, and them add them up, this summation should NOT be divisible by $7$. You'll have to find the maximum numbers of terms of your new sequence.

How do I approach such a problem?

I've come to a part in this problem where I've found out that numbers that add up to $7$'s multiples should not be included in the sequence. For example, in the case of $13$ and $1$, they add up to $14$, which is divisible by $7$. So both these numbers can't be included in this new sequence.

If I consider the number $1$, I can add it to the following sequence: $6, 13, 20, 27,\ldots$ and I would get multiples of $7$. So this sequence can't be in my new sequence. This also goes for $5, 12, 19, 26,\ldots$ when added with $2$. Similarly, $4, 11, 18, 25, \ldots$ with $3$. In all the above sequences, here are $42$ terms, so I thought of subtracting $3$ times of $42$ from the initial $300$ terms to get the maximum number of terms. However, that method actually turned out to be wrong.

  • 1
    $\begingroup$ Your wording is confusing. You said first that "no two numbers' sum is not divisibly by $7$." That would mean that the sum of any two numbers is divisible by $7$. $\endgroup$ – Elliot G Nov 6 '16 at 18:30
  • $\begingroup$ @Elliot Sorry, this was the wording in the olympiad problem page. Let me rephrase it $\endgroup$ – Ahnaf Nov 6 '16 at 18:31
  • $\begingroup$ @Ahnaf I would request you to double check the question, or otherwise, post the question and olympiad details so that we can see it. I'm sorry to be like that but the question seems to be too weird due to the grammatical errors (probably). $\endgroup$ – Mayank M. Nov 6 '16 at 18:37
  • $\begingroup$ @MayankM. I've edited the question. $\endgroup$ – Ahnaf Nov 6 '16 at 18:42

If we think of numbers as their remainder when divided by $7$ (that is, modulo $7$), then we can never have remainders of both $1$ and $6$, $2$ and $5$, or $3$ and $4$.

The numbers with remainder $1$ are $1,8,15,\ldots,295$, and those with remainder $6$ are $6,13,20,\ldots,300$. Since they are the same size lets choose to include the first set. This gives $43$ elements.

Similarly we have $2,9,16,\ldots,296$ and $5,12,19,\ldots,299$. Again, they are the same size, so we now have $43+43=86$ elements.

Next we have $3,10,17,\ldots,297$ and $4,11,18,\ldots,298$. Now we have $86+43=129$ elements.

We have ignored the elements with remainder $0$, that is, multiples of $7$. We can pick one of these, say, $7$, but not two, because the sum of two numbers divisible by $7$ is a multiple of $7$. This gets us cleanly to $130$.

We have given a set of $130$ terms, but for completeness we might remark on why it is also the largest set. Suppose we obtained our set from including elements with remainder $1$, $2$, or $3$, along with $7$. Suppose we add another term. It's remainder when divided by $7$ must then be $4$, $5$, $6$, or $0$. If it is $4$, for example, then the number plus $3$ is divisible by $7$. If it is $0$ then the number plus $7$ is divisible by $7$, etc.

| cite | improve this answer | |

Divide elements into classes modulo 7. Then you have pairs of classes from which you can take numbers from only one of them. You of course take all the numbers from bigger class. Eventualy, from class of numbers divisible by 7 you can take only one number. This should all some up into the given answer since you will have 1+43+43+43=130 terms.

| cite | improve this answer | |

First, split this set into the following subsets:

  • $S_1=$ numbers which are congruent to $1\pmod7:\{1, 8,\dots,295\}$
  • $S_2=$ numbers which are congruent to $2\pmod7:\{2, 9,\dots,296\}$
  • $S_3=$ numbers which are congruent to $3\pmod7:\{3,10,\dots,297\}$
  • $S_4=$ numbers which are congruent to $4\pmod7:\{4,11,\dots,298\}$
  • $S_5=$ numbers which are congruent to $5\pmod7:\{5,12,\dots,299\}$
  • $S_6=$ numbers which are congruent to $6\pmod7:\{6,13,\dots,300\}$
  • $S_7=$ numbers which are congruent to $0\pmod7:\{7,14,\dots,294\}$

Second, pick elements from these subsets as follows:

  • Pick all $43$ elements from either $S_1$ or $S_6$
  • Pick all $43$ elements from either $S_2$ or $S_5$
  • Pick all $43$ elements from either $S_3$ or $S_4$
  • Pick $1$ element from $S_7$
| cite | improve this answer | |

$$300 \equiv 6 \mod 7$$

Let's consider the congruent classes:


$[0]_7 + [0]_7=[0]_7$ form multiple of $7$, hence we can only pick exactly $1$ element from $[0]_7$.

There are $42$ multiples of $7$. Hence there are $300-42=258$ non-multiples of $7$

If you pick elements from $[1]_7$, we can't pick elements from $[6]_7$. Similar reasoning for the other equivalent classes. Also notice that $[i] \cap \left\{ 1, \ldots, 300 \right\}$ has the same cardinality for $i=1,\ldots, 6$.

Hence the maximum number is $1+258/2=130$


Let's count how many numbers are in $[6]_7 \cap \left\{1, \ldots, 300 \right\}$, the first number is $6$ and the last number is $300$. They can be written as $7i+6$ where $i=0, \ldots 42$, hence there are 43 numbers which is a mistake that you make. Another mistake is you forgot to exclude additional multiple of $7$'s.

Notice that there are 42 elements in $[0]_7 \cap \left\{1, \ldots, 300 \right\}.$

$$300-3 \times 43-42+1=130$$

| cite | improve this answer | |

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.