2

I got this problem in a mathematics class. I've already seen how to solve it and fully understand the proof that is most commonly seen online (for example on this website). However, I'm having trouble understanding whether my proof (which is simpler to my opinion) wouldn't work:

Let's name A:= {$a_1$, ..., $a_{20}$} $\subset$ {1, ..., 70} the set of distinct integers.

Let's name D:= {|$a_i$ - $a_j$| : 1 $\le$ i $\neq$ j $\le$ 20} $\subset$ {1, ..., 69} the set of pairwise differences

By a simple combinatorial argument, we know that if there aren't any equivalences in the set D then card(D)= ${20 \choose 2}$ = 190

Therefore, if we show that we actually have card(D) $\le$ 190-4 = 186, we've shown there's at least 4 equivalences in the set D.

But as a matter of fact, D $\subset$ {1, ..., 69} implies that card(D) $\le$ 69. Hence this proves the result.

Where have I gone wrong in my reasoning?

Calvin Lin
  • 68,864
Lupetto1927
  • 137
  • 6
    I think they mean "There are four differences that are all equal to one another". Which is to say "There are at least four pairs with difference 1, or there are at least four pairs with difference 2, or ..." – Arthur Nov 09 '19 at 14:40
  • 3
    So, to follow through on your reasoning, you have 190 pairwise differences (pigeons) and 69 possible values (holes), so there is some value that is equal to at least $3 = \lceil 190/69 \rceil $ pairwise differences. However, it is not immediately obvious how this can be extended to show 4 pairwise differences. – Calvin Lin Nov 09 '19 at 15:57

0 Answers0