Let $n$ be a positive integer. For each $4n$-tuple of nonnegative real numbers $a_1,\ldots,a_{2n}$, $b_1,\ldots,b_{2n}$ that satisfy $\sum_{i=1}^{2n}a_i=\sum_{j=1}^{2n}b_j=n$, define the sets \[A:=\left\{\sum_{j=1}^{2n}\frac{a_ib_j}{a_ib_j+1}:i\in\{1,\ldots,2n\} \textup{ s.t. }\sum_{j=1}^{2n}\frac{a_ib_j}{a_ib_j+1}\neq 0\right\},\]\[B:=\left\{\sum_{i=1}^{2n}\frac{a_ib_j}{a_ib_j+1}:j\in\{1,\ldots,2n\} \textup{ s.t. }\sum_{i=1}^{2n}\frac{a_ib_j}{a_ib_j+1}\neq 0\right\}.\]Let $m$ be the minimum element of $A\cup B$. Determine the maximum value of $m$ among those derived from all such $4n$-tuples $a_1,\ldots,a_{2n},b_1,\ldots,b_{2n}$. Proposed by usjl.
Problem
Source: 2021 Taiwan TST Round 1 Mock Day 2 P4
Tags: Inequality, algebra, Taiwan
20.03.2021 19:44
The maximum of $m$ is $\frac{n}{2}.$ This can be achieved by $a_1=\cdots=a_n=b_1=\cdots=b_n=1,a_{n+1}=\cdots=a_{2n}=b_{n+1}=\cdots=b_{2n}=0.$ All elements in $A \cup B$ are $\frac{n}{2}.$ Now let's prove the inequality. Wlog $a_1,\cdots,a_k>0,b_1,\cdots,b_{\ell}>0$ and others are $0$. And wlog further $k \ge \ell$. Taking sum for the $k$ elements in $A$, it suffices to prove \begin{align*} \sum_{i=1}^{k} \sum_{j=1}^{\ell} \frac{a_ib_j}{a_ib_j+1} &\le k \cdot \frac{n}{2} \\ \Leftrightarrow \sum_{i=1}^{k} \sum_{j=1}^{\ell} \frac{1}{a_ib_j+1} &\ge k \cdot ( \ell - \frac{n}{2} ) \end{align*}Now if $ \ell \le \frac{n}{2}$ we are done. Otherwise, apply Cauchy-Schwarz, \begin{align*} \sum_{i=1}^{k} \sum_{j=1}^{\ell} \frac{1}{a_ib_j+1} &\ge \frac{(k \ell)^2}{\sum_{i=1}^{k} \sum_{j=1}^{\ell} (a_ib_j+1)} \\ &= \frac{(k \ell)^2}{n^2+k \ell} \end{align*}So we are left to prove \begin{align*} &\frac{(k \ell)^2}{n^2+k \ell} \ge k( \ell-\frac{n}{2} ) \\ \Leftrightarrow &\frac{nk}{2} (n^2+k \ell -2n \ell) \ge 0 \end{align*}which is clear since $n^2+ k \ell \ge n^2 + \ell^2 \ge 2n \ell$.
28.03.2021 12:52
Chinese because I lazy to translate(? https://hackmd.io/@sine/2021_Taiwan_TST_1-M4
02.03.2024 16:10
Missed the fact that if some of them are $0$ they aren't counted in the set... but a quick fix solves this. We are free to permutate $a_i, b_j$ so without loss of generality suppose $a_i = 0 \text{ if } i >x, b_j = 0 \text{ if } j>y$ and otherwise nonzero. Bounding $\sum_{j=1}^y \frac{a_ib_j}{a_ib_j+1} = y - \sum_{j=1}^y \frac{1}{a_ib_j+1} \leq y-\frac{(\sum_{j=1}^y 1)^2}{\sum_{j=1}^y a_ib_j+1}=y-\frac{y^2}{y+na_i}.$ where the inequality follows from Cauchy-Schwarz. Call this quantity $A_i$, then $\sum_{i=1}^x A_i \leq xy-y^2 \sum_{i=1}^x \frac{1}{y+na_i} \leq xy-y^2 \frac{(\sum_{i=1}^x 1)^2}{\sum_{i=1}^x y+na_i} = xy-\frac{x^2y^2}{xy+n^2} = \frac{xyn^2}{xy+n^2}$, so by PHP at least one $$ 0<A_i \leq \frac{yn^2}{xy+n^2}.$$Note that $=$ can hold simply by setting all nonzero terms the same, that is to say, out of all initial setups of $a_i, b_j$ with $x, y$ nonzero terms respectively, the minimum of $A \cup B$ is precisely $$\frac{xyn^2}{(xy+n^2) \times \max \{x, y\}}.$$So the maximum of the minimum of $A \cup B$ among all setups is precisely the maximum of the quantity above, with $1 \leq x, y \leq n$. W.L.O.G. $x \leq y$ then $$\frac{xyn^2}{(xy+n^2) \times \max \{x, y\}} = \frac{xn^2}{xy+n^2} \leq \frac{xn^2}{x^2+n^2} \leq \frac{n}{2}.$$Equality is held when $x=y=n$.
25.07.2024 05:40
给定正整数$n$,对任意满足$\sum_{i=1}^{2n}a_i=\sum_{j=1}^{2n}b_j=n$的$4n$元非负实数组$a_1,\ldots,a_{2n}$,$b_1,\ldots,b_{2n}$定义集合\[A:=\left\{\sum_{j=1}^{2n}\frac{a_ib_j}{a_ib_j+1}:i\in\{1,\ldots,2n\} \textup{ s.t. }\sum_{j=1}^{2n}\frac{a_ib_j}{a_ib_j+1}\neq 0\right\},\]\[B:=\left\{\sum_{i=1}^{2n}\frac{a_ib_j}{a_ib_j+1}:j\in\{1,\ldots,2n\} \textup{ s.t. }\sum_{i=1}^{2n}\frac{a_ib_j}{a_ib_j+1}\neq 0\right\}.\]设$m$是集合$A\cup B$的最小元素,求$m$的最大可能值