Posted by: yanzhang | November 30, 2009

## M-2: Forcing properties onto integer pairs

Steven greeted me with a puzzle when I entered the office today. I got it after thinking a bit, though I definitely have seen this a long time ago:

Given 51 numbers between 1 and 100, show that you can find two of them that are relatively prime

Proof:

By pigeonhole, we must get at least two numbers of the form {x, x+1}, where x is odd. These two are relatively prime.

Steven then gave me a strictly harder followup. This took me a bit longer, and afterwards I was very happy to have come up with an unorthodox solution, and hence a new post:

Given 51 numbers between 1 and 100, show that you can find two of them such that one divides the other.

Proof and analysis:

Start by putting every number between 1 and 100 into a bucket. Now, starting with 100 and moving down to 2, move *all* the numbers in the bin of every even number of the form $2n$ into the bucket where $n$ is. Each time we do this, a bucket becomes empty. So at the end we have 50 buckets. By pigeonhole, we must get at least two numbers in the same bucket. The quotient of those two numbers is a power of two, so we’re done.

Note I could have just said something like: “for every odd number $q$, put all numbers of the form $2^kq$ into the same equivalence class” and then counted equivalence classes. However, it seems that in this language, counting equivalence classes requires at least a couple of steps of thought. For some unknown reason, by using this handwavy “bucket” talk, the number of equivalence classes is obviously 50, whereas by using the more rigorous language above, I don’t see an immediate way to get the answer at quite the same speed.

People used to competitions would probably recognize the first problem as an old chestnut; this is actually a puzzle Uncle Erdos used to test mathematical ability in young kids (‘epsilons’). I don’t know where the second problem comes from.

Happy Thanksgiving,
-Yan

## Responses

1. q is positive, odd, and less than 100?

Both of the problems are great classics. Another classic: prove that among n people, some two people have the same number of friends. (Friendship is presumed symmetric and antireflexive.)

2. As far as I can remember, the first problem you posed is given in Mathematical Circles: Russian Experience, and a variant of the second reads as follows (in the book):

Given 11 different natural numbers (0 not being considered a natural in this case), none greater than 20, show that two of these can be chosen such that one divides the other.

Here’s another one: Prove that of any 52 integers, two can always be found such that the difference of their squares is divisible by 100.

3. @Vishal: I see how to solve that one. Cute =) For that one, I feel you can actually do a lot better since there are many fewer quadratic residues mod 100.

4. […] Yan at Concrete Nonsense: M-2: Forcing Properties onto integer pairs […]

5. Just one small note for completeness: both results in the post are sharp, with examples of size 50 provided by {2, 4, 6, …, 100} and {51, 52, 53, …, 100}.

6. Whoa, I think the second comes directly from Engel’s Problem Solving Strategies (along with the first) in the Pigeonhole chapter.