Problem: Prove that in an $(n+1)$-element subset of $\{1,2,\ldots, 2n\}$ for a positive integer $n$, there exists two numbers that divide one another.
Solution: Consider the greatest odd divisor of each element. We have $n+1$ of these, one from each of the elements. All the odd divisors are $ < 2n$. But there are only $n$ odd numbers $ < 2n$. So by the Pigeonhole Principle, we have that two of the greatest odd divisors are equal ($n+1$ Pigeons in $n$ Holes). Then the element with a smaller power of $2$ divides the element with a larger power of $2$. QED.
--------------------
Comment: The problem at first probably doesn't look quite as easy as it turns out to be, thanks to our favorite Pigeonhole Principle. Problems involving sets and NT can many times be solved by the Pigeonhole Principle; it's only necessary to find out what the Pigeons are and what the Holes are. The Pigeonhole Principle can be generalized to the infinite case as well - given an infinite number of Pigeons and a finite number of Holes, there must be an infinite number of Pigeons in one Hole.
--------------------
Practice Problem #1: Given $50$ points on a $7 \times 7$ square, prove that there exists two points that are within $\sqrt{2}$ units of each other. Generalize this for an $n \times n$ square.
Practice Problem #2: Given a set $S$ of $51$ integers, prove that there exist $a,b \in S$ such that $100|(a+b)$ or $100|(a-b)$. Generalize this for $n|(a+b)$ or $n|(a-b)$.
I've got a better solution: n | 2n. :) More specifically, your solution stipulates that the element with the smaller power of 2 divides the element with the larger power of 2, but the only two elements of the form 2^a * n and 2^{a+1} * n are n and 2n, since, for all k > n, 2k does not appear in the set, and for all k
ReplyDeleteAnd for all k
ReplyDeleteAnd for all k less than 2n, k over two does not appear in the set. Stupid cutoff. x.x
ReplyDeleteBah. Copied the problem wrong... it's not supposed to be that easy -___-. Edited now.
ReplyDelete#1s easy. Its almost like that example that AoPS book gives in the beginning, only with 2x2. Although by generalizing, i guess it means that for n*n square of unit x, if there are n^2+1 points then at least two of them have to be within x\sqrt{2} unit?
ReplyDeleteFor #2, we denote such set {a_n}. They must be all different mod 100, or else the difference or the sum will be divisible by 100 (easily proven.)
ReplyDeleteSo there are 51 supposedly different mod 100, but since there are 50 groups of mod 100 that add up to 100 mod 100... i.e. {0}, {1,99}, ..., {49,51}, the last one must be in the same group as one of the other previous 50 integers, making those a and b such that 100|a+b.
generalize: For integer set S of x terms, there are two, a and b, such that 2(x-1)|
(a+b) or 2(x-1)|(a-b)