Partition of a set of positive integers

137 Views Asked by At

Problem: Let $A$ be a non-empty set of positive integers. Suppose that there are positive integers $b_1,\ldots b_n$ and $c_1,\ldots,c_n$ such that

  • for each $i$ the set $b_iA+c_i=\left\{b_ia+c_i\colon a\in A\right\}$ is a subset of $A$, and

  • the sets $b_iA+c_i$ and $b_jA+c_j$ are disjoint whenever $i\ne j$

Prove that ${1\over b_1}+\,\ldots\,+{1\over b_n}\leq1.$

My attempt: We will start by counting the number of positive integers that belongs to the sequence $b_iA+c_i$. It's not hard to see that at-most $\lfloor \frac{N-c_i}{b_i} \rfloor$ positive integers $\le N$ belong to the sequence $b_i A+C_i$. Then observe that $$\sum_{i=1}^{n} \lfloor \frac{N-c_i}{b_i} \rfloor\le N$$ $$\implies \sum_{i=1}^{n}\frac{N}{b_i}-\sum_{i=1}^{n}\frac{c_i}{b_i}-n\le N$$ $$\implies \sum_{i=1}^{n}\frac{1}{b_i}-\frac{1}{N}\sum_{i=1}^{n}\frac{c_i}{b_i}-\frac{n}{N}\le 1$$

Now taking $N\to \infty$(which is possible because $A$ is obviously an infinite set), we have the desired inequality.

Is this a correct solution?

Thanks for your help.

1

There are 1 best solutions below

2
On

I think you used the fact $x-1 <\lfloor x \rfloor $ to go from the first line to second line of inequalities in your proof, so the line should be $$\sum_{i=1}^n \dfrac{N}{b_i} - \sum_{i=1}^n\dfrac{c_i}{b_i}-n \le N$$ which gives the same result in the next step on taking $N\to\infty$. Apart from that, it looks alright to me. The idea you have used here is of natural density.

Another problem that you might try is

The natural number set $\Bbb{N}=\{1,2,3,\cdots\}$ is partitioned (divided into mutually disjoint subsets) into $A_1,A_2,\cdots,A_n$ (i.e. $A_i\cap A_j=\phi$ if $i\ne j$) such that the elements of $A_i$ are in arithmetic progression with common difference $b_i$. Prove that $$\dfrac1{b_1}+\dfrac1{b_2}+\cdots +\dfrac1{b_n}=1$$