Let $ k$ be a positive integer. Set $ A \subseteq \mathbb{Z}$ is called a $ \textbf{k - set}$ if there exists $ x_1, x_2, \cdots, x_k \in \mathbb{Z}$ such that for any $ i \neq j$, $ (x_i + A) \cap (x_j + A) = \emptyset$, where $ x + A = \{ x + a \mid a \in A \}$. Prove that if $ A_i$ is $ \textbf{k}_i\textbf{ - set}$($ i = 1,2, \cdots, t$), and $ A_1 \cup A_2 \cup \cdots \cup A_t = \mathbb{Z}$, then $ \displaystyle \frac {1}{k_1} + \frac {1}{k_2} + \cdots + \frac {1}{k_t} \geq 1$.
Problem
Source: China TST 2004 Quiz
Tags: inequalities, combinatorics unsolved, combinatorics
01.02.2009 17:21
Is there anything to this problem other than invoking a notion of density?
17.02.2009 06:51
This is a difficult problem, I hope everyone post solution.
10.09.2015 13:56
Let $\overline{d}(A) = \limsup_{n \rightarrow \infty} \frac{|\{-n,\ldots, -1,0,1,2,\ldots,n\} \cap A|}{2n} $ denote the upper density of a set $A\subset\mathbb{Z}.$ One can note that $\overline{d}(B_1 \cup B_2 \cup \cdots \cup B_m)\leq \sum_{i=1}^m \overline{d}(B_i)$. Lemma: For any $ \textbf{k - set}$ $A$ we have $\overline{d}(A)\leq \frac 1 k.$ The sets $(x_i+A)\cap [-n, n]$ are disjoint, thus $\sum_{i=1}^k |(x_i+A)\cap [-n, n]|\leq 2n$ or equivalently $\sum_1^k |A\cap [-n-x_i, n-x_i]|\leq 2n$. Let $l =\max \{x_1,\ldots ,x_k, -x_1,-x_2,\ldots, -x_k\}$, then $[-n+l, n-l]\subset \cap_i [-n-x_i, n-x_i]$ and thus $k|A\cap[-n+l, n-l]|\leq 2n$ which when $n\to+\infty$ gives $\overline{d}(A)\leq \frac 1 k$. Now we have $1= \overline{d}(\mathbb{Z})= \overline{d}(A_1 \cup A_2 \cup \cdots \cup A_t)\leq \overline{d}(A_1)+\overline{d}(A_2)+\ldots \overline{d}(A_t)\leq \frac {1}{k_1} + \frac {1}{k_2} + \cdots + \frac {1}{k_t}.$
03.12.2017 19:01
generation function maybe works