# Thread: Maths Problem Counting Techniques?

1. ## Maths Problem Counting Techniques?

What is the maximumsize of a subset, P, of {1, 2, 3, . . . , 50}
with the property that no pair of distinct elements of P
has a sum divisible by 7?
(A) 21 (B) 22 (C) 23 (D) 24 (E) 25

How do I solve it?
Can u guys show me the steps?

2. ## Counting problem

Hello paul14
Originally Posted by paul14
What is the maximumsize of a subset, P, of {1, 2, 3, . . . , 50}
with the property that no pair of distinct elements of P
has a sum divisible by 7?
(A) 21 (B) 22 (C) 23 (D) 24 (E) 25

How do I solve it?
Can u guys show me the steps?
Welcome to Math Help Forum!

I reckon the answer is 23. Here's my reasoning.

Consider the partition of P into sets $\displaystyle A_i, i = 0, 1, 2,...6$ as follows: $\displaystyle A_i = \{n:n=i \mod 7\}$

So, for example, $\displaystyle A_0 = \{7, 14, ..., 49\}, A_1 = \{1, 8, ..., 50\}$, etc

Then $\displaystyle |A_i| = 7, i = 0, 2, 3,4,5, 6$ and $\displaystyle |A_1| = 8$

Now if we choose an $\displaystyle n \in A_i$ to be in our subset , then we must not choose an $\displaystyle m \in A_{7-i}$, for then $\displaystyle n + m = 0\mod 7$

Thus the subset can contain at most $\displaystyle 1$ element from $\displaystyle A_0, 8$ elements from $\displaystyle A_1$, and then $\displaystyle 7$ elements from any two of the remaining $\displaystyle A_i$, in such a way that no two of the $\displaystyle i$'s add up to $\displaystyle 7$.

Total: $\displaystyle 1 + 8 + 7 + 7 = 23$