USOMO 2020 Problem 2

An empty $2020 \times 2020 \times 2020$ cube is given, and a $2020 \times 2020$ grid of square unit cells is drawn  on each of its six faces. A beam is a $1 \times 1 \times 2020$ rectangular prism. Several beams are placed inside the cube subject to the following conditions:

-- The two $1 \times 1$ faces of each beam coincide with unit cells lying on opposite faces of the cube. (Hence, there are $3 \cdot {2020}^2$ possible positions for a beam.)
-- No two beams have intersecting interiors.
-- The interiors of each of the four $1 \times 2020$ faces of each beam touch either a face of the cube or the interior of the face of another beam.

What is the smallest positive number of beams that can be placed to satisfy these conditions?

This one is easy!

Solution:

We prove it's $3n/2$ for every even $n$, i.e. $3030$ for $n=2020$, followed by construction.

Let $S$ be the set of minimum number of beams. Define a layer as a set of horizontally or vertically adjacent $n^2$ unit cubes. There are $3n$ layers. Consider the $n$ horizontal layers. Either each of them contains a beam in $S$, or none of them does and $S$ consists of $n^2$ vertical beams.

If nothing like the latter case happens in any direction, then each of the $3n$ layers contains a beam in $S$. Every beam is contained in exactly $2$ layers, so $S$ has at least $3n/2$ beams. It could be easily constructed. If the latter case happens in some direction, then $S$ has $n^2$ beams, more than $3n/2$ and so not the minimum.

APMO 2020 Problem 3

Determine all positive integers $k$ for which there exist a positive integer $m$ and a set $S$ of positive integers such that any integer $n > m$ can be written as a sum of distinct elements of $S$ in exactly $k$ ways.

I was totally screwed by a mistake and thought $k=1$. My excuse is that I didn't have a chance to sit down and think about it seriously. So below are just my proof after knowing that $k$ can only be power of two.



We say a number is good if it could be written as the sum of distinct elements of $S$ in exactly $k$ ways.

Let $s_1 \lt s_2 \lt \ldots \lt \ldots$ denote the good numbers in $S$. Let $S_1 \lt S_2 \lt \ldots \lt \ldots$ constitute $S$.

Lemma 1
There does not exist number $x+S_j=S_i+S_k\gt m$ where $x\lt S_j$, $x\notin\{S_i,S_k\}$, and $x$ is good.
Proof
If it does, then $x+S_j$ has at least $k+1$ representations, a contradiction.
$\square$

Lemma 2
For sufficiently large $i$, $2s_i\leq s_{i+1}$.
Proof
If not, let $x=s_{i+1}-s_i \lt s_i$. If $x \gt m$ then $x$ is good and $s_{i+1}$ has at least $k+1$ representations, a contradiction. If $x\leq m$, then given $s_i$ is sufficiently large we can find $S_a \lt y \lt s_i \lt s_{i+1}$ such that $y$ is good and $y+s_i=S_a+s_{i+1}$ which contradicts Lemma 1.
$\square$

With this, let $a=s_i\gt m$ where $2s_j\leq s_{j+1}$ for any $j\ge i$. Let $S'=\{x: x\lt a, x\in S\}$ and $t$ be the sum of elements in $S'$.

Lemma 3 
$t\leq a+m$
Proof
Note that $a+m$ is less than the next element in $S$ after $a$. If $a+m\lt t$, then $t$ has at least $k+1$ representations where $k$ of them come from representations of $t-a$ and an extra from $S'$, a contradiction.
$\square$

Lemma 4
$k$ is a power of two.
Proof
Double count representations using only $S'$. Define $f(n)$ as the number of representations using $S$. For $x\in[0, a-1]$, $f(x)$ completely comes from $S'$. For $x\in[a, a+m]$, $f(x)-f(x-a)$ counts representations using only $S'$. So the quantity

$$
f(0)+f(1)+\ldots+f(a-1)+\left(f(a)-f(0)\right)+\left(f(a+1)-f(1)\right)+\ldots+\left(f(a+m)-f(m)\right),
$$

reduced to $f(m+1)+\ldots+f(a+m)=ak$, is equal to $2^{|S'|}$, therefore $k$ must be a power of two.

$\square$

Finally, for any $k=2^{k'}$, the desired $S$ could be $S=\{3^0,3^1,\ldots,3^{k'}\}\cup\{2^0,2^1,\ldots\}$.

Task scheduler

Source

You have a bunch of tasks to be executed on a single thread. Each is of a certain type in $\{1,2,\ldots,n\}$ and each takes exactly one second to finish. Tasks of the same type must be executed at least $k$ seconds apart. How long does it take to finish them all?

The greedy algorithm works naturally: at each second run the type with most remaining tasks that are allowed to be executed. However you don't necessarily need to produce execution order if only the total run time is asked. Can we find out the total idle seconds? It turns out to be simple.

Order the types by task count $a_1\leq a_2\leq \ldots \leq a_n$. There are at least $a_n-1$ chunks of $k-1$ or more seconds between execution of task $n$. Consider
$$
S=\sum_{i < n}\min\left(a_n-1, a_i\right).
$$

These are the tasks that we hope to squeeze in those $(a_n-1)(k-1)$ seconds. Apparently if
$$
S<(a_n-1)(k-1)
$$
then there will be at least $(a_n-1)(k-1)-S$ idle seconds, and not hard to see how to achieve exactly that.

Interestingly, TONCAS -- The Necessary Condition is Also Sufficient! If $S\geq (a_n-1)(k-1)$ then there will be no idle seconds. It could be proved by induction.