Problem - 01 - National Math Camp 2021 Mock Exam - "Not as bad as it looks"

Discussion on Bangladesh National Math Camp
User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:
Problem - 01 - National Math Camp 2021 Mock Exam - "Not as bad as it looks"

Unread post by Anindya Biswas » Thu May 13, 2021 12:03 am

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\}$.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Problem - 01 - National Math Camp 2021 Mock Exam - "Not as bad as it looks"

Unread post by Mehrab4226 » Thu May 13, 2021 1:18 pm

Anindya Biswas wrote:
Thu May 13, 2021 12:03 am
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???
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: Problem - 01 - National Math Camp 2021 Mock Exam - "Not as bad as it looks"

Unread post by Anindya Biswas » Thu May 13, 2021 1:22 pm

Mehrab4226 wrote:
Thu May 13, 2021 1:18 pm
Anindya Biswas wrote:
Thu May 13, 2021 12:03 am
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!
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Problem - 01 - National Math Camp 2021 Mock Exam - "Not as bad as it looks"

Unread post by Mehrab4226 » Thu May 13, 2021 5:21 pm

Anindya Biswas wrote:
Thu May 13, 2021 12:03 am
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.
Last edited by Mehrab4226 on Thu May 13, 2021 7:45 pm, edited 1 time in total.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Problem - 01 - National Math Camp 2021 Mock Exam - "Not as bad as it looks"

Unread post by Mehrab4226 » Thu May 13, 2021 5:22 pm

Mehrab4226 wrote:
Thu May 13, 2021 5:21 pm
Anindya Biswas wrote:
Thu May 13, 2021 12:03 am
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
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Post Reply