Let $A$ be a non-empty set of positive integers. Suppose that there are positive integers $b_{1}$, $\cdots$, $b_{n}$ and $c_{1}$, $\cdots$, $c_{n}$ such that for each $i$ the set $b_{i}A+c_{i}=\{b_{i}a+c_{i}\vert a \in A \}$ is a subset of $A$, the sets $b_{i}A+c_{i}$ and $b_{j}A+c_{j}$ are disjoint whenever $i \neq j$. Prove that \[\frac{1}{b_{1}}+\cdots+\frac{1}{b_{n}}\le 1.\]
Problem
Source:
Tags: limit
25.05.2007 03:25
For any set $S$ of positive integers define $n_S(k) := | \{ s \in S | s \leq k \}|$. For $B \subseteq A$ we define the density of $B$ in $A$ by $d_A(B) := \lim_{k \to \infty} \frac{n_B(k)}{n_A(k)}$ if this limit exists. Clearly $0 \leq d_A(B) \leq 1$. We define $A_i := \{ b_i a + c_i \in A | a \in A\}$. Some easy analysis gives $d_A(A_i)= \frac{1}{b_i}$. Since the sets $A_i, A_j$ are disjont for $i \neq j$, we get that $n_A\left(\bigcup_{i=1}^n A_i\right) = \sum_{i=1}^n n_A(A_i)$, giving $d_A\left(\bigcup_{i=1}^n A_i\right) = \sum_{i=1}^n d_A(A_i)= \sum_{i=1}^n \frac{1}{b_i}$. But now $1 \geq d_A\left(\bigcup_{i=1}^n A_i\right) = \sum_{i=1}^n \frac{1}{b_i} $.
25.04.2009 18:58
ZetaX wrote: For any set $ S$ of positive integers define $ n_S(k) : = | \{ s \in S | s \leq k \}|$. For $ B \subseteq A$ we define the density of $ B$ in $ A$ by $ d_A(B) : = \lim_{k \to \infty} \frac {n_B(k)}{n_A(k)}$ if this limit exists. Clearly $ 0 \leq d_A(B) \leq 1$. We define $ A_i : = \{ b_i a + c_i \in A | a \in A\}$. Some easy analysis gives $ d_A(A_i) = \frac {1}{b_i}$. Since the sets $ A_i, A_j$ are disjont for $ i \neq j$, we get that $ n_A\left(\bigcup_{i = 1}^n A_i\right) = \sum_{i = 1}^n n_A(A_i)$, giving $ d_A\left(\bigcup_{i = 1}^n A_i\right) = \sum_{i = 1}^n d_A(A_i) = \sum_{i = 1}^n \frac {1}{b_i}$. But now $ 1 \geq d_A\left(\bigcup_{i = 1}^n A_i\right) = \sum_{i = 1}^n \frac {1}{b_i}$. Hi,ZetaX.Could you please show why Some easy analysis gives $ d_A(A_i) = \frac {1}{b_i}$. I think this is the difficulty of this problem(maybe it can be solved by an advanced theorem?)Could you please help me with it? You can also check http://www.mathlinks.ro/viewtopic.php?t=17335