Consider the set $E = \{1,2,\ldots,2n\}$. Prove that an element $c \in E$ can belong to a subset $A \subset E$, having $n$ elements, and such that any two distinct elements in $A$ do not divide one each other, if and only if \[c > n \left( \frac{2}{3}\right )^{k+1},\] where $k$ is the exponent of $2$ in the factoring of $c$.
Problem
Source: Romanian TST 4 2007, Problem 3
Tags: induction, number theory proposed, number theory
23.05.2007 21:50
I'm sorry but I think I misunderstood the problem We can take the set $A = \{n+1,n+2,\ldots,2n\}$. If $a,b \in A$ and $a \mid b$, then $b \ge 2a \ge 2(n+1)$, impossible. Then take $c = n+1$ of $c=n+2$, the one that is odd. Should we prove that $c > \frac{2}{3}n$ ??
24.05.2007 21:35
Yes edriv, the problem probably is wrong! I think that the correct is $c > (\frac{2}{3})^{k}$!
24.05.2007 22:18
Ok, I did't misunderstand the problem, I just swapped n with 2n (and e.lopes' mind is identical to mine ) Here is the proof. A comment: the problem is so strict that is not hard. But it's still very nice A definition: $\mbox{god}(n)$ is the greatest odd divisor of n Another definition: $v_{2}(n)$ is the greatest power of 2 that divides n. Then we have the decomposition $n = \mbox{god}(n) \cdot 2^{v_{2}(n)}$ Some facts: a) For each odd integer $1 \le k \le 2n$, there exist a unique power of 2 such that $n < 2^{e}k \le 2n$. Proof: take the greatest power of 2 such that $2^{i}k \le 2n$. Then $2^{i+1}> 2n$ because of maximality, and then $2^{i}> n$. b) If two distinct integers are such that $n <a,b \le 2n$, then $a \nmid b$ Proof: if $a\mid b$ and $a \neq b$ then $b \ge 2a$. c) If $a \mid b$ then $\mbox{god}(a) \mid \mbox{god}(b)$ d) If $\mbox{god}(a)=\mbox{god}(b)$ then $a \mid b$ or $b \mid a$. e) For each odd integer $1 \le c \le 2n$ and for each n-antichain A, there is an unique power of 2 such that $2^{e}c \in A$. Proof: A is an antichain, then using fact (d) we prove that the god's of its elements are distinct. There are n elements and n odd integers between 1 and 2n. Then they are all. And now to the proof, by induction on $k = v_{2}(c)$. $k=0$ means that c is odd. Suppose that $c \le \frac{2}{3}n$. Then $3c\le 2n$. By fact (e), a number of the form $2^{e}\cdot 3c \in A$. But $c \in A$ and $c \mid 2^{e}\cdot 3c$. Suppose that $c > \frac{2}{3}n$. Then, put c in A, and for each odd integer d, put the unique $n < 2^{e}d \le 2n$ in A (using fact a). A is an antichain, since if $a,b \in A, a\mid b$ then $\mbox{god}(a)=\mbox{god}(b)$, and either a,b are between n and 2n, or a = c. But then the greatest odd divisor of b is an odd multiple of c, and we obtain $b \ge 3c > 2n$. And now, suppose the problem is always true for all c such that $v_{2}(c) < i$ and let's prove it for $v_{2}(c) = k = i$, that is, $c=2^{i}c'$ with odd c'. Suppose $c \le \left(\frac{2}{3}\right)^{i+1}n$. Then $a = \frac{3}{2}c \le \left(\frac{2}{3}\right)^{i}n$ is odd, integer, such that $v_{2}(a) =i-1$. a, multiplied by a power of 2, must belong to A, and using the induction hypotesis, prove that this is impossible. Now suppose $c > \left(\frac{2}{3}\right)^{i+1}n$. We do this construction: - put c in A - If $3^{e}c' \le a < 3^{e+1}c'$, a is an odd integer and $c' \mid a$, then put $2^{i-e}a$ in A - if a is an odd integer and $c' \nmid a$, then put $n<2^{e}a \le 2n$ in A, as in fact (a) The proof that this works: - if a is an odd integer, then either $c' \mid a$ or $c' \nmid a$, therefor a number of the form $2^{e}a$ is in A. A has n elements. - If $a,b \in A, a \mid b$ then $\mbox{god}(a) \mid \mbox{god}(b)$. Then: * if $c' \nmid \mbox{god}(a)$, then by the construction $n < a \le 2n$ and b is too big. Impossible. * if $c' \mid \mbox{god}(a)$ then also $c' \mid \mbox{god}(b)$. But $\mbox{god}(b) \ge 3\mbox{god}(a)$, then, $\mbox{god}(a),\mbox{god}(b)$ are in two classes of the construction, then $v_{2}(b) < v_{2}(a)$ and it's impossible that $a \mid b$.
11.06.2015 22:27
An interesting result... Consider the following $ n \times \infty $ "matrix": $ 2^0*1, 2^1*1, 2^2*1, \ldots $ $ 2^0*3, 2^1*3, 2^2*3, \ldots $ $ \ldots $ $ 2^0*(2n-1), 2^1*(2n-1), 2^2*(2n-1), \ldots $ Clearly any set $A$ must have exactly one number from each row. But let $c$ be in row $(k+1)/2$ consider the rows $(3k+1)/2, (9k+1)/2, \ldots$. The first one must have a number in a column before the column of $c$, the second one must have a number in a column two spaces before the column of $c$, etcetera. From this we easily get $c > n*(2/3)^k$, as desired. Now assume $c>n(2/3)^k$ and $c$ is in column $y$. If $k | \ell$, then assume $\ell / k $ has $x$ primes (including repetition) in its factorization, and from line $(\ell +1)/2$ include the number in the column $y-x$ . If $k$ doesn't divide $\ell$, then from line $(\ell +1)/2$ include the maximum number in that line that is $\le 2n$. This works.