IMO ShortList 2002, combinatorics problem 5

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

IMO ShortList 2002, combinatorics problem 5

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: IMO ShortList 2002, combinatorics problem 5

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3647 posts

orl

#1 h Sep 28, 2004, 1:41 PM • 3 Y

Y by Inequality_forever, Adventure10, Mango247

Let $r\geq2$ be a fixed positive integer, and let $F$ be an infinite family of sets, each of size $r$ , no two of which are disjoint. Prove that there exists a set of size $r-1$ that meets each set in $F$ .

Attachments:

This post has been edited 1 time. Last edited by orl, Oct 25, 2004, 12:20 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3647 posts

orl

#2 h Sep 28, 2004, 1:43 PM • 3 Y

Y by Inequality_forever, Adventure10, Mango247

Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

129 posts

dzeta

#3 h Sep 30, 2004, 11:04 AM • 4 Y

Y by Tawan, Inequality_forever, Adventure10, Mango247

Just an idea. Let $A_{1},A_{2},...,A_{n} \in F$ . There is $X \in F$ which is not a subset of $\bigcup_{i=1}^{n}{A_{i}}$ (since $F$ is infinite), so $X'=X-\bigcup_{i=1}^{n}{A_{i}}$ has at most $r-1$ elements and also has noneempty intersection with all $A_{i}$ . So, I've proved that for all finite subfamilies $F' \subset F$ , there is a set with $r-1$ elements which meets all elements in $F'$ .
Can you see a nice way to finish it from this point? I think I found one, but it's quite boring, so I won't post it now.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1 post

#4 h Apr 27, 2005, 6:19 PM • 6 Y

Y by ValidName, Inequality_forever, Adventure10, Sross314, Mango247, Stuffybear

consider the union of all sets in the family, call it X. For any set B with at most r-1 elements, we can find a set in the family, A, outside B (not intersecting with B).

Now, take any set in the family, there is an element ,a1, in that set, that is contained in infinitely many sets in the family. Consider this infinite family, I1. Take a set ,A1, in the family but outside (not containing) a1,now there is an element a2 in A1 that is contained in infinitely many sets in the family I1, lets call it I2. Inductively, outside of the constructed set {a1, a2, ... a(r-1)} there is a set in the family, with an element ar that is in infinitely many sets in the family I(r-1), lets call it Ir, thus we have infinitely many sets(Ir family of sets) each contains a1...ar we reach a contradiction, as sets in the family are all distinct...
I think this does it.. it's a lovely problem indeed..

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

69 posts

Raúl

#5 h Sep 22, 2010, 5:40 PM • 3 Y

Y by Inequality_forever, Adventure10, Mango247

What if we put $F_1=\{r_1, r_2\}, F_2=\{r_2, r_3\}$ and $F_a=\{r_3, r_1\}$ , $a\geq 3$ . It contradicts the problem

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

240 posts

#6 h Oct 26, 2011, 10:53 PM • 4 Y

Y by Tawan, Inequality_forever, Adventure10, Mango247

Raúl wrote:

What if we put $F_1=\{r_1, r_2\}, F_2=\{r_2, r_3\}$ and $F_a=\{r_3, r_1\}$ , $a\geq 3$ . It contradicts the problem

the problem said " let be an infinite family of sets" .....it's a set and cannot have two similar element!!

i think i solved it but i'm not sure..!!
let $k \in F$ so every other element of $F$ has a subset of $k$ as it's intersection with $k$ so because the subset's of $K$ are finite so there are infinitely set of $F$ such that their interesction with $K$ is a subset of $K$ like $A_1$ and $K=A_1 \cup X_1$ ....so we can show them like $\{A_1 \cup X_1 , A_1 \cup Y_1,A_1 \cup Y_2,A_1 \cup Y_3,.... \}$ and $X_1 \cap Y_i = \emptyset$ ...also $\mid A_1\mid \leq r-1$ (because $F$ is a set and it's elements are different!)
if we repeat this steps for $Y_1,Y_2,Y_3,...$ and do this $r+1$ times ...i mean that each of $Y_2,Y_3,Y_4,...$ have intersection with a subset of $Y_1$ (maybe empty!) so infinitely of them have intersection with a subset of $Y_1$ call it $A_2$ that $Y_1= A_2 \cup X_2$ so we show them as : $A_1 \cup A_2 \cup X_2, A_1 \cup A_2 \cup Z_1 ,A_1 \cup A_2 \cup Z_2 ,......$ and so $X_2 \cap Z_i = \emptyset$ and $\mid A_1 \cup A_2 \mid \leq r-1$ now repeat this for $Z_1 , Z_2,Z_3,.....$

then we arrive to $A_1 \cup X_1 , A_1 \cup A_2 \cup X_2 , A_1 \cup A_2 \cup A_3 \cup X_3 ,..., A_1 \cup A_2 \cup....A_{r+1} \cup X_{r+1}$ and we konw that $X_i \cap X_j =\emptyset$
$P= A_1 \cup ...A_{r+1}$ thjat because of the last step and difference between the elements of $F$ so $\mid P \mid \leq r-1$ and if $T \in F , T \cap P=\emptyset \Rightarrow T \cap X_i$ is nonempty and because
1. $x_i$ are disjiont
2. $\mid P \mid \leq r-1 \Rightarrow \mid X_i \mid \geq 1$
so $\mid T \mid \geq r+1$ this is contradiction!!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2326 posts

yugrey

#7 h Oct 20, 2013, 1:56 AM • 8 Y

Y by Tawan, freefrom_i, huricane, ValidName, Inequality_forever, Supercali, IAmTheHazard, Adventure10

Lemma: Say all elements of an infinite family of (finite) sets $F$ intersect an infinite bunch $G$ of distinct $r$ sets (any $f$ in $F$ and any $g$ in $G$ intersect). Then $F$ also intersects an $r-1$ set. This lemma kills the problem because we just take $G=F$ and we are done.

We do this by induction. First we do $r=2$ . Note that there is some element that appears infinitely many times in $G$ , else we have infinitely many disjoint sets in $G$ and all elements of $F$ must intersect all of them and have infinite size, contradiction.

Say it is true for $r=k$ . Now we look at $r=k+1$ . All elements of the infinite family of $F$ intersect each of an infinite family $G$ of $k+1$ sets. Now some element must show up infinitely many times in $G$ by the exact same argument as for the $r=2$ case. Call this element $1$ . Say $H$ is the infinite subfamily of $G$ with $1$ 's, and $I$ is the infinite family of $k$ elements formed by removing the $1$ 's from the sets in $G$ . Now, every member of $F$ that lacks a $1$ must intersect every element of $I$ . Hence, by induction some set of $k-1$ elements meets everything in $F$ without a $1$ . Then take the union of $1$ and this set, and we have a set of $k$ elements that meets everything in $F$ .

The lemma is proved by induction, and the statement follows.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

92 posts

#8 h Jun 20, 2015, 2:17 AM • 4 Y

Y by Tawan, Inequality_forever, Adventure10, Mango247

Let a number $k \le r$ be "good" if, for any $k$ things, only a finite number of the sets of $F$ contain these $k$ things. Clearly $r$ is good since the sets are distinct. Now, assume $k$ is good, and $k \ge 2$ .

Then take any $k-1$ things, and assume an infinite number of sets of $F$ contain these $k-1$ things. Call these sets "good" sets, and let $X$ be the set of the $k-1$ things. Consider one of these good sets, $X \cup \{ t_1, ..., t_{r-k+1} \}$ . By the goodness of $k$ , only finitely many good sets contain one of the $t_i$ . So take one good set without any $t_i$ , say $X \cup \{t_1', ..., t_{r-k+1}'\}$ . By the goodness of $k$ , only finitely many good sets contain one of the $t_i$ or $t_i'$ , so take one good set without any of those. Continue until I have $r+1$ good sets that only share elements in $X$ . Let them be $G_1 \cap X, G_2 \cup X, ..., G_{r+1} \cup X$ .

If every set intersects $X$ , then the problem is proven. Otherwise, there exists a set in $F$ that doesn't intersect $X$ . Then it must intersect $G_1, ..., G_{r+1}$ . But all the $G$ 's are coprime, so this set has cardinality $r+1$ , contradiction!

Thus, $k-1$ is good. By induction, $1$ is good.

Take any set of $r$ things $a_1,...,a_r$ . Finite sets contain $a_i$ for any $i$ , and thus finite sets intersect $\{a_1,...,a_r\}$ . But all sets of $F$ intersect $\{a_1,...,a_r\}$ , contradiction!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1963 posts

ABCDE

#9 h May 26, 2016, 6:42 PM • 3 Y

Y by Inequality_forever, Adventure10, Mango247

For a set $A\in F$ and a subset $B$ of $A$ , let $S(A,B)$ denote the set of sets $T\in F$ with $A\cap T=B$ .

Let $|B|=1$ is a subset of $A\in F$ . If $S(A,B)$ is empty, then we take all elements in $A$ except for the element in $B$ as our set of size $r-1$ and this clearly intersects all sets in $F$ . Hence, we may suppose that $S(A,B)$ is nonempty for all such sets $A$ and $B$ .

Now, we will prove that $S(A,B)$ is finite for all $B\subseteq A\in F$ . We will strong induct on $|B|$ . Clearly, the statement is true for $|B|=r$ , since $S(A,B)=\{A\}$ . Now, suppose that the statement is true for $|B|=k,k+1,\ldots,r$ . We will now prove it for all $|B|=k-1$ . Consider a set $C\in F$ such that $|A\cap C|=1$ and $B\cap C\cap A=\emptyset$ . Such a $C$ exists by the previous paragraph, and let $C'$ be the subset of $C$ consisting of all elements of $C$ except the element it shares with $A$ . Now, suppose that infinitely many sets in $F$ intersect $A$ at $B$ . Let $T$ be the set of those sets. Now, all sets in $T$ intersect $C'$ , so since there are infinitely many of them, some subset $X$ of $C'$ is the set of intersection infinitely many times. Now, take some $D$ such that $D\cap C'=X$ , and note that infinitely many sets intersect $D$ at $B\cup X$ . But since $|B\cup X|=|B|+|X|\geq k$ , we have a contradiction by strong induction.

Since finitely many sets intersect at $A$ at each one of its subsets, there are finitely many sets in $F$ , a contradiction. Hence, the only possibility is the one described in the second paragraph, and we have already found the set of size $r-1$ , so we're done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6862 posts

#10 h Mar 27, 2017, 12:54 AM • 8 Y

Y by tenplusten, Ankoganit, huricane, Inequality_forever, v4913, DanDumitrescu, Adventure10, Mango247

I'll prove the generalized HMMT formulation:

HMMT 2016 Team Round #9 wrote:

Fix positive integers $r>s$ , and let $\mathcal F$ be an infinite family of sets, each of size $r$ , no two of which share fewer than $s$ elements. Prove that there exists a set of size $r-1$ that shares at least $s$ elements with each set in $F$ .

We consider the following algorithm. Initially, let $X = \varnothing$ and $\mathcal G = \mathcal F$ . Then, perform the following:

If there exists $x \notin X$ which lies in infinitely elements of $\mathcal G$ , then add $x$ to $X$ and remove all sets in $\mathcal G$ not containing $x$ .
Otherwise, stop.

The end result is an infinite sub-family $\mathcal G$ , such that each $S \in \mathcal G$ contains every element of $X$ , while $|\mathcal G| = \infty$ still.

We claim that this $X$ works. Evidently, $|X| \le r-1$ .

We can take a subset $G_1$ , \dots, $G_r$ of sets in $\mathcal G$ such that $G_i \cap G_j = X$ for $i \neq j$ , since each element of $G_i \setminus X$ is in finitely many guys. In particular, $|X| \ge s$ .

Crude picture:
$[asy] size(6cm); draw( (0,0)--(3,0)--(3,1)--(0,1)--cycle ); label("$X$", (3,1), dir(45)); dot( (0.5,0.5) ); dot( (1.5,0.5) ); dot( (2.5,0.5) ); dot( (-0.5,1.2), blue ); dot( (-1.2,1.2), blue ); dot( (-0.5,0.6), red ); dot( (-1.2,0.6), red ); dot( (-0.5,-0.2), heavygreen ); dot( (-1.2,-0.2), heavygreen ); [/asy]$
( $G_1$ is blue plus $X$ , et cetera)

Then any $S \in \mathcal F$ must meet each $G_i$ in at least $s$ places. It thus has to meet $X$ in at least $s$ places, since otherwise it would have to meet each $G_i$ in at least one element outside of $X$ , but those are disjoint.

This post has been edited 1 time. Last edited by v_Enhance, Mar 27, 2017, 12:54 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

54 posts

#11 h Oct 18, 2017, 10:54 PM • 3 Y

Y by Inequality_forever, Adventure10, Mango247

Suppose a set $X \in F$ has elements $\{1, 2, \cdots n\}$ . For each other set in $F$ , its intersection with $X$ is a subset of $X$ . Now consider all the subsets of $X$ , there is a finite number of them. There are infinitely many sets in $F$ , so there exists some set $Y \subset X$ with such that the set $S$ containing all sets in $F$ with precisely $Y$ as the intersection with $X$ is infinite.

First suppose the size of $Y$ is less than $n-1$ . If all the subsets in $F$ meet $Y$ , then we are done. Otherwise, take a set $Z$ in $F$ that is disjoint with $Y$ . For each set in $S$ , they must also intersect with $Z$ at another element not in $Y$ . Let $Y_1$ be the set containing $Y$ and this element. Since $|S|$ is infinite, there exists an infinite set $S_1 \in S$ such that all the elements in $S_1$ contain $Y_1$ .

Now do the same thing again to get an infinite set $S_2$ such that all sets in $S_2$ contain $Y_2$ where $|Y_2| > |Y_1|$ . We can continue to do so until we get to some infinite set $S_i$ such that all sets in $S_i$ contain $Y_i$ where $|Y_i| = n-1$ (For the case when $|Y| = n-1$ , we can just jump to this step and let $Y_i = Y$ ).

But now there can't exist another set in $F-S_i$ which doesn't meet $Y_i$ as otherwise an infinite subset of $S_i$ must contain the same $n$ elements and so we're done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3223 posts

#12 h Jun 30, 2019, 2:51 AM • 4 Y

Y by yugrey, Inequality_forever, IAmTheHazard, Adventure10

Here is a solution with StoryScene that only works when $F$ is countable. yugrey says this should be generalizable to all $F$ with transfinite induction, but I'm not knowledgeable enough on the subject to verify this.

Let $F=\{S_1,S_2,\dots\}$ . For any $t$ and any $1\le i\le r$ let $X_i(t)$ be the set of all sets of size $i$ which meet each of $S_1,S_2,\dots, S_t$ . Note that $X_r(t)$ is always infinite, since every element of $F$ lies in it. Let $f(t)$ be the smallest $i$ so that $X_i(t)\neq \emptyset$ . Since $X_i (t+1)\subseteq X_i(t)$ for all $t$ , it's clear that $f(t)$ is nondecreasing, but $f(t)$ only takes values in $\{1,2,\dots, r\}$ , so it eventually becomes some constant $k$ .

Now I claim that if $f(t)=k$ , then $|X_k(t)|$ must be finite. Suppose otherwise, so $X_k(t)$ is infinite. Then there exists some $S\in X_k(t)$ so that $S$ isn't in $S_1\cup S_2\cup \dots \cup S_t$ , so $S$ contains some element $e$ not in any of the $S_i$ for $1\le i\le t$ . Now consider $S' = S\backslash e$ , which has size $k-1$ and meets $S_1,S_2,\dots, S_t$ . This implies $X_{k-1}(t)\neq \emptyset$ , contradiction.

Now since $|X_k(t)|$ is finite but nonzero for all large $t$ and $X_k(t+1)\subseteq X_k(t)$ , it follows $X_k(t)$ eventually becomes constant for $t\ge T$ . Now take any $S\in X_k(T)$ ; it follows that $S$ meets all sets in $F$ , and since $X_r(t)$ is infinite, we have $k\le r-1$ , so $|S|\le r-1$ as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2326 posts

yugrey

#13 h Oct 6, 2019, 5:36 AM • 3 Y

Y by Inequality_forever, Adventure10, Mango247

The transfinite induction that tastymath references is rather straightforward. In any case, there is something else very interesting about this problem.

Amusingly in my research I am reading a paper by mathematician (and IMO 1971 gold medalist) Peter Frankl (https://www.renyi.hu/~pfrankl/2017-4.pdf) that asks what the right bound on $F$ is (it is known that we need $F$ to be bigger than $r^r/2^r$ and it cannot be bigger than $r^r/(1+o(1))^r$ ). My solution in this thread is reminiscent of some of the lemmas in this paper (in particular the ones about $A$ and $G$ ).

This post has been edited 2 times. Last edited by yugrey, Oct 6, 2019, 5:41 AM
Reason: referenced tastymath's post

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2459 posts

#14 h Oct 7, 2019, 2:50 PM • 2 Y

Y by Adventure10, Mango247

orl wrote:

Let $r\geq2$ be a fixed positive integer, and let $F$ be an infinite family of sets, each of size $r$ , no two of which are disjoint. Prove that there exists a set of size $r-1$ that meets each set in $F$ .

We denote the family of sets by $\mathcal{F}$ . Let $X:=\bigcup_{F\in\mathcal{F}}F$ be the underlying set. $X$ is infinite set, since $\mathcal{F}$ is infinite. For some $x_1\in X$ we choose a set $F_1$ of $k-1$ elements such that $\{x_1\}\cup F_1\in \mathcal{F}$ . Then we choose $x_2\in X, x_2\notin \{x_1\}\cup F_1$ and a set $F_2$ with $\{x_2\}\cup F_2\in \mathcal{F}$ .

Proceeding this way, we obtain (disjoint) sets $U_i:=\{x_i\}, i\geq 1$ , and sets of $r-1$ elements $F_i, i\geq 1$ such that $U_i\cup F_i \in \mathcal{F}, i=1,2,\dots$ and $\left(\bigcup_{i} U_i\right) \bigcap \left(\bigcup_i F_i\right)=\emptyset$ .
Consider $X':=\bigcup_i F_i$ . If $X'$ is infinite we run the same process again and obtain mutually disjoint sets (we use the same notations again) $U_i,i\geq 1$ , each one consisting of two elements and sets $F_i,i\ge 1$ , each one of $r-2$ elements, such that $U_i\cup F_i\in\mathcal{F}$ and $\left(\bigcup_{i} U_i\right) \bigcap \left(\bigcup_i F_i\right)=\emptyset$ .

In case $X':=\bigcup_i F_i$ is infinite, we proceed with this process further until we come to a moment we have disjoint sets $U_i,i\in\mathbb{N}$ each with $k,k<n$ elements and sets $F_i$ , each with $r-k$ elements, such that $U_i\cup F_i\in \mathcal{F}$ and $\left(\bigcup_{i} U_i\right) \bigcap \left(\bigcup_i F_i\right)=\emptyset$ and $X':=\bigcup_{i}F_i$ is finite. (Such moment certainly will come, since otherwise we finally get $F_i=\emptyset$ and disjoint set of $U_i$ of $r$ elements, $U_i\in\mathcal{F}$ , which contradicts that any two sets in $\mathcal{F}$ meet.)

Now, $X'$ being finite means there exist finitely many subsets of $X'$ with $r-k$ elements, implying infinitely many sets among $F_i,i\geq 1$ coincide with some $F_0\subset X', |F_0|=r-k$ .
We claim the elements in $F_0$ satisfy the requirement. Indeed, suppose there exists $F\in\mathcal{F}, F\cap F_0=\emptyset$ . But $U_i\cup F_0\in \mathcal{F}$ for infinitely many $i$ , and since $U_i$ are disjoint, some $U_i$ does not meet $F$ , thus $U_i\cup F_0$ does not meet $F$ , contradiction.

Remark. The fact exploited is that the family $\mathcal{F}$ is too large. There is no need $\mathcal{F}$ to be infinite. One can go through and estimate how large should be $|\mathcal{F}|$ , if finite, in order to apply the same arguments.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2459 posts

#15 h Oct 8, 2019, 5:02 PM • 3 Y

Y by tastymath75025, Adventure10, Mango247

tastymath75025 wrote:

Here is a solution with StoryScene that only works when $F$ is countable. yugrey says this should be generalizable to all $F$ with transfinite induction, but I'm not knowledgeable enough on the subject to verify this.

Let $F=\{S_1,S_2,\dots\}$ . For any $t$ and any $1\le i\le r$ let $X_i(t)$ be the set of all sets of size $i$ which meet each of $S_1,S_2,\dots, S_t$ . Note that $X_r(t)$ is always infinite, since every element of $F$ lies in it. Let $f(t)$ be the smallest $i$ so that $X_i(t)\neq \emptyset$ . Since $X_i (t+1)\subseteq X_i(t)$ for all $t$ , it's clear that $f(t)$ is nondecreasing, but $f(t)$ only takes values in $\{1,2,\dots, r\}$ , so it eventually becomes some constant $k$ .

Now I claim that if $f(t)=k$ , then $|X_k(t)|$ must be finite. Suppose otherwise, so $X_k(t)$ is infinite. Then there exists some $S\in X_k(t)$ so that $S$ isn't in $S_1\cup S_2\cup \dots \cup S_t$ , so $S$ contains some element $e$ not in any of the $S_i$ for $1\le i\le t$ . Now consider $S' = S\backslash e$ , which has size $k-1$ and meets $S_1,S_2,\dots, S_t$ . This implies $X_{k-1}(t)\neq \emptyset$ , contradiction.

Now since $|X_k(t)|$ is finite but nonzero for all large $t$ and $X_k(t+1)\subseteq X_k(t)$ , it follows $X_k(t)$ eventually becomes constant for $t\ge T$ . Now take any $S\in X_k(T)$ ; it follows that $S$ meets all sets in $F$ , and since $X_r(t)$ is infinite, we have $k\le r-1$ , so $|S|\le r-1$ as desired.

Nice! No need for transfinite induction in case the family is uncountable. But, if you use it, it usually is made by indexing the sets in $F$ with ordinals, like $\{S_{\alpha}:\alpha <\beta\}$ , where $\beta$ is some ordinal. In case $\beta$ is countable, one can arrange $S_{\alpha},\alpha <\beta$ in a sequence and apply the same argument. But, if $\beta$ is uncountable, for example the first uncountable ordinal $\omega_1$ (when you take the limit, and $\omega_1+1$ ,....etc.), one should use some other argument like the one used below. Not that it is of any difficulty, but it makes the induction pointless.

Suppose $\mathcal{F}$ is uncountable family satisfying the condition. As you proved, for any countable subfamily $F\subset \mathcal{F}, F=\{S_1,S_2,\dots\}$ , there exists a finite collection $X_k(T),k\leq r-1$ of sets with $k$ elements (eventually depending on $F$ ), as described in post N12. We simply denote $X_k(T)$ as $X_k$ or rather $X_k(F)$ (to mark it may depend on $F$ ).
Let $\ell$ me the maximal possible $k$ in $X_k(F)$ when $F$ varies. Note that for any two countable subfamilies $F_1,F_2\subset \mathcal{F}$ with $X_{\ell}(F_1)$ and $X_{\ell}(F_2)$ , $X_{\ell}(F_1)\cap X_{\ell}(F_2)\neq \emptyset$ . Indeed, $F_1\cup F_2$ is also countable, and arranging those sets in a row it easily follows $X_{\ell}(F_1\cup F_2)=X_{\ell}(F_1)\cap X_{\ell}(F_2)$ .

So, we take minimal $X_{\ell}(F)$ when $F$ varies (but providing in $X_k(F)$ we have $k=\ell$ ). Denote it with $X(F_0)$ . I claim, all sets in $X(F_0)$ (which consist of exactly $\ell<r$ elements) do the job. Indeed let $S_0\in X(F_0)$ . Take any set $S\in\mathcal{F}$ . We may consider $F:=\{S\}\cup F_0$ . Since $X_\ell(F)\subset X_{\ell}(F_0)$ and $X_{\ell}(F_0)$ is the minimal one, we get $X_\ell(F)=X_\ell(F_0)$ or $S\cap S_0\neq \emptyset$ . $\blacksquare$

Remark. The idea in post #12 may be applied in slightly different way, working only with finite sets. For any collection $F$ of finite sets $S_1,S_2,\dots,S_n$ , let $X(F)$ denotes the collection of all sets of size at most $r-1$ that meet any set in $F$ , and there aren't two sets in $X(F)$ one is the subset of the other. In the same way, as you proved it in #12, there exist finite collection $F$ with $X(F)$ of finite size. So, you take a minimal $X(F)$ , under inclusion, and further apply the same method as above.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2326 posts

yugrey

#16 h Nov 18, 2020, 12:04 AM

Y by

See https://arxiv.org/abs/2010.02541 for new bounds on this problem.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

308 posts

#17 h Apr 10, 2021, 12:38 PM

Y by

Suppose on the contrary that such set does not exist.

Claim. For each $1\leq n\leq r-1$ there exists some $\{a_1,...,a_n\}$ which is contained in an infinite number of sets in $F$ .
Proof. Induct on $n$ . For $n=1$ , suppose $S_0\in F$ . Then every $S$ in $F$ intersect $S_0$ , hence by pigeonhole principle, there exists infinitely many sets intersecting the same element in $S_0$ , so we are done.

Now for the general case $n$ we can find some $\{a_1,...,a_{n-1}\}$ contained in an infinite number of sets $S_1,S_2,...$ in $F$ . If this set intersects every other set in $F$ then we are done. Otherwise consider a set $S_0$ not intersecting it. Then each of the $S_1,S_2,...$ intersect $S_0$ . By pigeonhole principle an infinite number of them intersect at the same element $a_n$ , hence taking $\{a_1,...,a_n\}$ we are done. $\blacksquare$

Now we can take $T=\{a_1,...,a_{r-1}\}$ satisfying the condition in the Claim, being contained in sets $S_1=T\cap \{b_1\},S_2=T\cap\{b_2\} ,...$ , where the $b's$ are all distinct. Suppose on the contrary that some set $S_0$ in $F$ do not intersect $\{a_1,...,a_{r-1}\}$ . Then it must contain all $b_1,b_2,...$ , contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

222 posts

#18 h May 10, 2021, 11:16 AM • 2 Y

Y by L567, starchan

FTSOC, assume problem statement is false.

Let $S$ be the set of largest size which is a subset of infinitely many elements of $F$ . If there are many such $S$ , then pick any of them. Now, we claim $|S|=r-1$ .
Proof: Assume not, clearly $|S|<r$ . Now, we can find $f\in F$ such that $f\cap S=\Phi$ (else, problem statement follows). Thus, there must be some element $t\in f$ , such that $t$ is in infinitely many of the sets that contain $S$ . Thus, $S\cup \{t\}$ would be a larger set satisfying problem conditions.

Thus, we have found an $r-1$ set which is a subset of infinitely many sets in $F$ . But, observe that we should still be able to apply the above algorithm if problem statement is false. But, we cannot have $|S|=r$ . Thus, we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1665 posts

awesomeming327.

#19 h Jun 10, 2023, 12:12 AM

Y by

Clearly, there must exist at least one element $x$ that appears in infinitely many sets $F$ . Otherwise, consider any $S\in F$ . For each $x\in S$ , finitely many sets $T\in F$ have the property that $x\in T$ . However, this means that only finitely many sets $T\in F$ can meet $S$ , so infinitely many sets are disjoint from it, contradiction.

Now, let $U$ be the maximal set, selected from a greedy algorithm, such that $U$ is a subset of infinitely many $S\in F$ . Clearly, $|U|\le r-1$ . Let $F_0$ be the maximal subfamily of $F$ such that $U\subset S$ for all $S\in F_0$ . Since $U$ is maximal, for any $V_1,V_2,\dots, V_n\in F_0$ , there is infinitely many $W\in F_0$ such that $V_i$ and $W$ only intersect at $U$ for all $i$ . Otherwise, there is infinitely many $W\in F_0$ such that $V_i\setminus U$ and $W\setminus U$ aren't disjoint for some $I$ . Since the union of $V_i$ is finite, though, there must exist a particular element that appears in infinitely many $W\in F_0$ , contradiction.

Thus, let $V_1,V_2,\dots,V_{r+1}$ all be mutually disjoint except at $U$ . For all $S\in F$ , $S$ and $V_i$ are not disjoint for all $i$ . If $S$ is disjoint from $U$ , then it must reach one element from each $V_i\setminus U$ , but that's $r+1$ distinct elements, absurd.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a