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
jampm
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
math90
11.11.2021 17:30
Should I determine all such infinite sequences of sets?
plagueis
11.11.2021 17:48
math90 wrote: Should I determine all such infinite sequences of sets? Yes
cadaeibf
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.
jampm
13.11.2021 00:12
Want a better statement ? here you go:
Let $\mathbb{S}$ be the set of all finite subsets of $\mathbb{N}$. Find all functions $f: \mathbb{N} \mapsto \mathbb{S}$ such that:
\[\lvert f(n) \lvert \ \ + \ \ \lvert f(m) \lvert \ \ = \sum_{k \in f(m + n)} k\]for every $m,n \in \mathbb{N}$.
Note that the empty set yields a new solution but kinda doesn't really matter. Also, I think the original proposal resembled more what Im posting now than what appeared in the actual contest.
Justpassingby
07.01.2022 00:15
I proposed this problem, and was very happy and grateful that it appeared in the national contest
Let $k$ be the minimal element of $\{|C_1|,|C_2|,\dots\}$ and let $C_j$ be a set which achieves this size. Then we must have $$2k=|C_j|+|C_j|=S_{2j}=|C_1|+|C_{2j-1}|\ge k+k$$and all equalities must hold, so $|C_1|=k$. Since $|C_2|\ge k$, we must have $S_2\ge 1+2+\dots+k=\frac{k(k+1)}{2}$. $$2k=|C_1|+|C_1|=S_2\ge \frac{k(k+1)}{2}\Rightarrow 4\ge k+1\Rightarrow 3\ge k.$$
Let $$A_1=\{2\}, A_2=\{1,3\}, A_3=\{1,2,3\}$$and note that $|A_i|=i$.
Lemma: If $S_i=2k$, then $C_i=A_k$.
Proof: If $k=1$, then $C_i$ cannot have more than one element, otherwise $S_i\ge 1+2>2$. So $C_i$ has one element which must be $2$.
If $k=2$ then $C_i$ cannot have more than two elements, otherwise $S_i\ge 1+2+3>4$. So $C_i$ has exactly two elements, and since $1+3$ is the only way to represent $4$ as a sum of two distinct elements, $C_i=A_2$.
If $k=3$, $S_i\ge 1+2+3$ and since equality is achieved, we must have exactly $C_i=A_3$, which finishes the proof. $\blacksquare$
Then we must have $A_k=C_2=C_3=\dots$ by induction. It is clear that the sequences that satisfy $|C_1|=k\le 3$ and $A_k=C_2=C_3=\dots$ all satisfy the problem condition, so these are all the possibilities.