MathDB

Generalized Sylvester-Galai

Source: 2022 Taiwan TST Round 3 Mock Exam Problem 2

April 29, 2022

algebraTaiwan

Problem Statement

Let

n,s,t

be three positive integers, and let

A_1,\ldots, A_s, B_1,\ldots, B_t

be non-necessarily distinct subsets of

\{1,2,\ldots,n\}

. For any subset

S

of

\{1,\ldots,n\}

, define

f(S)

to be the number of

i\in\{1,\ldots,s\}

with

S\subseteq A_i

and

g(S)

to be the number of

j\in\{1,\ldots,t\}

with

S\subseteq B_j

. Assume that for any

1\leq x<y\leq n

, we have

f(\{x,y\})=g(\{x,y\})

. Show that if

t<n

, then there exists some

1\leq x\leq n

so that

f(\{x\})\geq g(\{x\})

.
Proposed by usjl

Back to Problems View on AoPS