Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2024 USAMO Problems/Problem 2"
(→‎Video Solution)
 
Line 1: Line 1:
 
Let <math>S_1, S_2, \ldots, S_{100}</math> be finite sets of integers whose intersection is not empty. For each non-empty <math>T \subseteq\left\{S_1, S_2, \ldots, S_{100}\right\}</math>, the size of the intersection of the sets in <math>T</math> is a multiple of the number of sets in <math>T</math>. What is the least possible number of elements that are in at least 50 sets?
 
Let <math>S_1, S_2, \ldots, S_{100}</math> be finite sets of integers whose intersection is not empty. For each non-empty <math>T \subseteq\left\{S_1, S_2, \ldots, S_{100}\right\}</math>, the size of the intersection of the sets in <math>T</math> is a multiple of the number of sets in <math>T</math>. What is the least possible number of elements that are in at least 50 sets?
 +
 +
==Solution 1==
 +
Let's determine the smallest possible number of elements that appear in at least 50 of the sets.
 +
 +
First, we establish some notation. For any subset <math>T \subseteq \{S_1, S_2, \ldots, S_{100}\}</math>, let <math>\cap T</math> denote the intersection of all sets in <math>T</math>. By the problem statement, <math>|\cap T|</math> is divisible by <math>|T|</math>.
 +
 +
We'll use a binary encoding approach. For each element <math>x</math> in our universe, define its "signature" as a binary string of length 100, where the <math>i</math>-th bit is 1 if <math>x \in S_i</math> and 0 otherwise.
 +
 +
For any signature <math>v</math> with exactly <math>k</math> ones, corresponding elements must appear in exactly <math>k</math> sets. The problem condition requires that for any subset of sets corresponding to positions where 1's appear in some signature <math>u</math>, the number of elements having signature <math>v</math> that contains all 1's from <math>u</math> must be divisible by <math>|u|</math>.
 +
 +
Let's denote by <math>f(v)</math> the number of elements with signature <math>v</math>. The problem condition translates to: for any signature <math>u</math>, <math>|u|</math> divides <math>\sum_{v \supseteq u} f(v)</math>.
 +
 +
Key claim: For any signature <math>u</math> with <math>|u| = 50</math>, we need <math>f(u) \geq 50</math>.
 +
 +
Proof: By the divisibility condition, <math>\sum_{v \supseteq u} f(v)</math> must be divisible by 50. For any <math>v</math> strictly containing <math>u</math>, if we sum over all such <math>u</math> of size 50, each <math>f(v)</math> with <math>|v| > 50</math> gets counted multiple times. To satisfy the divisibility condition for each individual <math>u</math>, we need <math>f(u) \geq 50</math> for each signature <math>u</math> with exactly 50 ones.
 +
 +
Since there are <math>\binom{100}{50}</math> different ways to choose 50 positions for ones in the signature, and each such signature must correspond to at least 50 elements, the minimum number of elements appearing in at least 50 sets is <math>50 \binom{100}{50}</math>.
 +
 +
Therefore, the answer is <math>\boxed{50 \binom{100}{50}}</math>.
 +
 +
~ brandonyee
  
 
==Video Solution==
 
==Video Solution==
 
https://youtu.be/eguz1OuckH0
 
https://youtu.be/eguz1OuckH0

Latest revision as of 16:32, 7 March 2025

Let $S_1, S_2, \ldots, S_{100}$ be finite sets of integers whose intersection is not empty. For each non-empty $T \subseteq\left\{S_1, S_2, \ldots, S_{100}\right\}$, the size of the intersection of the sets in $T$ is a multiple of the number of sets in $T$. What is the least possible number of elements that are in at least 50 sets?

Solution 1

Let's determine the smallest possible number of elements that appear in at least 50 of the sets.

First, we establish some notation. For any subset $T \subseteq \{S_1, S_2, \ldots, S_{100}\}$, let $\cap T$ denote the intersection of all sets in $T$. By the problem statement, $|\cap T|$ is divisible by $|T|$.

We'll use a binary encoding approach. For each element $x$ in our universe, define its "signature" as a binary string of length 100, where the $i$-th bit is 1 if $x \in S_i$ and 0 otherwise.

For any signature $v$ with exactly $k$ ones, corresponding elements must appear in exactly $k$ sets. The problem condition requires that for any subset of sets corresponding to positions where 1's appear in some signature $u$, the number of elements having signature $v$ that contains all 1's from $u$ must be divisible by $|u|$.

Let's denote by $f(v)$ the number of elements with signature $v$. The problem condition translates to: for any signature $u$, $|u|$ divides $\sum_{v \supseteq u} f(v)$.

Key claim: For any signature $u$ with $|u| = 50$, we need $f(u) \geq 50$.

Proof: By the divisibility condition, $\sum_{v \supseteq u} f(v)$ must be divisible by 50. For any $v$ strictly containing $u$, if we sum over all such $u$ of size 50, each $f(v)$ with $|v| > 50$ gets counted multiple times. To satisfy the divisibility condition for each individual $u$, we need $f(u) \geq 50$ for each signature $u$ with exactly 50 ones.

Since there are $\binom{100}{50}$ different ways to choose 50 positions for ones in the signature, and each such signature must correspond to at least 50 elements, the minimum number of elements appearing in at least 50 sets is $50 \binom{100}{50}$.

Therefore, the answer is $\boxed{50 \binom{100}{50}}$.

~ brandonyee

Video Solution

https://youtu.be/eguz1OuckH0

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2024_USAMO_Problems/Problem_2&oldid=244495"