MathDB
Maximal Proper Subset Closed under Operations

Source: China Team Selection Test 2016 Day 1 Q3

March 15, 2016
combinatoricsnumber theory

Problem Statement

Let n≥2n \geq 2 be a natural. Define X={(a1,a2,⋯ ,an)∣ak∈{0,1,2,⋯ ,k},k=1,2,⋯ ,n}X = \{ (a_1,a_2,\cdots,a_n) | a_k \in \{0,1,2,\cdots,k\}, k = 1,2,\cdots,n \}. For any two elements s=(s1,s2,⋯ ,sn)∈X,t=(t1,t2,⋯ ,tn)∈Xs = (s_1,s_2,\cdots,s_n) \in X, t = (t_1,t_2,\cdots,t_n) \in X, define s∨t=(max⁡{s1,t1},max⁡{s2,t2},⋯ ,max⁡{sn,tn})s \vee t = (\max \{s_1,t_1\},\max \{s_2,t_2\}, \cdots , \max \{s_n,t_n\} ) s∧t=(min⁡{s1,t1},min⁡{s2,t2,},⋯ ,min⁡{sn,tn})s \wedge t = (\min \{s_1,t_1 \}, \min \{s_2,t_2,\}, \cdots, \min \{s_n,t_n\}) Find the largest possible size of a proper subset AA of XX such that for any s,t∈As,t \in A, one has s∨t∈A,s∧t∈As \vee t \in A, s \wedge t \in A.
Back to ProblemsView on AoPS