Pigeonhole principle application sums and differences

Question

Let $A \subset \{1,2,...,99\}$, prove or disprove the following:

a. For $|A| = 27$
b. For $|A| = 26$

There are $2$ different numbers in $A$ that their sum or their difference can be divided with $50$.

I am sure the question points me to use Pigeonhole Principle, but I'm not quite sure which are the pigeons and which are the holes because the question deals with or so proving that a sum (or a difference) can be divided with $50$ closes the proof without handling the other case.

I've started with saying that there are $(99+98)-(1+2)+1=195$ different sums, and $(99-1)-(1-99)+1=197$ differences (including negatives) in $\{1,2,...,99\}$.
Also, when dividing with $50$ you can get maximum 50 remainders (let $r \in \{0,1,...,49\}$ mark the reminders)

Can anyone hint me with how to proceed from here?

Answer 1

Hint: Consider the sets: $\{1, 49, 51, 99 \}, \{2, 48, 52, 98 \}, \{3, 47, 53, 97 \}, \ldots, \{24, 26, 74, 76 \},\{25, 75 \}, \{50 \}$.

Answer 2

Every element of your set {1... 99} is either in A or A' (complement of A) You can pigeonhole more efficiently by considering which elements cannot be in the same set, then demonstrating that the requirements for how many elements are in A are violated.

So for example: If 1 is in A then 99 and 49 and 51 must be in A'. Try to continue this line of argument.

Answer 3

For part b) consider the set $A = \{n \mid 25 \leq n \leq 50\}$. It has $26$ elements and no sum or difference of two different elements is divisible by $50$.

For part a) consider the remainders of $\pm a$ ($\bmod$ $50$) for all $a \in A$, so $54$ remainders in total. Therefore there must be at least four pairs $$(a_1,b_1), (a_2,b_2), (a_3,b_3), (a_4,b_4)$$ with $a_k \in A$ all distinct and either $b_k \in A$ or $-b_k \in A$ such that $a_k-b_k$ is divisible by $50$ for $k \in \{1,\dotsc, 4\}$. If $b_k \in A$ then $b_k \neq a_k$ since each number in $A$ is used only once. The only possible pairs that do not lead to a solution are $$(25,-25), (50,-50), (75,-75)$$ since for these pairs the same number from $A$ is used twice. So there must be at least one pair left that leads to a proper solution.