any docks for expressing answer as $\sum_{i=0}^{49}\binom{100}{i}*(100-2i)$ instead of $50 \cdot \binom{100}{50}$? Couldn't find a way to simplify it in-contest oops

No one is posting the sol so here's the construction. Note that is equivalent to simply consider $|T| \ge 50$. Construction Add $a_i$ distinct elements to $S_1 \cap S_2 \cap \dots \cap S_i$ We want \[ k \mid a_k \binom{100 - k}{0} + a_{k+1} \binom{100 - k}{1} + \dots + a_{100} \binom{100 - k}{100 - k} \]or \[ k \mid a_k \binom{100 - k}{100 - k} + a_{k+1} \binom{100 - k}{100 - (k + 1)} + \dots + a_{100} \binom{100 - k}{0} \]for each $k$. We take $a_i = 2i - 100$ when $i \ge 50$, and set whatever when $i \le 50$. Claim: This works. Proof. For $k \ge 50$, this becomes \[ \sum_{n=k}^{100} (2n - 100) \binom{100-k}{100 - n} = 100 \cdot 2^{100-k} + \sum_{n=k}^{100} (2n - 200) \binom{100-k}{100 - n} = \]\[ 100 \cdot 2^{100-k} - 2 \sum_{n=0}^{100-k} n \binom{100-k}{n} = \]\[ 100 \cdot 2^{100-k} - 2 (100 - k) \sum_{n=0}^{100-k-1} \binom{100-k-1}{n} = \]\[ 100 \cdot 2^{100-k} - 2 (100 - k) 2^{100-k-1} = k \cdot 2^{100-k} \]$\blacksquare$ Claim: This uses $N = 50 \cdot \binom{100}{50}$ elements. Proof. This uses \[ \sum_{i=0}^{50} (100 - 2i) \binom{100}{100-i} = \sum_{i=0}^{50} (100 - 2i) \binom{100}{i} \]which is \[ 50 \cdot \binom{100}{50} + 50 \cdot 2^{100} - 2 \sum_{i=0}^{49} 100 \cdot \binom{99}{i} = 50 \cdot \binom{100}{50}. \]$\blacksquare$

got the construction but couldn’t prove cuz im bad at math oops

twinbrian wrote: any docks for expressing answer as $\sum_{i=0}^{49}\binom{100}{i}*(100-2i)$ instead of $50 \cdot \binom{100}{50}$? Couldn't find a way to simplify it in-contest oops hmm you can induct out $$\sum_{i = 0}^k \binom{100}{i} (100-2i) = (100-k)\binom{100}{k}$$but not sure how much not including this docks.

Lower bound sketch: Let a $k$-simplify operation be one that takes a size $k$ collection of sets, removes $k$ shared elements, and adds $1$ new shared element to each size $k-1$ sub-collection. Show $k$-simplifies always preserve modulo conditions on collections less than or equal to size $k$. Spam $100$-simplify, etc. After all $51$-simplifies are done each size $50$ collection must have distinct intersections. Hence $50\binom{100}{50}$ bound follows.

Let $S_1,\dots,S_{100}$ be finite sets of integers, and suppose their intersection is nonempty. Suppose that for any set \[T\subseteq \{S_1,\dots,S_{100}\},\]the size of the intersection of elements in $T$ is divisible by the size of $T$. Find the least number of elements contained in at least $50$ sets $S_i$. Replace $100$ with $n$. Consider the natural topological sort (Figure 1 here, arrows are in the same direction) for subsets of $\{1,\dots,n\}$ with size at least $\frac{n}{2}$. For any node/set (used interchangeably) $S=\{a_1,\dots,a_k\}$, let $c_S$ be the number of elements $e$ such that \[e\in S_{a_1},\dots,S_{a_k}\]and such that $e$ is not contained in any other $S_i$. For any node $S$, it has a subtree consisting of all sets $S'$ with $S\subseteq S'$. In particular, the divisibility condition in the question is now the following: let $x$ be the sum of $c_{S'}$ for all $S'$ described previously. Then we require $|S|\mid x$. Also, we have $c_{\{1,\dots,n\}}>0$. Now assume there exists $S$ with $|S|>\frac{n}{2}$ such that either $|S|=n$ and $c_S>n$ or $|S|<n$ and $c_S\ge |S|$. Also call the configuration satisfying both (1) divisibility and (2) nonempty intersection a good configuration. Let $S_1,\dots,S_{|S|}$ be the sets formed by subtracting one element from $S$. Claim: Let \[c_S := c_S - |S|\]\[c_{S_i} := c_{S_i} + 1.\]Then the resulting configuration is still good. Proof: This is not very hard to prove, but is very hard to find. Let $S'$ be some subset of $S$, and let $x_{S'}$ be the sum of its subtree. Then we would have \[x_{S'} := x_{S'} - |S| + \binom{|S|-|S'|}{|S|-|S'|-1} = x_{S'} - |S'|\]which is fine. $\square$ Now repeat this argument until it is no longer possible (it clearly terminates, as the size of the largest sized set for which we can run this algorithm must decrease). Then just write $c_S := c_S-|S|$ for all $|S|=\frac{n}{2}$ while we can. At this point, the configuration is unique. We can check that $c_S=2|S|-n<|S|$ works, and is therefore the only good configuration. Some calculations yields an answer of $n\binom{n-1}{n/2-1}$. To prove that the divisibility condition may hold for $|T|<\frac{n}{2}$, just run the following algorithm: Take the largest set $T$ for which the divisibility condition fails. For each set $S\in T$, add the (not already used) integer $e$ to $S$. Eventually this process terminates. We are done. $\blacksquare$

How many MOHS is this problem? I think 30-35 but I’m not exactly sure.

i said 35 first but i'm not great at combo, some people solved very fast (there's really only two ideas, 1 graph and 2 smoothing) and some people (me oops) didn't you can get stuck on PIE and other things for a bit, even like CRT

er .... would it be fine if my construction was just "<def correct construction> works for subsets of greater than 50 sets" "for subsets less than 50 sets, add a sufficient amount of elements because they don't affect the answer"

how many points would a construction and answer give?

you can technically just do an explicit construction; it's still 2|T|-n mod |T| so you can just take like (|T|-1)n or something pobably

I may give a sketch of the proof part: For $I\subset A:=\{1,2,\cdots,100\}$, let $a_{I}$ be the number of elements in $(\cup_{i\in I}S_i)\setminus(\cup_{i\notin I}S_i)$. Then the condition will be: for any $I\subset A$ , $\sum_{I\subset J\subset A} a_J$ is a multiple of $|I|$. And $a_A>0$. Let $b_A=\frac{a_A}{100}$ is an integer. We use induction on $|I|$ to define integers $b_I$ such that:for any $I\subset A$ , $$|I|b_I=a_I+\sum_{I\subset J,|J|=|I|+1}b_J.$$The number of elements that are in at least 50 set is $\sum_{|I|\ge 50} a_I$, use the expression $a_I=|I|b_I-\sum_{I\subset J,|J|=|I|+1}b_J$ , that sum can be reduced to $50\sum_{|I|=50} b_I$. Since all the $b_I\ge 1$, the proof is done.

ok time to actually post this somewhat cursed solution The answer is $50\cdot {100\choose 50}$. Imagine we have "vertices" corresponding to each of the subsets of $\{1,2,3,\dots ,99,100\}$, and a vertex that has size $k$ has $k$ different "states" that it cycles between. At each step, when we introduce a new element and put it in some sets, we "tap" one of our vertices, and all of its subsets (including itself) change color as their intersection as gained an element. When a vertex of size $k$ changes color, it goes to the next color in its cycle of $k$. In this way, the colors track the intersection size modulo $k$. The goal is to find the least taps on vertices of size at least 50 needed to revert the configuration to its original combination of colors. Claim: Tapping a vertex $V$ of size $k$ $k$ times has the same effect on the colors of all of the vertices as tapping each of its $k$ subsets of size $k-1$ one time each. Consider any vertex. If it is not a subset of $V$, the neither operation changes the color of the vertex. Now, suppose it is a subset of $V$, and has $s$ elements. The first operation causes it to change color $k$ times, while the second operation causes it to change color $k-s$ times, since there are $k-s$ ways to remove an element from $V$ to stay a superset of the size $s$ vertex. Since $$k-s\equiv k\pmod{s},$$both operations end up with the same color for this vertex. Thus, the two operations are equivalent, which shows the claim. This claim will be used to "send" taps. In particular, this operation does not change the number of taps nor the configuration of colors, so this can essentially be done for free. First, we will prove the bound of $50\cdot {100\choose 50}$. Note that the size 100 vertex must be tapped at least once by given. Thus, it must be tapped a multiple of 100 times. We can pretend to "send" all of these taps to size 99 vertices, so we can assume each size 99 vertex has at least one tap, so the 99 sets must then fill up to some multiple of 99 taps each. Send these taps again to the 98s, which then will each have at least 98 taps each, and so on until we send taps to size 50 vertices. Since they are now the only vertices with taps, they must all fill to at least 50 taps each, which proves the bound of $50\cdot {100\choose 50}$. The construction is just to do the tap sending "greedily". Tap the 100 vertex 100 times, send down to 99s. Then, tap each 99 98 times to fill them, which sends 2 taps down to each of the 98s. Fill them with 96 taps, which sends 3 taps down to the 97s, and so on. Keep doing this until we fill the 51 sets, which sends down 50 taps to each 50, which solves all of the $\geq 50$ size subsets in $50\cdot {100\choose 50}$ taps. Then, we just greedily tap $\leq 49$ size sets by tapping the largest vertex that is not at its original color (ties broken arbitrarily), which eventually solves the configuration and we don't care about these extra taps.

can't we do this by using linear algebra?ANY SOL ?

Does a correct construction with no proof of minimality get 1-2 points? Also, hilarious bijection to calculate the sum:

Fleshed out the solution to this monster problem in full: https://youtu.be/eguz1OuckH0 Lower bound proof is same as the sketch by gogobao

Define $\overline\cap T$ to be the set of elements in $\cap T$ but not in $\cap(T\cup{S_i})$ for any $S_i\not\in T$. (i.e. the elements which lie in exactly the sets in $T$). The answer is $\sum_{i=50}^{100}\binom{100}{i}(2i-100)=50\times\binom{100}{50}$, which occurs when each set $T$ of size $i\geq50$ has $\overline\cap T=2i-100$. It is easy to check that (by pairing $x$ with $100-x$) that every set $T$ has $|\cap T|$ dividing $|T|$. For smaller sets $|T|<50$, order them in decreasing size and arbitrarily add elements to only the sets in $T$ to make the size of $|\cap T|$ a multiple of $|T|$; this doesn't affect the answer. We define a $T$-move for a set $T$ with $|T|=k$, to be the following: Remove $k$ elements from $\overline\cap T$ Add $1$ element to $\overline\cap T'$ for every subset $T'$ of $T$ with size $k-1$, of which there are $k$. Evidently, for $k>50$, a $T$-move does not affect the number of elements in at least $50$ sets, and decreases the number of sets by $50$ if $k=50$. The $T$-move only affects the size of $\cup U$ if $U\subset T$, so we consider the following cases: If $U=T$, then $|\cap U|$ decreases by $k$, keeping it a multiple of $k$. If $|U|=j<|T|$, then it has $k-j$ supersets of size $k-1$ which are also subsets of $T$. This means that $|\cap U|$ increases by $k-j$ and decreases by $k$, ultimately keeping $|\cap U|$ a multiple of $j$. Now consider a minimal configuration. Perform a $T$-move on the sets $|T|\geq50$ in decreasing order of size, until: If $|T|=100$, apply it until $0<|\overline\cap T|\leq 100$. If $50\leq |T|<100$, apply it until $0\leq|\overline\cap T|<|T|$. After this sequence of $T$-moves, we get another minimal configuration satisfying the above bounds. But in fact, this determines the sizes uniquely, because there are only $|T|$ (consecutive) possible choices for $|\overline\cap T|$, so exactly one makes $|\cap T|$ a multiple of $|T|$. Since the construction at the start works, it exactly gives the minimum possible number of sets, and we are done.

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 \iff v_i = 1$. For example, $f(1\dots1)$ denotes $|\bigcap_1^{100} S_i|$, so we know $f(1 \dots 1) \equiv 0 \pmod{100}$. $f(1\dots10)$ denotes the number of elements in $S_1$ through $S_{99}$ but not $S_{100}$ so we know that $f(1 \dots 1) + f(1 \dots 10) \equiv 0 \pmod{99}$. \dots And so on. So the problem condition means that $f(v)$ translates to the statement \[ P(u): \qquad |u| \text{ divides } \sum_{v \supseteq u} f(v) \]for any $u \neq 0\dots0$, plus one extra condition $f(1\dots1) > 0$. And the objective function is to minimize the quantity \[ A \coloneqq \sum_{|v| \ge 50} f(v). \]So the problem is transformed into an system of equations over ${\mathbb Z}_{\ge 0}$ (it's clear any assignment of values of $f(v)$ can be translated to a sequence $(S_1, \dots, S_{100})$ in the original notation). Note already that: Claim: It suffices to assign $f(v)$ for $|v| \ge 50$. Proof. If we have found a valid assignment of values to $f(v)$ for $|v| \ge 50$, then we can always arbitrarily assign values of $f(v)$ for $|v| < 50$ by downwards induction on $|v|$ to satisfy the divisibility condition (without changing $M$). $\blacksquare$ Thus, for the rest of the solution, we altogether ignore $f(v)$ for $|v| < 50$ and only consider $P(u)$ for $|u| \ge 50$. Construction. Consider the construction \[ f_0(v) = 2 |v| - 100. \]This construction is valid since if $|u| = 100-k$ for $k \le 50$ then \begin{align*} \sum_{v \supseteq u} f_0(v) &= \binom{k}{0} \cdot 100 + \binom{k}{1} \cdot 98 + \binom{k}{2} \cdot 96 + \dots + \binom{k}{k} \cdot (100-2k) \\ &= (100-k) \cdot 2^k = |u| \cdot 2^k \end{align*}is indeed a multiple of $|u|$, hence $P(u)$ is true. In that case, the objective function is \[ A = \sum_{i=50}^{100} \binom{100}{i} (2i-100) = 50\binom{100}{50} \]as needed. Remark: This construction is the ``easy'' half of the problem because it coincides with what you get from a greedy algorithm by downwards induction on $|u|$ (equivalently, induction on $k = 100-|u| \ge 0$). To spell out the first three steps, We know $f(1\dots1)$ is a nonzero multiple of $100$, so it makes sense to guess $f(1\dots1) = 100$. Then we have $f(1\dots10) + 100 \equiv 0 \pmod{99}$, and the smallest multiple of $99$ which is at least $100$ is $198$. So it makes sense to guess $f(1\dots10) = 98$, and similarly guess $f(v) = 98$ whenever $|v| = 99$. Now when we consider, say $v= 1 \dots 100$ with $|v| = 98$, we get \[ f(1\dots100) + \underbrace{f(1\dots101)}_{=98} + \underbrace{f(1\dots110)}_{=98} + \underbrace{f(1\dots111)}_{=100} \equiv 0 \pmod{98}. \]we obtain $f(1\dots100) \equiv 96 \pmod{98}$. That makes $f(1\dots100) = 96$ a reasonable guess. Continuing in this way gives the construction above. Proof of bound. We are going to use a smoothing argument: if we have a general working assignment $f$, we will mold it into $f_0$. We define a push-down on $v$ as the following operation: Pick any $v$ such that $|v| \ge 50$ and $f(v) \ge |v|$. Decrease $f(v)$ by $|v|$. For every $w$ such that $w \subseteq v$ and $|w| = |v| - 1$, increase $f(w)$ by $1$. Claim: Apply a push-down preserves the main divisibility condition. Moreover, it doesn't change $A$ unless $|v| = 50$, where it decreases $A$ by $50$ instead. Proof. The statement $P(u)$ is only affected when $u \subseteq v$: to be precise, one term on the right-hand side of $P(u)$ increases by $|v|$, while $|v|-|u|$ terms decrease by $1$, for a net change of $+|u|$. So $P(u)$ still holds. To see $A$ doesn't change for $|v| > 50$, note $|v|$ terms increase by $1$ while one term decreases by $-|v|$. When $|v| = 50$, only $f(v)$ decreases by $50$. $\blacksquare$ Now, given a valid assignment, we can modify it as follows: First apply pushdowns on $1\dots1$ until $f(1\dots1) = 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$; \dots and so on, until we have $f(v) < 50$ for $|v| = 50$. Hence we get $f(1\dots1) = 100$ and $0 \le f(v) < |v|$ for all $50 \le |v| \le 100$. However, by downwards induction on $|v| = 99, 98, \dots, 50$, we also have \[ f(v) \equiv f_0(v) \pmod{|v|} \implies 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.

Answer: $50\binom{100}{50}$ Construction: For every subset $G\subseteq \{1,2,\dots,100\}$ let $S_G$ denote the the set of elements that belong only to the sets $S_i$ for $i\in G$. We are only concerned with $50\leq |G|$ (and we can always chose the rest to satisfy the problem statement). Choose $S_G$ such that $|S_G|=2|G|-100$. Let $T'$ be the indexes of $T$. Then for any subset $T$ with $50\leq |T|$ we have that the size of the intersection of the sets in $T$ is equal to $$\sum_{T'\subseteq G}(2|G|-100)=\sum_{n=|T'|}^{100}\binom{100-|T'|}{n-|T'|}(2n-100)=|T'|\cdot2^{100-|T'|}$$as desired. The number of elements that are in at least $50$ sets is equal to $$\sum_{50\leq |G|}(2|G|-100)=\sum_{n=50}^{100} \binom{100}{n}(2n-100)=50\binom{100}{50}$$ Bound: For all $100n$ elements in all the sets place $n$ elements in each of the $100$ intersections of $99$ sets. Then notice that the second sentence still remains true and the number of elements does not change. We can then repeat this, for all $99n$ elements in the intersection of some $99$ sets place $n$ elements in each of the $99$ intersections amongst $98$ of these sets and so on. Eventually there will only be elements that lie in at most $50$ sets and for any $50$ sets there intersection must be at least $50$, proving the bound.