We say that a $2023$-tuple of nonnegative integers $(a_1,\hdots,a_{2023})$ is sweet if the following conditions hold: $a_1+\hdots+a_{2023}=2023$ $\frac{a_1}{2}+\frac{a_2}{2^2}+\hdots+\frac{a_{2023}}{2^{2023}}\le 1$ Determine the greatest positive integer $L$ so that \[a_1+2a_2+\hdots+2023a_{2023}\ge L\]holds for every sweet $2023$-tuple $(a_1,\hdots,a_{2023})$ Ivan Novak
Problem
Source: EMC 2023 Juniors P4
Tags: emc, algebra, Inequality, 2023
19.12.2023 01:41
Let us take the $2023$-tuple $(a_1,\hdots,a_{2023})$, which achieves the minimal value of $L$ and out of all of these the minimal value of $S=\frac{a_1}{2}+\frac{a_2}{2^2}+\hdots+\frac{a_{2023}}{2^{2023}}$. Claim 1: This optimal $2023$-tuple has all $a_i$ equal to 0 except for two or one adjacent ones. Suppose that this optimal tuple has at least three $a_i$ which are different then zero, or that it only has two which are not adjacent, we will now use the following algorithm. Given an $a_k, a_j>0$, with $j > k+1$, now we can decrease $a_k,a_j$ by $1$ and increase $a_{k+1},a_{j-1}$ by $1$. We can see that this does not change $L$, but this decreases $S$, contradicting minimality of $S$ and $L$. Now we look at the inequality $1)$$\frac{a_l}{2^l}+\frac{a_{l+1}}{2^{l+1}}\le 1$ with $a_l + a_{l+1}=2023$. We want to find the smallest value of $L$, This rewrites as $2023 + a_l\le 2^{l+1}$ It is not difficult to see that the maximal value of $L$ is achieved when it is $a_l=25$ and $l=10$. Now all that is left is to calculate this value of $L$ $L=10*25 + 1998*11= 22228 $ This value of $L$ does not seem very special to me, so my answer might be completely wrong. We can also just repeat the algorithm in step one to get to a case like the one discussed.
21.12.2023 17:58
S_2 wrote: ...This value of $L$ does not seem very special to me, so my answer might be completely wrong... No, It's ok. The solution I found during the tournament (though not as a contestant) was almost the same. You take the tuple $(a_i)$ that minimizes $L:=a_1+2a_2+\dots 2023a_{2023}$ and if there are $a_i,a_j\neq 0, j\ge i+2$ you decrease $a_i$ and $a_j$ by $1$ and increase $a_{i+1}$ by $2$. In this way all the restrictions are also satisfied but $L$ decreases - it doesn't change only if $j=i+2$. So, making transformations like that, we arrive at a situation where all $a_i$ are zeroes except two of them $a_k$ and $a_{k+1}$. This tuple also minimizes $L$. It remains to check the possible values of $k$ which is a routine task. Note that if we drop the requirement $a_i$ being integers, the minimum of $L$ is attained at the same point. Same idea, the set of all tuples complying the conditions is compact, so $\min\, L$ is attained, we decrease $a_i, a_j, j\ge i+2$ by some $\varepsilon>0$ and increase $a_{i+1}$ by $2\varepsilon$.
26.12.2023 00:42
By the way, this problem is actually motivated by a combinatorial question. Suppose you want to form an alphabet on N letters, such that each letter is a binary string, and in such a way that any word can be read in one way, without ambiguities. For example, if your alphabet consists of $/{01, 001, 010/}$, then $01001$ can mean either $01 \mid 001$ or $010 \mid 01$, so there is an ambiguity. However, if your alphabet is $/{01, 001, 1/}$, you can uniquely decompose any word made of these strings into letters. We'll call such an alphabet clear. So now the question is, if you have a clear alphabet of $n$ letters, what's the shortest possible sum of lengths of letters? Then let $a_j$ denote the number of letters of length $j$ in the alphabet. The sequence $a_1, a_2,...$ will be called the signature of an alphabet. The length of the alphabet is then $a_1+2a_2+...$. It can be proven that a clear alphabet on $n$ letters with signature $a_1,a_2..$ exists if and only if $\sum a_i=n$, and $\sum a_i2^{-i}\leq 1$. This reduces the combinatorial problem to this algebraic problem.