$ T$ is a subset of $ {1,2,...,n}$ which has this property : for all distinct $ i,j \in T$ , $ 2j$ is not divisible by $ i$ . Prove that : $ |T| \leq \frac {4}{9}n + \log_2 n + 2$
Problem
Source:
Tags: logarithms, LaTeX, combinatorics proposed, combinatorics
18.05.2009 21:36
Ok here we go. First, it is clear that all the biggest odd divisors of elements of $ T$ are different. Let me say $ log_2\ n = x$ and define the set $ T_i$ for $ i = 0, 1,\ldots\,x$ such that $ T_i$ is the set of the biggest odd divisors of the elements of $ T$ which has $ 2^i$ as the biggest power of $ 2$ that divides them. Then for all even $ k$, I claim that for any two different element from the union $ T_k$ and $ T_{k + 1}$ any of them can't divide the other. (actually for all k of course, but i will use only this) This is straightforward from the condition. Now, assume that we have a subset of the odd numbers from $ 1$ to $ t$ and for any two different element from this set, any of them can't divide the other. We will prove that this subset has at most $ \frac {t}{3}\ + 1$ elements. (Remember the problem that our set is the integers from $ 1$ to $ n$ and the other condition is the same. The method is absolutely the same.) Say this subset, $ S$. Now rewrite all the elements of $ S$ as $ 3^s\cdot\ p$ in which $ p$ is coprime with $ 3$. All the $ p$'s are different, otherwise the one with bigger $ s$ would divide the other. Moreover, all $ p$'s are from $ {1, 2,\ldots\ ,t}$; odd and coprime with $ 3$. Easy calculation shows that there are at most $ \frac {t}{3}\ + 1$ such numbers. So for any even $ k$ the union of $ T_k$ and $ T_{k + 1}$ can consist at most $ \frac {n}{3\cdot\ 2^k} + 1$ elements.(since the elements of $ T_i$ are lesser than or equal to $ \frac {n}{2^k}$) Summing all gives we can have lesser than $ \frac {4n}{9} + \frac {x + 1}{2}$ elements with only the possible exception of $ T_x$ which can have at most $ 1$ element (the sum of geometrical series) It's done. Actually this is a better bound than the wanted one, but I couldn't see my mistake. Anyways, this is the spirit.
06.01.2011 15:13
I have a solution from a book of a math group:
Attachments:
3.23.PDF (41kb)
06.01.2011 15:25
Love_Math1994 wrote: I have a solution from a book of a math group: Is it really from a math group? It is totally the same as the offical solution given by Iranian (every year Chinese leader in IMO will publish some problems of some countries with offical solution). Which book is it?
15.05.2011 21:20
It also from AMM:AMM E 3403 Proposed by Paul Erdos but have a different form:Prove that exist $|T-\frac{4}{9}|<C \cdot \ln n$...I am finding it in my collection of AMMs:) edit: Iran Mo 26:http://www.mediafire.com/?7w91n63sph7bf7o Moderator says: LaTeX knows \ln