MathDB

Problem involving sets, as always

Source: Iranian TST 2021, second exam day 2, problem 3

May 22, 2021

set theorycombinatoricsgraph theoryColoring

Problem Statement

Prove that we can color every subset with

n

element of a set with

3n

elements with

8

colors . In such a way that there are no

3

subsets

A,B,C

with the same color where :

|A \cap B| \le 1,|A \cap C| \le 1,|B \cap C| \le 1

Proposed by Morteza Saghafian and Amir Jafari