Suppose $A\subset \{(a_1,a_2,\dots,a_n)\mid a_i\in \mathbb{R},i=1,2\dots,n\}$. For any $\alpha=(a_1,a_2,\dots,a_n)\in A$ and $\beta=(b_1,b_2,\dots,b_n)\in A$, we define \[ \gamma(\alpha,\beta)=(|a_1-b_1|,|a_2-b_2|,\dots,|a_n-b_n|), \] \[ D(A)=\{\gamma(\alpha,\beta)\mid\alpha,\beta\in A\}. \] Please show that $|D(A)|\geq |A|$.
Problem
Source: China Team Selection Test 2003, Day 1, Problem 3
Tags: inequalities, vector, induction, function, ceiling function, inequalities unsolved
ThAzN1
19.10.2005 04:00
Does this work? Let $|A| = a$. Playing around with the cases $n = 1, 2$, we are inspired to induct on $a$. For $a=1$, the result is trivial because taking $\alpha = \beta$, we deduce that the zero vector is in $D(A)$. Assume that $|D(A)| \geq a$ some integer $a \geq 1$. For an element $\alpha$ in $A$, let $f_k(\alpha)$ denote the $k$th term in the $n$-tuple $\alpha = (a_1,\dots , a_n)$. (Of course, $k = 1,\dots , n.$) Now, consider the element $X = (x_1, \dots , x_n) \in A$ such that $f_1(X) > f_1(Y)$ for any $Y \in A$ such that $X \neq Y$. If $f_1(X) = f_1(Y)$ for some $X\neq Y$, then out of all the elements $Z \in A$ with $f_1(Z)$ maximal, we choose an $X$ such that $f_2(X) > f_2(Y)$ for any $Y \in A$ such that $X \neq Y$. If instead $f_2(X) = f_2(Y)$ for some $X \neq Y$, we may continue this procedure and move on to $f_3(X)$. Note that eventually, we can obtain an $X$ such that for some $Y \in A$ with $X \neq Y$, we have $f_k(\gamma (X,Y)) > 0$ for some $k \in \{1,\dots , n\}$ and $f_j(\gamma (X,Y)) = 0$ for all integers $0 < j < k$. This will hold, unless $k=1$, but $f_1(\gamma (X,Y)) > 0$ is all we will need in this case. We can choose such an $X\in A$ satisfying these because otherwise, if there exists $X,Y \in A$ with $X \neq Y$ and $f_k(X) = f_k(Y)$ for all $k = 1, \dots , n$, then $X=Y$, contradiction. Now, consider the set $A/ \{X\}$. We apply the induction hypothesis on this set, so we have $|D(A/ \{X\})| \geq a-1$. Now, pick an element $X' \in A/ \{X\}$ as we did when we chose an $X \in A$, except in the exact opposite way. (Essentially, we reverse all of the inequality signs.) Thus, there will exist some $k \in \{1,\dots , n\}$ such that $f_k(\gamma (X, X')) > f_k(\gamma (X, Y))$ for any $Y \in A/ \{X\}$ satisfying $f_j(\gamma (X, Y)) = f_j(\gamma (X, X'))$ for $j = 1,\dots ,k-1$. Unless, of course $k=1$ (when the result is pretty much clear), this procedure is valid. Thus, we have $|D(A)| > |D(A/ \{X\})| \geq a-1$. This completes the induction. (Yeah, that was kind of hard to write-up so it's kind of vague... I'll probably rewrite it later, but feel free to object -- I'm not sure at all if this is even close to being valid. )
ThAzN1
20.10.2005 03:46
Actually, the last part isn't completely true. Take, for instance (5, 3, 3), (5, 1, 1), (3, 2, 2). So, X = (5, 3, 3) and X' = (3, 2, 2) but nothing new in D(A) is added for this pair. (Thanks to darktreb for pointing that out.) Any ideas? :
ThAzN1
03.12.2005 03:31
OH SWEET I THINK I GOT IT Let $m = |A|$ and let the $n$-tuples of $A$ be $(a_{i,1}, a_{i,2}, \dots , a_{i,n})$ where $1 \leq i \leq m.$ Without loss of generality, assume $a_{1,1} \leq a_{2,1} \leq \cdots \leq a_{m,1}$. We proceed by induction on $n$. For $n=1$, our ordering must be strict, so $a_{1,1} < a_{2,1} < \cdots < a_{m,1}$. Note that \[ 0 = a_{m,1} - a_{m,1} < a_{m,1} - a_{m-1,1} < \cdots < a_{m,1} - a_{1,1} \] are $m$ elements all in $D(A)$ so it follows that $|D(A)| \geq m = |A|$. Now assume that the result holds for some positive integer $n$. Let $X_1$ be the set of all distinct values of $a_{i,1}$ for $1 \leq i \leq m$. Let $r = |X_1|$ and let $x_1 < x_2 < \cdots < x_r$ be the elements of $X_1$. Moreover, define $t_j$ to be the number of $a_{i,1}$ equal to $x_j$ for $1 \leq j \leq r$ . In other words, we have \[ a_{1,1} = \cdots = a_{t_1,1} < a_{t_1+1,1} = \cdots = a_{t_1+t_2,1} < \cdots < a_{m-t_r+1,1} = \cdots = a_{m,1}. \] Clearly, we have $t_i \geq 1$ for $1\leq i \leq r$ and also $t_1+t_2+\cdots + t_r = m$. Now, consider the sets of $(n-1)$-tuples $B_k$ for $1 \leq k \leq r$, where an element $(b_1, b_2, \dots , b_{n-1})$ is in $B_k$ if and only if $(x_k, b_1, b_2, \dots , b_{n-1}) \in A$. We have at least $r$ distinct values of the first entry in the elements of $D(A)$, namely, \[ 0 = x_1 - x_1 = x_2 - x_2 = \cdots = x_r - x_r < x_r - x_{r-1} < \cdots < x_r - x_1. \] If the first entry of an element $\alpha \in D(A)$ is $0$, then there are at least $|D(B_k)| \geq |B_k|$ (by the induction hypothesis) of these elements for all $1 \leq k \leq r$. If the first entry of an element $\alpha \in D(A)$ is $x_r - x_\ell$ for some $1\leq \ell < r$, then there are at least $|D(B_r)| \geq |B_r|$ or at least $D(B_\ell) \geq |B_\ell|$ of these elements in $D(A)$, where the inequalities again follow from the induction hypothesis. Thus, we have \[ |D(A)| \geq \sum_{i=1}^{r-1} \textrm{max}\{t_i, t_r\} + \textrm{max}\{t_1,t_2,\dots , t_r\} \geq \sum_{i=1}^{r-1} t_i + t_r = m = |A|, \] as desired. [edit] nvm maybe this is wrong?
ptolemy
01.04.2007 20:13
Quote: If the first entry of an element is , then there are at least (by the induction hypothesis) of these elements for all . If the first entry of an element is for some , then there are at least or at least of these elements in , where the inequalities again follow from the induction hypothesis. Not true. Suppose A contains the four triples (-1,-1,0) (-1,1,0) (1,0,-1) (1,0,1). Then D(A) only has one element whose first element is 2.
The QuattoMaster 6000
04.08.2010 22:46
Induct on $n$. For the base case $n = 1$ let the elements of $A$ be $z_1, z_2, \cdots, z_{|A|}$ and, without loss of generality, $z_1 < z_2 < z_3 < \cdots < z_{|A|}$. Thus, for all $1\le j\le |A|$, $(z_i - z_1)$ is an element of $D(A)$. Since $z_i - z_1\ge 0$ and $z_i\ne z_j$ when $i\ne j$, $D(A)$ has at least $|A|$ elements. Now suppose the inequality is true when $A$ consists of at $n-1$-tuples and we will prove the inequality if $A$ consists of $n$-tuples.
Let $A$ consist of the elements $e_i = \{a_{i, 1}, a_{i, 2}, a_{i, 3}, \cdots , a_{i, n} \}$ for all $1\le i\le a = |A|$. Consider the $n-1$-tuples $e_i' = \{a_{i, 2}, a_{i, 3}, a_{i, 4}, \cdots , a_{i, n} \}$ for all $1\le i\le a$, and let $f_1, f_2, f_3, \cdots, f_t$ be the set of distinct elements $e_i'$, ordered such that if $n_j$ is the number of $e_i'$ so that $e_i' = f_j$ for each $1\le j\le t$, then $n_1 \le n_2\le n_3\le \cdots \le n_t$. Set $A_j$, for all $1\le j\le t$, to be the set of $e_i$ so that $e_i' = f_j$. By definition, $\sum_{i=1}^t n_i= a$. Define the function $f(f_i, f_j) = \{ |a_{u, 2} - a_{v, 2}|, |a_{u, 3} - a_{v, 3}| , \cdots , |a_{u, n} - a_{b,n}| \}$ if $e_u' = f_i$ and $e_v' = f_j$.
Correspond these sets to vertices of a graph; let vertex $v_i$ correspond to the set $A_i$ in our graph. Now define the following process. Start at $v_t$, draw an edge to itself, and record the $n-1$-tuple $f(f_t, f_t) = \{ 0, 0, 0, \cdots , 0 \}$. Then, draw an edge between $v_t$ and $v_{t-1}$ and record the difference $f(f_{t-1}, f_t)$. Now, if $f(f_t, f_{t-2})$ has not yet been recorded, draw an edge between $v_t$ and $v_{t-2}$ and record $f(f_t, f_{t-2})$. Otherwise, do nothing and proceed. If $f(f_{t-1}, f_{t-2})$ has not been recorded, draw an edge between $v_{t-1}$ and $v_{t-2}$ and record $f(f_{t-1}, f_{t-2})$. Otherwise, do nothing and proceed. Do the same for the pairs $(v_t, v_{t-3})$, $(v_{t-1}, v_{t-3})$, and $(v_{t-2}, v_{t-3})$ in that order. Keep doing this for $t - 4, t - 5, \cdots , 1$. Say that once we have determined whether to draw an edge between $v_{i-1}$ and $v_i$, we have "completed the $i$th set."
By Lemma 1 below, there are at least $\left\lceil \frac{n_x + n_y - 1}{2} \right\rceil$ differences between elements of $A_x$ and $A_y$ (upon taking differences between the first element of $A_x$ and the first of $A_y$). Moreover, by the base case of the original problem, there are at least $n_t$ differences between elements of $A_t$. Let $n(A_x, A_y)$ be the number of distinct $n$-tuples in the set of $f(s, t)$, where $s$ ranges over all elements of $A_x$ and $t$ ranges over all elements of $A_y$. Summing this over all sets $(x, y)$ so that $v_x$ and $v_y$ are connected gives that \[|D(A)| \ge \sum_{v_i, v_j connected} n(A_i, A_j) + n_t \ge \sum_{v_i, v_j connected} \left\lceil \frac{n_i + n_j - 1}{2} \right\rceil + n_t\] because differences between $A_i$ and $A_j$ will form a "new difference" in the last $n - 1$ elements of the $n$-tuple if $v_i$ and $v_j$ are connected. By the inductive hypothesis, after completing the $j$th set, there are at least $j$ edges for all $1\le j\le n$. Hence (by induction, for instance), \[\sum_{v_i, v_j connected} \left\lceil \frac{n_i + n_j - 1}{2} \right\rceil \ge \sum_{i=2}^t \left\lceil \frac{n_i + n_{i-1} - 1}{2} \right\rceil + n_t\] which is greater than or equal to $ \sum_{i=1}^t n_i = a = |A|$ by Lemma 2 below. Hence, $|D(A)| \ge |A|$, as desired.
Lemma 1: Given two sets of reals $X = \{x_1, x_2, x_3, \cdots , x_k\}$ and $Y = \{y_1, y_2, y_3, \cdots , y_l\}$, the set containing the distinct values of $|x_i - y_j|$, where $i$ ranges from $1$ to $k$ inclusive and $j$ ranges from $1$ to $l$ inclusive, contains at least $\left\lceil \frac{k+l- 1}{2} \right\rceil$ elements.
Proof: It suffices to show that there are at most $k + l - 1$ elements in the set consisting of distinct values of $x_i - y_j$. Proceed by induction on $k + l$ to prove this. If $k +l = 2$, this is clear. Suppose it is true for all $k, l$ so that $k + l\le r - 1$, and we will show that it holds for $k, l$ so that $k + l = r$. Assume that $x_1 < x_2 < x_3 < \cdots < x_k$ and $y_1 < y_2 < y_3 < \cdots < y_l$. If $\min\{k , l \} = 1$, suppose $k = 1$, so the elements $(y_i - x_1)$, for all $1\le i\le l$ are pairwise distinct and lie in our set of differences, thereby yielding $l$ differences, as claimed. Now, suppose $\min\{k, l\} > 1$. If $X' = X - x_k$, then there are at least $k + l - 2$ distinct values among differences between elements of $X'$ and $Y$ due to the inductive hypothesis. Now, $x_k - y_1 \ge x_k - y_j \ge x_i - y_j$ for all $1\le i\le k$ and $1\le j\le l$, where equality only occurs when $i = k$ and $j = 1$. Thus, $x_k - y_1$ is a new difference, so our set has at least $k + l - 1$ elements, as claimed.
Lemma 2: Given integers $t\ge 2$ and $1\le n_1 \le n_2 \le n_3 \le \cdots \le n_t$, \[\sum_{i=2}^t \left\lceil \frac{n_i + n_{i-1} - 1}{2} \right\rceil + n_t \ge \sum_{i=1}^t n_i\]
Proof: Proceed by induction on $t$. Consider the base case, when $t = 2$. If $n_1 = n_2$, then $\left\lceil \frac{n_1 + n_2 - 1}{2} \right\rceil = n_1$, so \[\left\lceil \frac{n_1 + n_2 - 1}{2} \right\rceil + n_2 = n_1 + n_2\] as claimed. If $n_1 > n_2$, then \[\left\lceil \frac{n_1 + n_2 - 1}{2} \right\rceil + n_2 \ge \frac{n_1 + n_1 + 1 - 1}{2} + n_2 = n_1 + n_2\] The base case is thus proven. Now suppose that result holds for $t = r - 1$, and we shall prove the result for $t = r$. If $n_{r-1} = n_r$, then \[\sum_{i=2}^r \left\lceil \frac{n_i + n_{i-1} - 1}{2} \right\rceil + n_r = \sum_{i=2}^{r-1} \left\lceil \frac{n_i + n_{i-1} - 1}{2} \right\rceil + n_{r-1} + \left\lceil \frac{n_{r-1} + n_r}{2} \right\rceil \] \[\ge \sum_{i=1}^{r-1} n_i + n_r = \sum_{i=1}^r n_i\] If $n_r > n_{r-1}$, then \[\sum_{i=2}^r \left\lceil \frac{n_i + n_{i-1} - 1}{2} \right\rceil + n_r = \sum_{i=2}^{r-1} \left\lceil \frac{n_i + n_{i-1} - 1}{2} \right\rceil + n_r + \left\lceil \frac{n_{r-1} + n_r - 1}{2} \right\rceil \] \[\ge \sum_{i=2}^{r-1} \left\lceil \frac{n_i + n_{i-1} - 1}{2} \right\rceil + \frac{n_{r-1} + n_{r-1} + 1 -1}{2} + n_r \ge \sum_{i=1}^r n_i \] by the inductive hypothesis. Hence, the lemma is proven.
anantmudgal09
17.12.2015 02:30
........
randomgreenblue
23.09.2024 00:18
Induct on $n$ with $n=1$ case being trivial. Below we assume $n>1$. Let $B=\{(a_1, \ldots, a_{n-1}): \text{there exists }a_n\in\mathbf{R} \text{ such that }(a_1, \ldots, a_n)\in A\}$. For $\mathbf{b}\in B$, let $A(\mathbf{b}) = \{(a_1, \ldots, a_{n-1}, a_n)\in A: (a_1, \ldots, a_{n-1})=\mathbf{b}\}$. For $\mathbf{b}, \mathbf{b}'\in B$, let $D(\mathbf{b}, \mathbf{b}')= \{\gamma(\mathbf{a}_1, \mathbf{a}_2): \mathbf{a}_1\in A(\mathbf{b}), \mathbf{a}_2\in A(\mathbf{b}')\}$; it is a subset of $D(A)$. Proposition. We have \[ |D(\mathbf{b}, \mathbf{b}')|\geq \min(|A(\mathbf{b})|, |A(\mathbf{b}')|). \]
Let $A(\mathbf{b}) = \{(\mathbf{b}, x_1), \ldots, (\mathbf{b}, x_p)\}, x_1<\cdots<x_p$ and $A(\mathbf{b}') = \{(\mathbf{b}', x_1'), \ldots, (\mathbf{b}', x_q')\}, x_1'<\cdots<x_q'$. Assume (switch $\mathbf{b}$ and $\mathbf{b}'$ if necessary) $x_1 \leq x_1'$. Then the $q$ vectors $\gamma((\mathbf{b}, x_1), (\mathbf{b}', x_i')) = (\gamma(\mathbf{b}, \mathbf{b}'), x_i' - x_1), i=1, \ldots, q$ are pairwise different; hence $|D(\mathbf{b}, \mathbf{b}')|\geq q= |A(\mathbf{b}')|\geq \min(|A(\mathbf{b})|, |A(\mathbf{b}')|)$.
Let $B=\{\mathbf{b}_1, \ldots, \mathbf{b}_m\}$. Proposition. There are $m$ pairs $(s_1, t_1), \ldots, (s_m, t_m)$ such that: $\bullet\ 1\leq s_i, t_i\leq i$; $\bullet\ \gamma(\mathbf{b}_{s_1}, \mathbf{b}_{t_1}), \ldots, \gamma(\mathbf{b}_{s_m}, \mathbf{b}_{t_m}) $ are pairwise distinct.
Assume $2\leq l\leq m$ and we have chosen pairs $(s_1, t_1), \ldots (s_{l-1}, t_{l-1})$ such that $1\leq s_i, t_i \leq i$ and that $\gamma(\mathbf{b}_{s_1}, \mathbf{b}_{t_1}), \ldots, \gamma(\mathbf{b}_{s_{l-1}}, \mathbf{b}_{t_{l-1}}) $ are pairwise distinct. We can choose $1\leq s_l, t_l \leq l$ such that $\gamma(\mathbf{b}_{s_l}, \mathbf{b}_{t_l})\notin \{\gamma(\mathbf{b}_{s_1}, \mathbf{b}_{t_1}), \ldots, \gamma(\mathbf{b}_{s_{l-1}}, \mathbf{b}_{t_{l-1}})\}$, since $|D(\{\mathbf{b}_1, \ldots, \mathbf{b}_l\})| = |\{\gamma(\mathbf{b}_i, \mathbf{b}_j): 1\leq i,j\leq l\}| \geq l$ by induction hypothesis.
The proof is completed by picking $s_1=t_1=1$ and successively performing the above operation for $l=2, \ldots, m$.
The $m$ subsets $D(\mathbf{b}_{s_i}, \mathbf{b}_{t_i}), i=1, \ldots, m$ of $D(A)$ are pairwise disjoint. Assume (by permuting indices if necessary) $|A(\mathbf{b}_1)|\geq\cdots\geq|A(\mathbf{b}_m)|$. \begin{align*} |D(A)|&\geq\sum_{i=1}^m|D(\mathbf{b}_{s_i}, \mathbf{b}_{t_i})|\\ &\geq \sum_{i=1}^m\min(|A(\mathbf{b}_{s_i})|, |A(\mathbf{b}_{t_i})|)\\ &(s_i, t_i \leq i)\\ &\geq\sum_{i=1}^m|A(\mathbf{b}_i)|\\ &=|A|. \end{align*}