Problem 862

The answer is $50\binom{100}{50}$.
ף Rephrasing (cosmetic translation only, nothing happens yet). We encode with binary strings $v \in \mathbb{F}_{2}^{100}$ of length 100 . Write $v \subseteq w$ if $w$ has 1 's in every component $v$ does, and let $|v|$ denote the number of 1 's in $v$.

Then for each $v$, we let $f(v)$ denote the number of elements $x \in \bigcup S_{i}$ such that $x \in S_{i} \Longleftrightarrow v_{i}=1$. For example,
- $f(1 \ldots 1)$ denotes $\left|\bigcap_{1}^{100} S_{i}\right|$, so we know $f(1 \ldots 1) \equiv 0(\bmod 100)$.
- $f(1 \ldots 10)$ denotes the number of elements in $S_{1}$ through $S_{99}$ but not $S_{100}$ so we know that $f(1 \ldots 1)+f(1 \ldots 10) \equiv 0(\bmod 99)$.
- ...And so on.

So the problem condition means that $f(v)$ translates to the statement
$$P(u): \quad|u| \text { divides } \sum_{v \supseteq u} f(v)$$
for any $u \neq 0 \ldots 0$, plus one extra condition $f(1 \ldots 1)>0$. And the objective function is to minimize the quantity
$$A:=\sum_{|v| \geq 50} f(v) .$$

So the problem is transformed into an system of equations over $\mathbb{Z}_{\geq 0}$ (it's clear any assignment of values of $f(v)$ can be translated to a sequence ( $S_{1}, \ldots, S_{100}$ ) in the original notation). $\square$
Note already that:

Proof. If we have found a valid assignment of values to $f(v)$ for $|v| \geq 50$, then we can always arbitrarily assign values of $f(v)$ for $|v|50$, note $|v|$ terms increase by 1 while one term decreases by $-|v|$. When $|v|=50$, only $f(v)$ decreases by 50 .
Now, given a valid assignment, we can modify it as follows:
- First apply pushdowns on $1 \ldots 1$ until $f(1 \ldots 1)=100$;
- Then we may apply pushdowns on each $v$ with $|v|=99$ until $f(v)<99$;
- Then we may apply pushdowns on each $v$ with $|v|=98$ until $f(v)<98$;
- . . . and so on, until we have $f(v)<50$ for $|v|=50$.

Hence we get $f(1 \ldots 1)=100$ and $0 \leq f(v)<|v|$ for all $50 \leq|v| \leq 100$. However, by downwards induction on $|v|=99,98, \ldots, 50$, we also have
$$f(v) \equiv f_{0}(v) \quad(\bmod |v|) \Longrightarrow f(v)=f_{0}(v)$$
since $f_{0}(v)$ and $f(v)$ are both strictly less than $|v|$. So in fact $f=f_{0}$, and we're done.
Remark. The fact that push-downs actually don't change $A$ shows that the equality case we described is far from unique: in fact, we could have made nearly arbitrary sub-optimal decisions during the greedy algorithm and still ended up with an equality case. For concrete example, the construction
$$f(v)=\left\{\begin{array}{ll} 500 & |v|=100 \\ 94 & |v|=99 \\ 100-2|v| & 50 \leq|v| \leq 98 \end{array}\right.$$
works fine as well (where we arbitrarily chose 500 at the start, then used the greedy algorithm thereafter)