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?

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

3 Answers 3

Reset to default
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 \}$.

$\endgroup$
5
  • $\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, 2013 at 18:23
  • $\begingroup$ $\{a, 50-a, 50+a, 100-a | a \in \{1,2,...,25\}\} \cup \{50\}$? :-) $\endgroup$
    – Georgey
    May 27, 2013 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, 2013 at 18:57
  • $\begingroup$ What does the LHS of the iff means? $\endgroup$
    – Georgey
    May 27, 2013 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, 2013 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.

$\endgroup$
1
  • $\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, 2013 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.

$\endgroup$
5
  • $\begingroup$ How come there are $54$ remainders? Aren't there 50 remainders in $\mod50$? $\endgroup$
    – Georgey
    May 27, 2013 at 20:19
  • $\begingroup$ @Georgey Each $a \in A$ gives two (one from $a$, one from $-a$) and $|A|=27$. $\endgroup$
    – WimC
    May 27, 2013 at 20:22
  • $\begingroup$ Right, and how did you use the PHP to show that there are 4 pairs? $\endgroup$
    – Georgey
    May 27, 2013 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, 2013 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, 2013 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.