Problem - 01 - National Math Camp 2021 Mock Exam - "Not as bad as it looks"
Posted: Thu May 13, 2021 12:03 am
by Anindya Biswas
Let $a_1 \leq a_2 \leq a_3 \cdots \leq a_n$ be a sequence of positive integers. For $1 \leq i \leq a_n$, let $b_i$ be the number of terms in the sequence that are not smaller than $i$. It is given that,
$b_1 > b_2 > \cdots > b_{a_n}$,
for each $1 \leq i \leq a_n, b_i$ is a power of three, and
$b_1 = 3^{2021}$
Find the sum of $\sum_{j=1}^na_j$ over all possible sequences $\{a_i\}$.
Re: Problem - 01 - National Math Camp 2021 Mock Exam - "Not as bad as it looks"
Let $a_1 \leq a_2 \leq a_3 \cdots \leq a_n$ be a sequence of positive integers. For $1 \leq i \leq a_n$, let $b_i$ be the number of terms in the sequence that are not smaller than $i$. It is given that,
$b_1 > b_2 > \cdots > b_{a_n}$,
for each $1 \leq i \leq a_n, b_i$ is a power of three, and
$b_1 = 3^{2021}$
Find the sum of $\sum_{j=1}^na_j$ over all possible sequences $\{a_i\}$.
I am not getting, why this question should have a single answer??? If it has multiple answers, then how should I express those answers???
Re: Problem - 01 - National Math Camp 2021 Mock Exam - "Not as bad as it looks"
Let $a_1 \leq a_2 \leq a_3 \cdots \leq a_n$ be a sequence of positive integers. For $1 \leq i \leq a_n$, let $b_i$ be the number of terms in the sequence that are not smaller than $i$. It is given that,
$b_1 > b_2 > \cdots > b_{a_n}$,
for each $1 \leq i \leq a_n, b_i$ is a power of three, and
$b_1 = 3^{2021}$
Find the sum of $\sum_{j=1}^na_j$ over all possible sequences $\{a_i\}$.
I am not getting, why this question should have a single answer??? If it has multiple answers, then how should I express those answers???
Yeah it also confused me at first. It is asking for the sum of all possible values of $\sum_{j=1}^na_j$. That is, sum of the sum!
Re: Problem - 01 - National Math Camp 2021 Mock Exam - "Not as bad as it looks"
Let $a_1 \leq a_2 \leq a_3 \cdots \leq a_n$ be a sequence of positive integers. For $1 \leq i \leq a_n$, let $b_i$ be the number of terms in the sequence that are not smaller than $i$. It is given that,
$b_1 > b_2 > \cdots > b_{a_n}$,
for each $1 \leq i \leq a_n, b_i$ is a power of three, and
$b_1 = 3^{2021}$
Find the sum of $\sum_{j=1}^na_j$ over all possible sequences $\{a_i\}$.
I am not sure the answer is ok or not as the answer looks quite arbitrary.
Let,
Let, $M_g=3^{g}+3^{g-1}+\cdots 3^1+3^0$ Claim:We claim that the answer is $2^{2020}(3^{2021}+M_{2021})$
But before we go to the sum of the sequence, we need to find what the sequence actually is. For the sake of generality, we will assume $2021=g$,
Now we have $b_1>b_2>\cdots >b_{a_n}$. Since $b_1=3^g$ there are $3^g$ elements in the sequence in other words $n=3^g$.
Note,
$b_1>b_2$ means that some elements of the sequence are equal to 1.
From this part, it can go kinda crazy but bear with me.
Now we will call the sequence having $t$ numbers if the sequence has $t$ distinct numbers.
Now if the sequence has 1 number we can easily know the sum is $3^g$
If the sequence has 2 numbers the sum is $3^g+3^k$ for some $k<g$[Why? This is for the reader. Hint: $1(3^g-3^k)+2(3^k)=3^g+3^k$]
Now if the sequence has 3 numbers the sum is $3^g+3^k+3^l$ for some $l<k<g$.[Same reason as above]
Now we can do the same for other numbers, but the sequence can have at most $g+1$ distinct numbers because more than that is not possible.
Now let us make an array,
\[ \begin{array}{lcr}
& 3^g & 3^{g-1} & 3^{g-2} & \cdots & 3^1 & 3^0 \\
& 1 & 0 & 0 & \cdots & 0 & 0 \\
&1 & 0 & 0 & \cdots & 0 & 1 \\
& \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
\end{array}
\]
At the end of the array, we will multiply all the total numbers of 1's in the column with the name of the column. The sum of all those will be the required sum. why? The reason is given below:
At first, we have to know what the array is actually saying. The array, the row especially says all the ways we can choose numbers from $3^{g-1} \to 3^0$[only the powers of 3] while having $3^g$. So, there are exactly $2^{g}$ rows. Now column except for $3^g$ will have $2^{g-1}$ rows because if we also included the ways not choosing $3^g$ there would have been $2^g+1$ rows, but $2^g$ ones are in column $3^g$ and $2^g$ ones are also in the other columns. By excluding the way we can choose the numbers not having $3^g$ we lost exactly half of all the numbers except $3^g$. So there are exactly $2^g$ ones in $3^g$ column and $2^{g-1}$ ones in the other columns.
Now we will multiply the number of ones in the column with the name of the column and get
$2^g3^g+2^{g-1}3^{g-1} + 2^{g-1}3^{g-2}+ \cdots+ 2^{g-1}3^{1}+ 2^{g-1} 3^0$
$=2^{g-1}(3^g +M_g)$.
On why this sum is the answer. Recall that if we had 1 number in the sequence all the numbers are equal to 1. Or else the conditions do not hold. For 2 distinct numbers, the sum is $3^g+3^k$ where k can be any number, $0 \leq k <g$. Thus all such sums are added to the array. Similarly, others are too.
So our answer is $\boxed{2^{2020}(3^{2021}+M_2021)}$
##Note the array can also be said to be a collection of numbers in base-3. Which makes the solution more elegant and beautiful.
The solution may be a lot difficult to understand. But if any part is not understandable I will appreciate it if the reader asks about it. And the solution can also be wrong.
Re: Problem - 01 - National Math Camp 2021 Mock Exam - "Not as bad as it looks"
Let $a_1 \leq a_2 \leq a_3 \cdots \leq a_n$ be a sequence of positive integers. For $1 \leq i \leq a_n$, let $b_i$ be the number of terms in the sequence that are not smaller than $i$. It is given that,
$b_1 > b_2 > \cdots > b_{a_n}$,
for each $1 \leq i \leq a_n, b_i$ is a power of three, and
$b_1 = 3^{2021}$
Find the sum of $\sum_{j=1}^na_j$ over all possible sequences $\{a_i\}$.
I am not sure the answer is ok or not as the answer looks quite arbitrary.
Let,
Let, $M_g=3^{g}+3^{g-1}+\cdots 3^1+3^0$ Claim:We claim that the answer is $2^{2020}(3^{2021}+M_{2021})$
But before we go to the sum of the sequence, we need to find what the sequence actually is. For the sake of generality, we will assume $2021=g$,
Now we have $b_1>b_2>\cdots >b_{a_n}$. Since $b_1=3^g$ there are $3^g$ elements in the sequence in other words $n=3^g$.
Note,
$b_1>b_2$ means that some elements of the sequence are equal to 1.
From this part, it can go kinda crazy but bear with me.
Now we will call the sequence having $t$ numbers if the sequence has $t$ distinct numbers.
Now if the sequence has 1 number we can easily know the sum is $3^g$
If the sequence has 2 numbers the sum is $3^g+3^k$ for some $k<g$[Why? This is for the reader. Hint: $1(3^g-3^k)+2(3^k)=3^g+3^k$]
Now if the sequence has 3 numbers the sum is $3^g+3^k+3^l$ for some $l<k<g$.[Same reason as above]
Now we can do the same for other numbers, but the sequence can have at most $g+1$ distinct numbers because more than that is not possible.
Now let us make an array,
\[ \begin{array}{lcr}
& 3^g & 3^{g-1} & 3^{g-2} & \cdots & 3^1 & 3^0 \\
& 1 & 0 & 0 & \cdots & 0 & 0 \\
&1 & 0 & 0 & \cdots & 0 & 1 \\
& \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
\end{array}
\]
At the end of the array, we will multiply all the total numbers of 1's in the column with the name of the column. The sum of all those will be the required sum. why? The reason is given below:
At first, we have to know what the array is actually saying. The array, the row especially says all the ways we can choose numbers from $3^{g-1} \to 3^0$[only the powers of 3] while having $3^g$. So, there are exactly $2^{g}$ rows. Now column except for $3^g$ will have $2^{g-1}$ rows because if we also included the ways not choosing $3^g$ there would have been $2^g+1$ rows, but $2^g$ ones are in column $3^g$ and $2^g$ ones are also in the other columns. By excluding the way we can choose the numbers not having $3^g$ we lost exactly half of all the numbers except $3^g$. So there are exactly $2^g$ ones in $3^g$ column and $2^{g-1}$ ones in the other columns.
Now we will multiply the number of ones in the column with the name of the column and get
$2^g3^g+2^{g-1}3^{g-1} + 2^{g-1}3^{g-2}+ \cdots+ 2^{g-1}3^{1}+ 2^{g-1} 3^0$
$=2^{g-1}(3^g +M_g)$.
On why this sum is the answer. Recall that if we had 1 number in the sequence all the numbers are equal to 1. Or else the conditions do not hold. For 2 distinct numbers, the sum is $3^g+3^k$ where k can be any number, $0 \leq k <g$. Thus all such sums are added to the array. Similarly, others are too.
So our answer is $\boxed{2^{2020}(3^{2021}+M_2021)}$
The solution may be a lot difficult to understand. But if any part is not understandable I will appreciate it if the reader asks about it. And the solution can also be wrong.
Too wordy, I know. Better solution probably exists