Any solutions ?

Solution

I claim it is $m = n-2$. I propose an induction construction. Assuming we already have such a construction for case $n$, I prove for case $n+2$. Denote the original sets $A_1, A_2, ..., A_m$ and new sets $B_1, B_2, ..., B_{m+2}$. $B_1 = \{n+1\}, B_{2\leq i \leq m+1} = A_{i} \cup \{n+2\}, B_{\color{blue}{m+2 = n}} = \{1, 2, 3, ..., n\}$ It is obvious that the size constraints are satisfied. Furthermore, it is trivial that $B_1$ is not a subset of any of the other sets, and no set is a subset of $B_1$ due to size. No subset is a subset of $B_{m+2}$ since they all include either $n+1$ or $n+2$, and $B_{m+2}$ is not a subset of any other set due to size. It is trivial that none of the sets $B_{2\leq i\leq m+1}$ are subsets of one another from the inductive hypothesis, and we are done with our inductive construction. We simply need our base cases now: 4 has $\{1\}, \{2, 3\}$. 5 has $\{1\}, \{2,3\}, \{2, 4, 5\}$. Now to prove this is maximal: Assume otherwise, then either $m = n-1$ or $m = n$. If $m = n$, then it is obvious that $A_1$ is a subset of $A_m$ (the entire set of numbers), and we are done. If $m = n-1$, then it is clear that $A_2$ contains two elements that are not equal to the element of $A_1$, and that $A_m$ contains all elements other than the element in $A_1$ due to size. Thus, $A_2$ is a subset of $A_m$, leading to a contradiction. Thus, we are done. And for those who are wondering, I have highlighted the statement in blue that causes small cases under 4 to not follow induction.

@2above "contained" refers to subset, not overlapping.

Inconsistent wrote: I claim it is $m = n-2$. I propose an induction construction. Assuming we already have such a construction for case $n$, I prove for case $n+2$. Denote the original sets $A_1, A_2, ..., A_m$ and new sets $B_1, B_2, ..., B_{m+2}$. $B_1 = \{n+1\}, B_{2\leq i \leq m+1} = A_{i} \cup \{n+2\}, B_{\color{blue}{m+2 = n}} = \{1, 2, 3, ..., n\}$ It is obvious that the size constraints are satisfied. Furthermore, it is trivial that $B_1$ is not a subset of any of the other sets, and no set is a subset of $B_1$ due to size. No subset is a subset of $B_{m+2}$ since they all include either $n+1$ or $n+2$, and $B_{m+2}$ is not a subset of any other set due to size. It is trivial that none of the sets $B_{2\leq i\leq m+1}$ are subsets of one another from the inductive hypothesis, and we are done with our inductive construction. We simply need our base cases now: 4 has $\{1\}, \{2, 3\}$. 5 has $\{1\}, \{2,3\}, \{2, 4, 5\}$. Now to prove this is maximal: Assume otherwise, then either $m = n-1$ or $m = n$. If $m = n$, then it is obvious that $A_1$ is a subset of $A_m$ (the entire set of numbers), and we are done. If $m = n-1$, then it is clear that $A_2$ contains two elements that are not equal to the element of $A_1$, and that $A_m$ contains all elements other than the element in $A_1$ due to size. Thus, $A_2$ is a subset of $A_m$, leading to a contradiction. Thus, we are done. And for those who are wondering, I have highlighted the statement in blue that causes small cases under 4 to not follow induction. I proposed this question. Thanks for your solution. I also solved it this way.