1
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ How about considering the members of A (mod 50)? $\endgroup$ – CarlesV May 27 '13 at 18:23
  • $\begingroup$ Wouldn't it be the set I've mentioned? $\{0,1,...,49\}$? $\endgroup$ – Georgey May 27 '13 at 18:26
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How do I generate those sets systematically? I can write a $10 \times 9$ table and circle the sums that can be divided with $50$ but I'm looking for an elegant proof. $\endgroup$ – Georgey May 27 '13 at 18:23
  • $\begingroup$ $\{a, 50-a, 50+a, 100-a | a \in \{1,2,...,25\}\} \cup \{50\}$? :-) $\endgroup$ – Georgey May 27 '13 at 18:33
  • $\begingroup$ @Georgey It is worthwhile to point out that these are the sets $A_i$ such that $a \in A_i \Leftrightarrow a \equiv \pm i \pmod{50}$. So your initial guess is close, you just needed to account for the sum, as opposed to just the difference. $\endgroup$ – Calvin Lin May 27 '13 at 18:57
  • $\begingroup$ What does the LHS of the iff means? $\endgroup$ – Georgey May 27 '13 at 19:03
  • $\begingroup$ All in all it means that by using PHP that a. $\left \lceil \frac{27}{26} \right \rceil = 2$ is a proof while b. $\left \lceil \frac{26}{26} \right \rceil$ is a disproof? $\endgroup$ – Georgey May 27 '13 at 19:27
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Why would $99,49$ and $51$ be in $A'$? Because their sum/difference with $1$ makes it divisible by $50$? I'm not sure I understand which elements are supposed to be in $A'$. $\endgroup$ – Georgey May 27 '13 at 18:39
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How come there are $54$ remainders? Aren't there 50 remainders in $\mod50$? $\endgroup$ – Georgey May 27 '13 at 20:19
  • $\begingroup$ @Georgey Each $a \in A$ gives two (one from $a$, one from $-a$) and $|A|=27$. $\endgroup$ – WimC May 27 '13 at 20:22
  • $\begingroup$ Right, and how did you use the PHP to show that there are 4 pairs? $\endgroup$ – Georgey May 27 '13 at 20:27
  • $\begingroup$ @Georgey There are $50$ holes for $54$ pigeons, so at least four pigeons have to go into a hole that was already occupied. $\endgroup$ – WimC May 27 '13 at 20:29
  • $\begingroup$ I must be too tired and totally wrong but doesn't the PHP means that there are at least $\left \lceil \frac{54}{50} \right \rceil = 2$ pigeons that will go to an occupied hole? $\endgroup$ – Georgey May 27 '13 at 20:33

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.