Find the smallest real number $M$ with the following property: Given nine nonnegative real numbers with sum $1$, it is possible to arrange them in the cells of a $3 \times 3$ square so that the product of each row or column is at most $M$. Evan O' Dorney.
Problem
Source: ELMO Shortlist 2010, A7
Tags: algebra proposed, algebra
CeuAzul
19.10.2016 17:24
Hello,I got $\boxed{\frac{1}{432}}$ wrong! Your sincerely CeuAzul
PSY-Math
19.10.2016 19:18
I think $\frac{1}{729}$.
pco
19.10.2016 19:26
PSY-Math wrote: I think $\frac{1}{729}$. It cant be $\frac 1{729}$ : look for example at $\left(\frac 12,\frac 1{16},...\frac 1{16}\right)$. You'll get at least one row whose product is $\frac 12\frac 1{16}\frac 1{16}$ $=\frac 1{512}>\frac 1{729}$
CeuAzul
20.10.2016 14:17
Oh sorry I'll change my answer to $\boxed{\frac{4}{1323}}$ $\{0,\frac{1}{3},\frac{7}{27},\frac{7}{27},\frac{7}{27},\frac{7}{27},\frac{7}{27},\frac{7}{27},\frac{7}{27}\}$ Your sincerely CeuAzul
pco
20.10.2016 14:50
CeuAzul wrote: Oh sorry I'll change my answer to $\boxed{\frac{4}{1323}}$ It cant be $\frac 1{1323}$ : look for example at $\left(\frac 12,\frac 1{16},...\frac 1{16}\right)$. You'll get at least one row whose product is $\frac 12\frac 1{16}\frac 1{16}$ $=\frac 1{512}>\frac 1{1323}$
CeuAzul
20.10.2016 15:13
I said $\boxed{\frac{4}{1323}}$ dude Your sincerely CeuAzul
pco
20.10.2016 15:16
CeuAzul wrote: I said $\boxed{\frac{4}{1323}}$ dude Yep, sorry
CeuAzul
20.10.2016 16:32
Proof: WLOG $a_1 \le a_2 \le \cdots \le a_9,\sum_{i=1}^{9}a_i=1$ We form these numbers like below \[\begin{pmatrix} a_7&a_4&a_3\\a_8&a_2&a_5\\a_1&a_9&a_6 \end{pmatrix}\]Then we prove that each row & column is okay
Since $7(a_3+a_4+a_7) \le 3(a_3+a_4+\cdots+a_9) \le 3(a_1+a_2+\cdots+a_9)=3 \hookrightarrow a_3+a_4+a_7 \le \frac{3}{7}$
By AM-GM $a_3a_4a_7 \le \frac{1}{343} <\frac{4}{1323}$
If $a_2+a_5+a_8 \le \frac{3}{7}$ it's obvious;
If $a_2+a_5+a_8 > \frac{3}{7}$,then we have $a_3+a_6+a_9 \ge a_2+a_5+a_8 > \frac{3}{7} \Longrightarrow a_4+a_7 \le a_1+a_4+a_7<\frac{1}{7} \Longrightarrow a_2+a_5 \le a_4+a_7<\frac{1}{7}$
Since $a_8 \le a_9 \Longrightarrow a_8 \le \frac{1}{2} \Longrightarrow a_2a_5a_8 \le (\frac{a_2+a_5}{2})^2a_8 \le (\frac{1}{14})^2 \cdot \frac{1}{2}<\frac{4}{1323}$
Let $a_1=\alpha,a_6=\beta \Longrightarrow a_1+a_2+\cdots+a_5 \ge 5 \alpha,a_6+a_7+a_8 \ge 3 \beta \Longrightarrow a_9 \le 1-5 \alpha -3 \beta$
$\Longrightarrow a_1a_6a_9 \le \alpha \cdot \beta (1-5 \alpha -3 \beta) \le \frac{1}{15} \cdot (\frac{1}{3})^3<\frac{4}{1323}$
Let $a_1=t \Longrightarrow a_1+a_2+\cdots+a_6 \ge 6t \Longrightarrow a_7+a_8+a_9 \le 1-6t$
$\Longrightarrow a_7+a_8 \le \frac{2}{3}(1-6t) \Longrightarrow a_1a_7a_8 \le a_1 \cdot (\frac{a_7+a_8}{2})^2=\frac{1}{9}t \cdot (1-6t)^2 \le \frac{2}{729}<\frac{4}{1323}$
Let $a_4=t \Longrightarrow a_2+a_3+\cdots+a_8 \le 1-t$
But $a_2+a_3+\cdots+a_8 =(a_2+a_8)+(a_3+a_7)+(a_4+a_6)+a_5 \ge \frac{7}{2}(a_2+a_4)$
$\Longrightarrow a_2+a_4 \le \frac{7}{2}(1-t) \Longrightarrow a_2a_4a_9 \le (\frac{a_2+a_4}{2})^2 \cdot t =\frac{1}{49}(1-t)^2t \le \frac{1}{49} \cdot \frac{1}{2} \cdot (\frac{2}{3})^3=\frac{4}{1323}$
Exactly the same proof as 1st row
This solution isn't mine.
Your sincerely CeuAzul