Probabilistic method yay A1 without flavortext wrote: Find the smallest real number $D$ with the following property: for any positive real numbers $a_1$, $\dots$, $a_{100}$ with sum $100$, there exist nonnegative integers $b_1$, $\dots$, $b_{100}$ with sum $100$ such that \[ |a_1 - b_1| + \dots + |a_{100} - b_{100}| \le D. \]

The answer is $\boxed{50}$. This number is optimal for the construction: 99 bowls with size $\frac12$, and a bowl with size $\frac{101}2$. Now we will show $D\leq 50$. Let the sum of dissatisfaction be $2t$, so that both the sum of excess food in each bowl and the sum of remaining space in each bowl are both $t$. FTSOC, assume that for some configuration of capacities, the optimal food distribution gives $2t>50$. Suppose there are $x$ pokemon that receives excess food. Observe that we have\[\frac tx+\frac{t}{100-x}=t\cdot\frac{100}{x(100-x)}\geq t\cdot\frac{100}{2500}>1,\]so there exist a bowl with excess food and a bowl with remaining space with the sum of dissatisfaction greater than 1. However, this implies we can move 1 kg of food from the excess bowl to the other bowl and get a better distribution, a contradiction.

This nice problem was proposed by Oleksii Masalitin from Ukraine.

We ALMOST had a Pokémon problem for the IMO in Japan. We were on the verge of greatness. We were this close.

non probabilistic pure ineq sol

By the way, the idea is quite similar to APMO 2006 P1.

The answer is $D=50$. We'll denote by $C_i$, $D_i$, and $N_i$ the $i$-th Pokémon's capacity, dissatisfaction level, and food received (in kilograms), respectively. To show $D\geq 50$, we can take $C_i=1/2$ for $i\leq 50$ and $C_i=3/2$ for $i>50$. This guarantees $D_i\geq 1/2$ for all $i$, hence $D\geq 50$. To show $D=50$ suffices, suppose it doesn't for some collection of $C_i$ and take the distribution of food which minimizes $D$ (pick one at random if there is more than one distribution achieving the same $D$). Such a distribution exists as there are finitely many ways Professor Oak can split $100$ kilograms of food into $100$ parts of non-negative integer weight. For this distribution, we can partition the Pokémon depending on the sign of $C_i-N_i$. If we denote \[S_+=\{i\mid C_i-N_i\geq 0\}\quad \text{and}\quad S_-=\{i\mid C_i-N_i < 0\},\]then clearly $\sum\limits_{i\in S_+} D_i = \sum\limits_{i\in S_-} D_i$ as $\sum\limits_{i=1}^{100} C_i = 100 = \sum\limits_{i=1}^{100} N_i$. Hence, assuming that $D>50$, we have that the sum of the $D_i$ in both $S_+$ and $S_-$ is larger than $25$. Therefore: \[\max\limits_{\substack{i\in S_+ \\ j\in S_-}} (D_i+D_j) \geq \frac{\sum\limits_{i\in S_-} D_i}{|S_-|} + \frac{\sum\limits_{i\in S_+} D_i}{|S_+|}>\frac{25}{|S_-|}+\frac{25}{|S_+|}\geq 1.\]Taking these $i\in S_+$ and $j\in S_-$, such that $D_i+D_j>1$, we claim that switching $(N_i, N_j)$ for $(N_i-1, N_j+1)$ reduces $D$. Note that $D_i=C_i-N_i = a > 0$ (equality can't occur as this would mean $D_i=0$ for all $i\in S_+$, which leads to $D=0$) and $D_j=C_j-N_j = -b<0$. Given that $a+b>1$ and $a, b>0$, out claim from above is just \[|a-1|+|1-b| < a + b.\]If either $a\geq 1$ or $b\geq 1$, this is obvious as after the local switch one of the moduli decreases by $1$ and the other can't increase by more than one as $a,b>0$. If $a, b<1$, we have: \[|a-1|+|1-b|=2-a-b<a+b\]which is a contradiction with our initial assumption, so we're done.

carefully wrote: We ALMOST had a Pokémon problem for the IMO in Japan. We were on the verge of greatness. We were this close.

The answer is $50$. For the construction, set the bowl capacities to \[\underbrace{0.5, 0.5, \dots, 0.5}_{99\text{ copies}}, 50.5;\]then clearly each Pokémon has a dissatisfaction level of at least $0.5$, so the sum of the dissatisfaction levels is at least $50$. For the bound, first perform the following optimisations: if a Pokémon has an integer bowl capacity, then give it that amount of food and delete it; if a Pokémon has a non-integer bowl capacity $c > 1$, then give it $\lfloor c \rfloor$ kilograms of food and replace $c$ with $\{c\}$, the fractional part of $c$. These operations do not change the dissatisfaction levels of the Pokémon. Now suppose there are $n$ Pokémon left; let $c_1$, $c_2$, $\dots$, $c_n$ be the bowl capacities such that $c_1 \leq c_2 \leq \dots \leq c_n < 1\ (\spadesuit)$ and suppose they sum to $k$, which must clearly be an integer. We claim the sum of the dissatisfaction levels is at most $n / 2$. Indeed, we will show that setting \[a_1 = a_2 = \dots = a_{n - k} = 0, a_{n - k + 1} = a_{n - k + 2} = \dots = a_n = 1\]works. Note the sum of the dissatisfaction levels is \begin{align*} \sum_{i = 1}^n |c_i - a_i| &= \sum_{i = 1}^{n - k} c_i + \sum_{i = n - k + 1}^n (1 - c_i) \\ &= k + \sum_{i = 1}^{n - k} c_i - \sum_{i = n - k + 1}^n c_i \\ &= \sum_{i = 1}^n c_i + \sum_{i = 1}^{n - k} c_i - \sum_{i = n - k + 1}^n c_i \\ &= 2 \sum_{i = 1}^{n - k} c_i \end{align*}for the above choice of $a_i$. But by $(\spadesuit)$ we have \begin{align*} 2 \sum_{i = 1}^{n - k} c_i &\leq \frac{2(n - k)}{n} \sum_{i = 1}^n c_i \\ &= \frac{2(n - k)}{n} \cdot k \\ &= \frac 2n \cdot k(n - k) \\ &\leq \frac 2n \cdot \left(\frac n2 \right)^2 \\ &= \frac n2. \end{align*}by AM-GM. It then follows that the sum of the dissatisfaction levels before optimisation is equal to the sum of the of the dissatisfaction levels after optimisation, which is at most $n / 2$ and thus at most $100 / 2 = 50$.

Answer: $D=50$ For the construction fill each bowl with fractional part $\frac{1}{2}$. Let the bowls have integral parts $n_1,n_2,\dots, n_{100}$ and fractional parts $x_1,x_2,\dots, x_{100}$. WLOG assume that $x_1\geq x_2\geq \dots \geq x_{100}$. Let $S=x_1+x_2+\dots+x_{100}$ ($S$ is an integer). Place $n_i+1$ kilograms of food in the first $S$ bowls and $n_i$ kilograms of food in the last $100-S$ bowls. Then we have $$S-(x_1+x_2+\dots +x_S)+(x_{S+1}+x_{S+2}+\dots+x_{100})\leq S-\frac{S^2}{100}+\frac{(100-S)S}{100}=\frac{(100-S)S}{50}\leq 50$$

We claim the answer is $50$. This is achievable by taking capacities $\frac 12, \frac 12, \ldots, 50 \frac 12$. Cleary the dissatisfaction of each pokemon is at least $\frac 12$ which implies that the total dissatisfaction is at least $50$. We will show the bound. Let $f_i = \{c_i\}$ where $c_i$ is the capacity of each bowl and $\{x\}$ denotes the fractional part of $x$. WLOG that $f_1 \le f_2 \le \ldots \le f_{100}$. Let the amount of food for each pokemon to be $n_i$ for pokemon $i$. There must be some $1 \le M \le 100$ such that we can pick $n_i = \lfloor c_i \rfloor$ for $i \le M$ and $n_i = \lfloor c_i \rfloor + 1$ for $i > M$. Since we have \[\sum_{i=1}^M f_i = \sum_{i=M+1}^{100} 1 - f_i \]realize that if \[\sum_{i=1}^{100} |a_i - b_i| = \sum_{i = 1}^M f_i + \sum_{i = M+1}^{100} 1 - f_i > 50 \]then we an find $f_i$ and $f_j$ with $i \le M$ and $j > M$ satisfying \[f_i + (1-f_j) > 1\]However, this means that $f_i >f_j$, which is a contradiction, so we are done.

OG, The Answer is 50 Proof: Consider the case where, the capacities of the bowls are $0.5, 1.5, 0.5 \cdots1.5$ Now since Professor Oak gives an integral value of food(bhojan). Thus, dissatisfaction level of each Pokemon is at least 0.5 in this case Thus sum of all dissatisfaction levels $= D \geq (0.5)(100)= 50$ Consider the following strategy to be used by Professor Oak: 1. Professor Oak segregates the pokemons into 2 sets $A,B$. $A$ contains pokemons with bowls having capacities(in kilograms) having fractional part $\neq 0.5 $, $B$ contains the pokemons with bowls having capacities(in kilograms) whose fractional part is 0.5 2. Let $x$ be the capacity of any pokemon's bowl in set $A$. Professor Oak gives $\lfloor x \rfloor$ kilograms of food, if the fractional part of x is less than 0.5, otherwise, gives $\lfloor x \rfloor + 1$ kilograms of food. 3.For set $B$(Let $y$ denote the capacity of any pokemon's bowl in set $B$) , Professor choses wisely either to give $\lfloor y \rfloor$ kilograms of food or $\lfloor y \rfloor + 1$ kilograms of food to each pokemon such that the total food given by him to all pokemons is 100kg. Now to prove that Professor Oak can do such a wise selection: Let professor Oak give $k$ kilograms of food(bhojan) to $n$ pokemons in set $B$ and let the sum of capacities of bowls of pokemons in set $B$ be denoted by $S_B$, define $S_A$ similarly. Professor Oak then gives $m$ kilograms of food(bhojan) to $100-n$ pokemons in set $A$. since, Oak Sir gives either $\lfloor x \rfloor + 1$ or $\lfloor x \rfloor $ kg of food(bhojan). Thus. diferrence of food given to each bowl of pokemons in set $A$and the bowl's capacity is less than 0.5. So $100-n-(0.5)(100-n)= 50-\frac{n}{2} \leq m \leq 100-n+(0.5)(100-n)= 150-\frac{3n}{2}$. note that $m$ is an integer. Now, Oak Sir gives either $\lfloor x \rfloor + 1$ or $\lfloor x \rfloor $ kg of food(bhojan) to pokemons in set $B$ depending on his choice . Thus. diferrence of food given to each bowl of pokemons in set $A$and the bowl's capacity is 0.5. So we get, $n-(0.5)n= \frac{n}{2} \leq k \leq n+(0.5)n= \frac{3n}{2}$ Since, he can select in any order whether to give floor of the capacity or floor of the capacity +1 for all bowls of pokemons in set $B$. Therefore $k$ is surjective i.e. it can take any integral value that the professor wants between $\frac{n}{2}$ and $\frac{3n}{2}$.( FOR INSTANCE IF PROFESSOR OAK WANTS TO SET $k= \frac{n}{2}$ then he would simply give floor function of the capacities of bowls of all pokemons in set $B$.) Now, whatever $k$ is in any case professor Oak can do a wise selecetion in set $B$ such that he can set $m=100-k$ as $\frac{n}{2} \leq 50+ \frac{n}{2} \leq 100-k \leq \frac{3n}{2} - 50 \leq \frac{3n}{2}$. Since $100-k$ lies between $\frac{n}{2}$ and $\frac{3n}{2}$, Thus $m$ can be set equal to $100-k$ by a specififc selection of giving floor function of or floor +1 of capacities of bowls in set $B$ as we prooved $m$ was surjective. Now, the above strategy easily assures that $D \leq (0.5)(100) = 50$. Thus, $D=50$

CWMI 2015/1

We claim the answer is $D= \boxed{50}$. Define $a_i = b_i + c_i$, such that $\lfloor a_i \rfloor $ and $c_1 \le c_2 \le \dots \le c_{99} \le c_{100} $. Say the $i$th pokemons bowl has capacity $a_i$ kilograms. We claim the following method makes the sum of the dissatisfaction levels less than or equal to $50$. For $1 \le i \le 100- \sum_{i=1}^{100} c_i$ assign the $i$th pokemon $\lfloor a_i \rfloor$ kilograms of food. Otherwise assign the $i$th pokemon $\lceil a_i \rceil$ kilograms of food. Now observe that the sum of the dissatisfaction levels is (letting $x=\sum_{i=1}^{100} c_i $) $$c_1+c_2+ \cdots + c_{100-x}+ x-c_{101-x}-c_{102-x}- \cdots- c_{100}= 2(c_1+ c_2 + \cdots + c_{100-x}) \le \frac{2(100-x)x}{50} \le 50.$$Observe that if $a_1= a_2 = \cdots = a_{50} =.5, a_{51}= a_{52} \cdots = a_{100}$ then the dissatisfaction levels are all at least $.5$ which gives a sum of at least $50$ so $D=50$ is indeed minimal.

this problem SUCKS. why would you ever use the inferior system. jokes aside nice and easy c1 man. I claim the answer is $50$. Construction forcing $D \ge 50$: Consider $99$ Pokemon receiving bowls of $\frac 12$ and the last one receiving a bowl with $\frac{101}{2}$. Clearly, each dissatisfaction level is at least $\frac 12$, so the total is at least $50$. Proof we can assign to get a dissatisfaction at most $50$: Let $b_i$ be the bowl size of Pokemon $i$. First, give each Pokemon $\lfloor b_i \rfloor$ kg of food. Let the total number of food assigned be $a$. We then give $100 - a$ Pokemon $1$ extra kg of food, precisely the $100 - a$ with maximal values of $b_i - \lfloor b_i \rfloor = c_i$. We claim this is sufficient. Note the total amount of food given out is $100$ The total dissatisfaction at before giving the extra food was $100 - a$, then we added $1 - 2c_i$ dissatisfaction for each Pokemon that received extra food, so we just have to prove $100 - a - \sum c_i \le 25$. Let $1 - c_i = d_i$, then we have to prove $\sum d_i \le 25$ where the sum is over the relevant indices that were given extra food, note all $d_i$ sum to $a$, so the desired sum is at most $\frac{a}{100}(100 - a)$ (we are taking the minimal $d_i$), by quadratic maximization this is always less than $25$.

Super nice problem The answer is 50, construction given by 99 copies of 0.5 and one copy of 50.5 Bound is just smart probabilistic method

funny story

Here's a pretty standard local solution. I still think this is a bit hard for first shortlist problem and definitely not algebra. The answer is $50$. The flavortext is confusing, so we rephrase the problem as the following: Rephrase wrote: Given any real numbers $a_1, a_2, \dots, a_{100}$ summing to $100$, find the greatest real number $D$ such that one can always find nonnegative integers $b_1, b_2, \dots, b_{100}$ summing to $100$ such that \[|a_1-b_1| + |a_2-b_2| + \cdots + |a_{100}-b_{100}| \leq D.\] Construction: Take $a_{2n-1} = 0.5$ and $a_{2n} = 1.5$ for every $1 \leq n \leq 50$. Then clearly $|a_i-b_i| \geq 0.5$ for each $i$. Bound: Let $(b_1, b_2, \dots, b_{100})$ be a $100$-tuple for the given set of $a_i$'s such that the desired sum is minimized. We call an index $i$ small if $b_i < a_i$ for that $i$ and big otherwise. Assume without loss of generality that there are at least as many small indices as big indices, and let $x_i = |a_i - b_i|$ for each $i$. Assume for the sake of contradiction that \[x_1+x_2+\cdots+x_{100} > 50.\]Claim: There exists a small index $i$ and a big index $j$ such that $x_i+x_j > 1$. Proof: Assume otherwise. Let $|S| = k$ be the set of all small indices and $B$ be the set of all big indices. Then \[\sum_{i=1}^{100} x_i =\sum_{i \in S} x_i + \sum_{j \in B} x_j \leq \sum_{i \in S} x_i + \sum_{j \in S' \subseteq S} (1-x_j)\]for any $100-k$-element subset $S'$ of $S$. This sum is bounded above by the sum of $100-k$ and the $2k-100$ smallest elements of $S$, i.e. the elements in $S \setminus S'$. Claim: These elements are all at most $0.5$. Proof: Assume otherwise. Then all the elements in $S'$ are all greater than $0.5$, so all the elements in $B$ are less than $0.5$ by assumption. But then the sum of $x_j$ across big indices is strictly less than the sum of $x_i$ across small indices, contradicting $a_1+a_2+\cdots+a_{100} = b_1+b_2+\cdots+b_{100}$. Thus \[x_1+x_2+\cdots+x_{100} \leq 100 - k + \frac 12(2k-100) = 50,\]contradiction. $\blacksquare$ So we can instead designate $i$ big and $j$ small and decrease the sum, which contradicts mimimality. This finishes the proof.

Sketch: Answer is 50, take everything with frac part = 1/2 To prove bound, calculate $\mathbb{E}[\sum D_i]$ and win by AM-GM