Determine all non empty sets $C_1, C_2, C_3, \cdots $ such that each one of them has a finite number of elements, all their elements are positive integers, and they satisfy the following property: For any positive integers $n$ and $m$, the number of elements in the set $C_n$ plus the number of elements in the set $C_m$ equals the sum of the elements in the set $C_{m + n}$. Note: We denote $\lvert C_n \lvert$ the number of elements in the set $C_n$, and $S_k$ as the sum of the elements in the set $C_n$ so the problem's condition is that for every $n$ and $m$: \[\lvert C_n \lvert + \lvert C_m \lvert = S_{n + m}\]is satisfied.
Problem
Source: Mexico National Olympiad 2021 Problem 6
Tags: combinatorics, algebra, number theory, Mexico
11.11.2021 01:49
I might post my in contest solution later (busy with coordination ) but like hahaha I think this problem is officially considered Algebra, but my solution kinda uses the fact that the elements are integers? and also a bit of NT and algebra, but it also has this combi flavour is so weird! but I really liked it, this one was my favourite problem tbh
11.11.2021 17:30
Should I determine all such infinite sequences of sets?
11.11.2021 17:48
math90 wrote: Should I determine all such infinite sequences of sets? Yes
12.11.2021 00:16
By looking at the property for $(1,n+1)$ and $(2,n)$, we get $|C_{n+1}|+|C_1|=S_{n+2}=|C_n|+|C_2|\implies |C_{n+1}|-|C_n|=|C_2|-|C_1|$. In other words $|C_n|$ is an arithmetic progression of the form $an+b$. Assuming $a>0$, we get, by substituting $(1,n-1)$ in the problem, that $2b+an=a+b+a(n-1)+b=|C_1|+|C_{n-1}|=S_n\geq 1+2+\cdots+|C_n|=\frac{|C_n|(|C_n|+1)}{2}=\frac{(an+b)(an+b+1)}{2}$, which is a contradiction for large enough $n$. Therefore $a$ must be $0$ or in other words $c=|C_n|$ is constant, and $S_n=2c$ is also constant(at least for $n>1$, and on $C_1$ we can do whatever we want, as long as it has $c$ elements). However, once again, we must have $2c=S_n\geq 1+2+\cdots+|C_n|=\frac{c(c+1)}{2}\implies 2\geq \frac{c+1}{2}\implies c\leq 3$. So let us look at these three cases: i)$c=1$ in this case we have to have $S_n=2$ which trivially implies $C_n=\{2\}\forall n>1$, and $C_1$ is any singleton. ii)$c=2\implies S_n=4$. Once again we only have one possibility, since $4=2+2=1+3$ but the numbers in the set have to be distinct, so $C_n=\{1,3\}\forall n>1$, and $C_1$ is any two element set. iii)$c=3\implies S_n=6$. Once again the only case in which they are distinct is $\{1,2,3\}$ (because it is the equality case in the above arguement). So $C_n=\{1,2,3\}\forall n>1$ and $C_1$ is any $3$ element set.
13.11.2021 00:12
Want a better statement ? here you go:
07.01.2022 00:15
I proposed this problem, and was very happy and grateful that it appeared in the national contest