MathDB

C1

Part of 2020 Balkan MO Shortlist

Problems(1)

k-tuples sharing entries

Source: Balkan MO SL 2020 C1

9/14/2021
Let s≥2s \geq 2 and n≥k≥2n \geq k \geq 2 be integes, and let AA be a subset of {1,2,...,n}k\{1, 2, . . . , n\}^k of size at least 2sk2nk−22sk^2n^{k-2} such that any two members of AA share some entry. Prove that there are an integer p≤kp \leq k and s+2s+2 members A1,A2,...,As+2A_1, A_2, . . . , A_{s+2} of AA such that AiA_i and AjA_j share the pp-th entry alone, whenever ii and jj are distinct.
Miroslav Marinov, Bulgaria
combinatoricsAZE EGMO TST