For a positive integer $n$, $(a_0, a_1, \cdots , a_n)$ is a $n+1$-tuple with integer entries. For all $k=0, 1, \cdots , n$, we denote $b_k$ as the number of $k$s in $(a_0, a_1, \cdots ,a_n)$. For all $k = 0,1, \cdots , n$, we denote $c_k$ as the number of $k$s in $(b_0, b_1, \cdots ,b_n)$. Find all $(a_0, a_1, \cdots ,a_n)$ which satisfies $a_0 = c_0$, $a_1=c_1$, $\cdots$, $a_n=c_n$.
Problem
Source: 2017 FKMO Day 1 Problem 2
Tags: combinatorics
25.03.2017 16:59
I have no idea how to solve this rip, I guess you need a good bound for $a_0=c_0$
25.03.2017 17:09
Some Progress!
25.03.2017 18:06
25.03.2017 19:24
The problem can be much easier if you know this problem.
25.03.2017 23:14
The solution has already been provided by @talkon but the configuration is exciting and here are some interesting (?) things I found. Let the uppercase letter denote the sequence, so $X=(x_i)_{0\leq i\leq n}$ as an example and similarly. We shall consider sequences having their elements ranging from $0$ to $n $, since $B $ and $C $ clearly satisfy this condition by definition hence so does $A=C $. Let $\Gamma $ be the set of all $(n+1)$-tuple of integers all of whose elements are non-negative integers less than $(n+1) $. Henceforth all sequences $X $ that shall be considered $\in \Gamma $. Clearly $A,B,C\in\Gamma $ by previous observation. Let $f: \Gamma\longrightarrow\Gamma $ be the function that replaces a sequence $X $ with $Y $ where $y_i= $ number of occurences of $i $ in $X $. Thus $B=f (A),A=f (B) $. So here are some interesting observations. $\text {Lemma 1:}$ For a sequence $X\in\Gamma, f^{-1}(X) $ exists if and only if $\sum_{i=0}^nx_i=(n+1).$ $\text {Proof}: $ Suppose there exists $Y\in\Gamma $ such that $f (Y)=X $, then $x_i $ is the number of occurences of $i $ in $Y $. Hence $\sum_{i=0}^nx_i $ is equal to the number of elements of $Y $ that are smaller than $(n+1) $. Since all the elemnts of $Y $ satisfy this condition, $\sum_{i=0}^nx_i $ is equal to the number of elements of $Y $ which is $(n+1) $. Now suppose $\sum_{i=0}^nx_i=(n+1) $ then consider a sequence $Y $ which has $x_i $ occurences of $i$, this is clearly possible simply let $y_i=t\forall \sum_{r=0}^{t-1}x_r\leq i <\sum_{r=0}^{t}x_r$. Hence the claim is proven. $\text {Lemma 2}: $ For any $X\in\Gamma $ let $Y=f (X)$, then $\sum_{i=0}^nx_i=\sum_{i=0}^niy_i $. $\text {Proof}:$ $y_i $ is the number of occurences of $i $ in $X $, hence $iy_i $ is the sum of all such occurences in $X $. Hence $\sum_{i=0}^niy_i $ is the sum of all numbers in $X $ smaller than $(n+1) $, since all elements of $X $ are smaller than $(n+1) $, we conclude that tjis sum is equal to sum of elements of $X $ hence the claim follows. $\text {Lemma 3}: $ For any $X\in\Gamma, f^{-1}(f^{-1}(X))$ exists if and only if $\sum_{i=0}^nx_i=\sum_{i=0}^nix_i=(n+1) $. $\text {Proof}: $ Suppose $f^{-1}(f^{-1}(X)) $ exists. Put $f (Y)=X,f (Z)=Y $, then $\text {Lemma 1} $ applied to $X $ and $Y $ tells us $\sum_{i=0}^nx_i=\sum_{i=0}^ny_i=(n+1) $. Applying $\text {Lemma 2} $ to $X $ we obtain $\sum_{i=0}^nix_i=\sum_{i=0}^ny_i=(n+1) $. Now suppose $\sum_{i=0}^nx_i=\sum_{i=0}^nix_i=(n+1) $. Then $\text {Lemma 1} $ tells us that $Y\equiv f^{-1}(X)\in\Gamma$. Then $\text {Lemma 2} $ applied to $Y $ tells us that $\sum_{i=0}^ny_i=\sum_{i=0}^nix_i=(n+1) $, hence $\text {Lemma 1} $ applied to $Y $ tells us that $Z\equiv f^{-1}(Y)\in\Gamma $, hence $Z\equiv f^{-1}(f^{-1}(X)) $ exists. Hence the claim is proven. These are all the observations that I could make. Can someone find more properties amd completely characterise $f $ on $\Gamma $?
16.08.2017 15:13
This problem sems to be too similar to 2001 C5.But can anyone continue this idea. Counting in two ways we get $n+1=a_0+...+a_n=b_0+...+b_n=0*a_0+...+n*a_n=0*b_0+...+n*b_n $
03.10.2017 23:47
rkm0959 wrote:
I have no idea how to solve this rip, I guess you need a good bound for $a_0=c_0$ How did you get/think of the last two generalized n-tuples? I spent quite a while bashing with babu2001-like logic and kind of gave up after finding the other stuffs...
02.10.2020 07:23
If $n=0,1,2$ there are no solutions. When $n=3$ it is easy to check that the only solutions are $(1,2,1,0)$ and $(2,0,2,0)$. Now assume $n\geq 4$. Suppose $a,b,c$ are such sequences. Now since $c_i$ are integers in the range $[0,n+1]$, $a_i$ are also integers in that range. If $c_i=n+1$ for some $i$ then $b$ is a constant sequence, which obviously yields no solution. Hence all the integers are in the range $[0,n]$. Therefore, we have $$b_0+b_1+...+b_n=n+1\qquad(1)$$and similarly $$c_0+c_1+...+c_n=a_0+a_1+...+a_n=n+1\qquad(2)$$$\noindent\rule{15.5cm}{0.01pt}$ Now obviously $a_0,b_0,c_0$ are all positive. CLAIM. $a_0-1\leq b_0\leq a_0+1$ Proof. Suppose that there are $m$ integers which are positive among $a_1,...,a_n$. On one hand, each of those postive integer belongs to one of $b_1,b_2,...,b_n$, hence $$m=b_1+b_2+...+b_n-1=n-b_0 \qquad(3)$$On the other hand each of those integer is at least $1$, hence $$m\leq a_1+a_2+...+a_n=n+1-a_0\qquad(4)$$This implies $a_0-1\leq b_0$. By symmetry we have $b_0-1\leq c_0=a_0$. This proves the CLAIM. $\blacksquare$ $\noindent\rule{15.5cm}{0.01pt}$ Now we are just left with some boring casework. CASE I: $b_0=a_0-1$ Let $x_1,x_2,...,x_m$ be the positive integers among $b_1,b_2,...,b_m$. Then from $(3)$ $m=n-b_0$ while $x_1+x_2+...+x_m=a_1+a_2+...+a_n=n+1-a_0=n-b_0$, hence each of the $x_is$ equals $1$. Hence $b_i=0$ for all $i\neq a_0,1,0$. Therefore $a_0=c_0\geq n-2\neq 0,1$. THis implies $c_0=n-2=a_0$, hence $b_0=n-3$. Therefore $b_1=3$ and $b_{n-2}=1$, while all other numbers are $0$. This yields the solution $(a_0,a_1,...,a_n)=(n-2,1,0,1,0,...0,1,0,0,0)$, where $n\geq 6$. When $n=5$ we have $(3,1,1,1,0,0), (3,2,1,1,0,0)$ as the other solution. CASE II: $b_0=a_0$ Similarly, $x_1+x_2+...+x_m=a_1+a_2+...+a_n=n+1-b_0$, while $m=n-b_0$. Therefore exactly one $x_i$ equals $2$ while the others are all equal to $1$. Hence $b_i=0$ for all $i\neq a_0,2,1,0$. For all $n>5$ we have $a_0\geq n-3\neq 0,1,2$. Hence $a_0=n-3$, $b_1=2$, $b_1=1$. This yields the solution $(a_0,a_1,...,a_n)=(n-3,2,1,0,...0,,1,0,0,0)$. When $n=4$ we have another solution namely $(2,1,2,0,0)$. CASE III: $b_0=a_0+1$. Similarly, $x_1+x_2+...+x_m=a_1+a_2+...+a_n=n+2-b_0$, while $m=n-b_0$. Therefore they are either $3,1,1,...,1$ or $2,2,1,...,1$. For the former, we have $a_0=n-3$ and $b_1=b_3=b_{n-3}=1$. This yields the solution $(a_0,a_1,...,a_n)=(n-3,3,0,...,0,1,0,0)$. For the latter we have $a_0=n-2$, which is impossible since $a_0+2+2>n+1$. For $n=5 $ we also have $(2,3,0,1,0,0)$.