MathDB
single representation problem

Source: 2007 Indonesia TST stage 2 test 2 p4

December 14, 2020
combinatoricsrepresentationset theorySubsets

Problem Statement

Given a collection of sets X={A1,A2,...,An}X = \{A_1, A_2, ..., A_n\}. A set {a1,a2,...,an}\{a_1, a_2, ..., a_n\} is called a single representation of XX if aiAia_i \in A_i for all i. Let S=mn|S| = mn, S=A1A2...An=B1B2...BnS = A_1\cup A_2 \cup ... \cup A_n = B_1 \cup B_2 \cup ... \cup B_n with Ai=Bi=m|A_i| = |B_i| = m for all ii. Prove that S=C1C2...CnS = C_1 \cup C_2 \cup ... \cup C_n where for every i,Cii, C_i is a single represenation for {Aj}j=1n\{A_j\}_{j=1}^n and {Bj}j=1n\{B_j\}_{j=1}^n.