Let $n \geq 2$ be a natural. Define $$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 = (s_1,s_2,\cdots,s_n) \in X, t = (t_1,t_2,\cdots,t_n) \in X$, define $$s \vee t = (\max \{s_1,t_1\},\max \{s_2,t_2\}, \cdots , \max \{s_n,t_n\} )$$$$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 $A$ of $X$ such that for any $s,t \in A$, one has $s \vee t \in A, s \wedge t \in A$.
Problem
Source: China Team Selection Test 2016 Day 1 Q3
Tags: combinatorics, number theory
15.03.2016 15:40
The answer is $(n+1)!-(n-1)!$ for all $n>1$,for $n=1$ the answer is $1$.Example for $n>1$ are all elements expect those who have $a_n=n$ and $a_(n-1)=0$.I will call the first operation $($ and second $)$.Now define an ordering of elements where $s>t$ iff $s_i>=t_i$ for all $i$ from $1$ to $n$.Lemma 1:The minimal element of $X/A$ has at least $n-1$ $a_i$ that are equal $0$. Proof:Suppose opposite.Let $a_q>0$ and $a_w>0$ for the minimal element $a$.Let $s$ be such $s_i$ be equal $a_i$ for all $i$ expect $q$ and let $s_q$ be equal $0$.Let $t$ be such that $t_i$ equals $a_i$ for all $i$ expect $w$ and let $t_w$ equals $0$.Then $s(t$ equals $a$,which is a contradiction. Lemma 2:Let $T$ be a proper subset of $X$ not containg $s=(0,0,...0)$.Then there exist an index $j$ such that for any element $q$ from $T$ $q_j$ isn't equal to $0$. Proof:Suppose opposite and let $m$ be the element with the maximum number of zeroes.Let $m_j$ not be equal $0$(it exists by assumption).There exists an element $w$ such that $w_j$ equals $0$.Now,$m)w$ has more zeroes than $m$,which is a contradiction. Now,let $a$ be the minimal element not in $A$.Case 1:$a=(0,0...0)$.Then,by Lemma $2$ we easily conclude that A has at most $n*n!$ elements. Case $2$:There exist $a_i>0$.Consider all elements $s$ such that $s_i=a_i$.By applying Lemma $2$,$A$ has at most $(n+1)!*(1-1/i*j)$,where $i$ and $j$ are distinct integers less than or equal $n+1$.
19.03.2016 06:34
Answer: $(n + 1)! - (n - 1)!$ Consider some $A$ with $|A| > (n + 1)! - (n - 1)!.$ Call $a = (a_1, a_2, \cdots, a_n) \in X$ interesting if $a_k \ne 0$ for at most one $k.$ Let $\mathbf{x}_k$ be the interesting element of $X$ whose $k$th entry equals $k.$ We refer to the $\mathbf{x}_i$s as elementary. Note that if $A$ contains all interesting elements of $X$, then $A$ contains all elements of $X$, because an arbitrary element $(a_1, a_2, \cdots, a_n) \in X$ can written as \begin{align*} (a_1, 0, \cdots, 0) \vee (0, a_2, 0, \cdots, 0) \vee \cdots \vee (0, \cdots, 0, a_n), \end{align*}where the operations are performed in any order. We will in fact prove the stronger statement that if $A$ contains all elementary elements of $X$, then $A$ contains all elements of $X.$ We need the following preliminary result. Lemma: Fix some $0 \le j \le n.$ Then for each $k \ge \max\{1, j\}$, there is an element $a = (a_1, a_2, \cdots, a_n) \in A$ with $a_k = j.$ Proof: Suppose that $A$ does not contain such an element. Then there are at most $k$ choices for the $k$th entry of an element of $A.$ Hence, \begin{align*} |A| \le (n + 1)!\left(\frac{k}{k + 1}\right) \le (n + 1)!\left(\frac{n}{n + 1}\right) = (n + 1)! - n!, \end{align*}which contradicts our assumption on $|A|.$ $\blacksquare$ Now, suppose that $A$ contains all elementary elements of $X.$ We will show that $A$ contains all interesting elements of $X$ (and consequently all elements of $X$). Take some interesting $a = (a_1, a_2, \cdots, a_n) \in X$ with possibly $a_k \ne 0.$ By the lemma, there exists some $b = (b_1, b_2, \cdots, b_n) \in A$ with $b_k = a_k.$ It follows that $a = b \vee \mathbf{x}_k \in A$, as desired. Therefore, as $A$ is a proper subset of $X$, it follows that $A$ cannot contain all elementary elements. So suppose that $\mathbf{x}_k \not\in A$ for some $0 \le k \le n.$ We will find $(n - 1)!$ elements of $X$ that do not belong to $A$, thus contradicting our assumption on $|A|.$ Denote $B = \{a = (a_1, a_2, \cdots, a_n) \in A : a_k = k\}.$ Since $\mathbf{x}_k \not\in B$, it follows that for some $j \ne k$, we have $a_j \neq 0$ for all $a \in B.$ This is because if there were an element with $a_j = 0$ for each $j$, we could repeatedly apply the $\vee$ operation on said elements to obtain $\mathbf{x}_k$, impossible. Hence, there are at most $j$ choices for the $j$th entry of an element in $B.$ It follows that for any $a = (a_1, a_2, \cdots, a_n) \in X$ with $a_k = k$ and $a_j = 0$, we have $a \not\in B$ and therefore $a \not\in A.$ But there are evidently \begin{align*} \frac{(n + 1)!}{(j + 1)(k + 1)} \ge \frac{(n + 1)!}{n(n + 1)} = (n - 1)! \end{align*}elements $a$ of this form. Thus, we have found $(n - 1)!$ elements of $X$ that do not belong to $A$, as needed. It remains to provide an equality case. Inspired by the above reasoning, we let $A$ contain all elements of $X$ except those of the form $(a_1, a_2, \cdots, a_n)$ with $a_n = n$ and $a_{n - 1} = 0.$ It is easy to check that this construction works, because no element of $X$ whose final two entries are $0, n$ can be obtained by applying the $\vee$ or $\wedge$ operation to two elements of $A.$ This completes the proof. $\square$
26.02.2020 10:38
Nice problem. I claim the answer is $(n+1)!-(n-1)!$. For the construction: All $(n+1)!$ combinations except those which end with $n$ and have second last $0$ ($(n-1)!$). Proof: Consider the subset $A$. Let $S_0,S_1,\cdots , S_n$ be the sets of strings ending with $0,1,\cdots , n$ respectively. We will prove it by induction. Let $X_n$ be the set of all the possible strings (we use a general $X_n$ instead of $X$) If not all the elements of the $x_{n-1}$ have appeared atleast once in atleast one of the $s_i$, there can be atmost $(n+1)\times (n!-(n-2)!)<$ the claimed answer. (the value is according to induction). So, we each the elements of $X_{n-1}$ must appear atleast once in atleast one of the $S_i$. Now, we prove the following claims: 1. $(1,2,\cdots, n) \in S_n$ Proof: It must be in atleast one of the $s_i$'s. But, if it is in a lower $S_i$, it must also be in the topmost since $S_i \wedge S_n$. 2. $S_i$ are set of ranges, i.e., If $x,y\in S_i$, and $x<a<y$ (the relation operator works s.t. every element must follow that relation). Proof: We will use the fact that every element of $X_{n-1}$ has been used. $a$ must be atleast in one of the upper set, say $S_A$ ($S_k$ where $k<i$) or lower set($S_k$ where $k\geq i$), say $S_B$. $x\wedge S_A \in S_i$, $x\vee S_B \in S_i$. $y\wedge S_A \in S_i$, $y \vee S_B \in S_i$. We can take one of them $S_A/S_B$ to be $a$ and get the desired result that $a \in S_i$. 3. If $x$ (a $n-1$ size string) is in $S_i$ and $S_j$ ($i<j$), then: $x\in S_i, S_{i+1},\cdots, S_j$. Proof: $x\vee S_k$ and $x\wedge S_k$ must be in $S_k$ (for $i<k<j$), and since $S_i$ are ranges, the statement is true. Atleast one of the $S_0,S_n$ is not full as otherwise all must be full (by claim 3). WLOG assume $S_n$ to be non-full. We have $S_n$ as a union of some ranges. $S_n \vee S_n \in S_n$ implies that it cannot have more than 1 lower bound to its ranges. The bottom element of the range must be one of the bottom-most element in the DAG with an edge from $s$ to $t$ if $t$ differs from $s$ by one and $t>s$. The bottom-most element of the tree is $0,0,\cdots ,0$. So, this lower bound must have atmost one '1'. For the maximum number of elements in $S_n$, it is clearly at the end. For the maximum, the $S_0,S_1, \cdots , S_{n-1}$ must be full, giving the desired maximum.
02.10.2020 18:50
The answer is $(n+1)!-(n-1)!$. For construction, take all elements of $X$ that do not satisfy ``$a_n=n$ and $a_{n-1}=0$.'' Call any $n+1$-tuple in $X$ almost zero if all but one of its components are zero. It is not hard to see that any $A$ containing every almost zero tuple is $X$. So consider some $A$ satisfying the conditions of the problem that is not $X$, then it does not contain some almost zero $(0,\dots,0,x_i,0,\dots,0)$. Let $B$ denote the set of elements of $A$ such that the $i$-th component is at least $x_i$, and $\textbf{B}$ denote the set of elements of $X$ such that the $i$-th component is at least $x_i$. Take $\bigvee B$ and observe that either The $i$-th component of any element of $B$ is at least $x_i+1$, so $|B| \le |\textbf{B}| - \frac{1}{i+1-x_i}|\textbf{B}| = \frac{i-x_i}{i+1-x_i}|\textbf{B}|$, For some $j\ne i$, the $j$-th component of any element of $B$ is at least $1$, so $|B| \le \frac{j}{j+1}|\textbf{B}|$. Now, note that $|\textbf{B}| = \frac{i+1-x_i}{i+1}(n+1)!$. It is not hard to see that $|B| \le \frac{n}{n+1}|\textbf{B}|$. If $|\textbf{B}|\ge \frac{1}{n}|X|$, we are done. Otherwise, the almost zero term that $X$ does not contain must be $(0,\dots,0,n)$, so we get $|\textbf{B}|-|B| \ge \frac{1}{n(n+1)}|X|$ anyway because of the restriction $j\ne i$.
30.04.2021 07:27
The answer is $(n+1)!-(n-1)!$, with $A$ not containing an $n$-tuple iff $a_{n-1}=0, a_n=n$. USOMO 2020/5 vibes. First of all, there must be one $n$-tuple with one nonzero element not in $A$. Otherwise, any element in $S$ can be formed. Suppose this $n$-tuple has $a_k=C\ne 0$. Call this element root. Let $B=\{1,\cdots,n\} \backslash \{k\}$ Call a subset $S\subseteq B$ obliterated, if for all $(x_1,\cdots,x_n)$ where $x_k=C, x_t=0\forall t\in S$ and $x_t>0\forall t\in B\backslash S$ Observe the set of unobliterated subsets all have a + in one location, for otherwise the root would be in $A$ by the operation. Call this location $l$. (1) Let $g(T)=\prod\limits_{i\in T}i$. Notice each obliterated $T$ corresponds to $g(T)$ elements NOT in A. Note $\sum\limits_{S\in B} g(S) = \sum\limits_{S\in B} \prod\limits_{i\in S} i = \prod\limits_{i\in B} (1+i) = \frac{(n+1)!}{1+k}$ Furthermore, by (1), $\sum\limits_{S \text{ obliterated}} \left(\prod\limits_{i\in T} i \right) \ge \frac{1}{l+1} \sum\limits_{S\in B} g(S) \ge \frac{(n+1)!}{(k+1)(l+1)} \ge (n-1)!$, as desired.
03.10.2022 14:44
I believe this is a new solution,but can someone verify. We claim the answer is $(n+1)!-(n-1)!$.For the construction,take all tuples not satisfying $a_n=n$ and $a_{n-1}=0$. Call a subset $A$ of $X$ ,nice if it has the property that for any two indices $i,j \le n$,and any two numbers $a_i,a_j$,both in range ,we have a $n$ tuple belonging to $A$,that contains $a_i,a_j$ at the $i,j$ th position respectively.We claim that any nice subset $A=X$.We prove it by induction on $n$.It is true by definition for $n=2$.Now ,suppose ,we have a nice subset of $n$ tuples.Consider the set of distinct tuples,formed by ignoring the n'th component of the tuples.These have to consist of all the $(n-1)$ tuples by induction hypothesis. Note that $(0,0...k)$ belongs to $A$,for any $k$.This can be seen easily by firstly taking two n-tuples,one containing $0,k$ at the $(n-1),n$ th positions .The other tuple containing ,$0,k$ at the $(n-2),n$ th position .If these are not the same ,the the second operation,yields a tuple containing 0s at the n-1,n-2 th position and $k$ at the n th position.Doing this repeatedly,we get the desired tuple in $A$. Note that $(1,2,...n-1,0)$ belongs to $A$ by repeatedly performing the first operation ,starting out with the strings that contain $n-1,0$ at the $n-1,n$ th postions and the other tuple with $n-2,0$ at the $n-2,n$ th postions. From the inductive hypothesis ,we have that $(M,a)$ belongs to $A$ for some $a$and $M$ is an arbitrary $n-1$ tuple .Now that $M,0$ belongs to $A$,by performing the second operation with $(M,a)$ and $(1,2,...n-1,0)$,we get $(M,0)$ belongs to $A$.Now we get that $(M,k)$ belongs to $A$,for any $k \le n$,by performing the first operation with $(M,0)$ and $(0,0...k)$. So we get that $A$ is not nice ,which means that $A$ excludes at least $\frac{(n+1)!}{(i+1)(j+1)} \ge (n-1)!$ tuples.
07.10.2022 06:52
No one seems to mention the solution that I came up with, so here's a sketch. We claim $|A|\leq (n+1)!-(n-1)!$. In other word, if $|A|>(n+1)!-(n-1)!$, then $A$ would have to be $X$. We induct to $n$. The case $n=2$ is trivial. Now assume the claims is true for $n-1 (n\geq 3)$, we check the $n$ case. Partition $A$ into $\cup_{i=0}^{n}A_i$, where $A_i=\{(a_1,\dots,a_n)\in A | a_n=i\}$. If $|A_i|\leq n!-(n-2)!$ for all $0\leq i\leq n$, then $|A|\leq(n+1)(n!-(n-2)!)<(n+1)!-(n-1)!$. Otherwise we may assume that for some index $l$, $|A_l|>n!-(n-2)!$, thus $A_l$ must be $\{(a_1,\dots,a_n)\in X|a_n=l\}$. We call a subset $T$ of $X$ “closed downward”, if it is of the form $\{(a_1,\dots a_n)\in X|a_i\leq c_i, 1\leq i\leq n\}$ for some fixed $c_i$. Define “closed upward” subsets analogously. It is not hard to check that for $i<l$, $A_i$ is closed downward, and for $i>l$, $A_i$ is closed upward. Because $A\neq X$, we know that there exist an index $j\neq l$, $A_j\neq X_j$, where $X_j=\{(a_1,\dots,a_n)\in X|a_n=j\}$.From here it is super easy to check that this particular $A_j$ will lose at least $(n-1)!$ elements, thus finishing the inductive step.
31.12.2024 08:36
same sol as @above and i think its pretty natural -- did it all in my head somehow. We claim the answer is $(n+1)! - (n-1)!$. Construction Take all elements of $X$ except those with $n-1$th element $0$ and $n$th element $n$. Then $s \lor t$ must be in $A$ unless they both have $n$th element $n$, which implies that they both have $n-1$th element at least $1$. Simlarly, $s \land t$ is in $A$ unless some element has $n$th element $k$, which implies the same result. Bound Suppose this holds inductively for $n$. Parition $A$ into subsets $A_0 \sqcup A_1 \sqcup \dots \sqcup A_{n+1}$ based off the $n$th element of $a \in A$. Note that \[ (n+2) \cdot ((n+1)! - (n-1)!) < (n+2)! - n! \]so if all $A_i$ have size at most $(n+1)! - (n-1)!$ then $A_i < (n+2)! - n!$ as desired. Else, suppose that $|A_t| > (n+1)! - (n-1)!$ which implies $A_t$ consists of all elements in $X$ with last element $t$ for some $t$. Define a tuple $a \ge b$ if all elements in $a$ are pairwise larger than $b$. Claim: Any subset $S \subset X$ has a minimal and maximal element $m, M$ such that $m \le x, M \ge x$ for all $x \in S$. Proof. Take $m$ as the $\land$ over all elements in $S$, take $M$ as the $\lor$. $\blacksquare$ As such, let $m_i, M_i$ be the minimum and maximum tuples. Then for $i > k$, by considering $a \land (m_i, i)$ for $a \in A_t$, it follows that $A_i$ consists of tuples $(\mathbf{a}, i)$ where $\mathbf{a} \ge m$. Similarly, for $i \le k$, $A_i$ consists of the tuples $(\mathbf{a}, i)$ with $\mathbf{a} \le M$. Suppose $m$ is not all $0$s. Then if $m$ is nonzero in its $t$th component, then $A_i$ has size at most $(n+1)! - \frac{(n+1)!}{t} \le (n+1)! - n!$. The same holds similarly with $M$. Since some $A_i$ has size at most $(n+1)! - n!$, it follows that \[ |A_0| + |A_1| + |A_2| + \dots + |A_{n+1}| \le (n+1)(n+1)! + ((n+1)! - n!) = (n+2)! - n! \]as desired.