pow:problem3f23
Differences
This shows you the differences between two versions of the page.
| pow:problem3f23 [2023/10/08 15:22] – created mazur | pow:problem3f23 [2023/10/10 20:23] (current) – mazur | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| + | <box 85% round orange| Problem 3 (due Monday, October 9)> | ||
| + | |||
| + | Given a sequence $a_1, a_2,\ldots, a_n$ of $n$ real numbers we construct | ||
| + | a new sequence of $n-1$ numbers as follows: first we set | ||
| + | $b_i=\max(a_i, | ||
| + | one index $i$ and add $1$ to $b_i$. This is our new sequence. After | ||
| + | repeating this | ||
| + | operation $n-1$ times we arrive at a single number $A$. Prove that if | ||
| + | $a_1+\ldots +a_n=0$, then $A\geq \log_2 n$. | ||
| + | |||
| + | Here $\max(a,b)$ denotes the | ||
| + | larger of the numbers $a,b$. | ||
| + | |||
| + | </ | ||
| + | |||
| + | We did not receive any solutions. The key idea for our solution is to observe that the quantity $2^{a_1}+\ldots + 2^{a_n}$ is a monovariant for our operation on sequences, i.e. that this quantity computed for the new sequence | ||
| + | is larger or equal than the quantity for the original sequence. It follows that $2^A\geq 2^{a_1} +\ldots + 2^{a_n}$. | ||
| + | By the AMGM inequality (the arithmetic mean is always greater or equal than the geometric mean), we have | ||
| + | $2^{a_1} +\ldots + 2^{a_n}\geq n$, hence $A\geq \log_2n$. For a detailed solution and some additional discussion | ||
| + | see the following link {{: | ||