uniolympiads Ελληνικά

IMC 1997, Day 1, Problem 6

Suppose that FF is a family of finite subsets of N\mathbb{N} and for any two sets A,B∈FA, B \in F we have A∩B≠∅A \cap B \ne \emptyset.

a) Is it true that there is a finite subset YY of N\mathbb{N} such that for any A,B∈FA, B \in F we have A∩B∩Y≠∅A \cap B \cap Y \ne \emptyset?

b) Is the statement a) true if we suppose in addition that all of the members of FF have the same size?

Justify your answers.

Original from the official PDFSuppose that F is a family of finite subsets of N and for any two sets A, B ∈ F we have A ∩ B 6 = Ø. a) Is it true that there is a finite subset Y of N such that for any A, B ∈ F we have A ∩ B ∩ Y 6 = Ø? b) Is the statement a) true if we suppose in addition that all of the members of F have the same size? Justify your answers.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. a) No. Consider F={A1,B1,…,An,Bn,…}F = \{A_1, B_1, \ldots, A_n, B_n, \ldots\}, where An={1,3,5,…,2n−1,2n}A_n = \{1, 3, 5, \ldots, 2n-1, 2n\}, Bn={2,4,6,…,2n,2n+1}B_n = \{2, 4, 6, \ldots, 2n, 2n+1\}.

b) Yes. We will prove inductively a stronger statement:

Suppose FF, GG are two families of finite subsets of N\mathbb{N} such that: 1) For every A∈FA \in F and B∈GB \in G we have A∩B≠∅A \cap B \ne \emptyset; 2) All the elements of FF have the same size rr, and elements of GG – size ss. (we shall write #(F)=r\#(F) = r, #(G)=s\#(G) = s). Then there is a finite set YY such that A∪B∪Y≠∅A \cup B \cup Y \ne \emptyset for every A∈FA \in F and B∈GB \in G.

The problem b) follows if we take F=GF = G.

Proof of the statement: The statement is obvious for r=s=1r = s = 1. Fix the numbers rr, ss and suppose the statement is proved for all pairs F′F', G′G' with #(F′)<r\#(F') < r, #(G′)<s\#(G') < s. Fix A0∈FA_0 \in F, B0∈GB_0 \in G. For any subset C⊂A0∪B0C \subset A_0 \cup B_0, denote

F(C)={A∈F:A∩(A0∪B0)=C}.F(C) = \{A \in F : A \cap (A_0 \cup B_0) = C\}.
Then F=⋃∅≠C⊂A0∪B0F(C)F = \bigcup\limits_{\emptyset \ne C \subset A_0 \cup B_0} F(C). It is enough to prove that for any pair of non-empty sets C,D⊂A0∪B0C, D \subset A_0 \cup B_0 the families F(C)F(C) and G(D)G(D) satisfy the statement.

Indeed, if we denote by YC,DY_{C,D} the corresponding finite set, then the finite set ⋃C,D⊂A0∪B0YC,D\bigcup\limits_{C,D \subset A_0 \cup B_0} Y_{C,D} will satisfy the statement for FF and GG. The proof for F(C)F(C) and G(D)G(D).

If C∩D≠∅C \cap D \ne \emptyset, it is trivial.

If C∩D=∅C \cap D = \emptyset, then any two sets A∈F(C)A \in F(C), B∈G(D)B \in G(D) must meet outside A0∪B0A_0 \cup B_0. Then if we denote F~(C)={A∖C:A∈F(C)}\tilde F(C) = \{A \setminus C : A \in F(C)\}, G~(D)={B∖D:B∈G(D)}\tilde G(D) = \{B \setminus D : B \in G(D)\}, then F~(C)\tilde F(C) and G~(D)\tilde G(D) satisfy the conditions 1) and 2) above, with #(F~(C))=#(F)−#C<r\#(\tilde F(C)) = \#(F) - \#C < r, #(G~(D))=#(G)−#D<s\#(\tilde G(D)) = \#(G) - \#D < s, and the inductive assumption works.

Transcribed from the official solutions, pages 7–8. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?