Goodbye, 2021.

It is the last moment of 2021. The very last. Do your last farewells.

I thank God and my parents for all the opportunities they have given me during this year. 

And I hope me and everyone get even better ones in the coming year. 

After this, no more 2021. 

I would like to share a meme at this moment. 




On this occasion, I am solving 2021 IMO #6; as the last of 2021. 

Let $m\ge 2$ be an integer, $A$ a finite set of integers (not necessarily positive) and $B_1,B_2,...,B_m$ subsets of $A$. Suppose that, for every $k=1,2,...,m$, the sum of the elements of $B_k$ is $m^k$. Prove that $A$ contains at least $\dfrac{m}{2}$ elements.


Let $A=\{a_1, a_2, a_3, \dots, a_n\}$. Note that for some number $0 \leq N \leq m^{m+1} - m$ with $m | N$, we can choose integers $x_{1}, x_{2}, \ldots x_{m}$ so that $$0 \leq x_{i} < m$$ and \[N = x_{1}m + x_{2}m^{2} + \ldots + x_{m}m^{m}.\] We know this by dividing both sides by $m$ and then writing $N$ in base $m$. Next, notice that we can write $N$ as the sum of elements in $A$, where duplicates are permitted in the sum. Also, for each element $a_{i}\in \text{set }A$, $a_{i}$ will be included maximum $m(m-1)$ times. We know this because for each $x_{j}$, $a_{i}$ will be included at most $x_{j}$ times, and $x_{j} \leq m-1$ for the $m$ values of $j$. Next, we know that that there are $m(m-1) + 1$ ways to choose the total number of copies of element $a_{i}$, hence the total number of distinct sums is at minimum $(m(m-1) + 1)^{|A|}$. But there are $m^{m}$ values of $N$, so we obtain 

$$m^{m} \leq (m(m-1) + 1)^{|A|} \leq (m^{2})^{|A|}$$ 

$$\implies m^{2|A|} \geq m^{m} \Rightarrow |A|\geq \frac{m}{2},$$

which was what had to be proven. $\square$ 


Comments

Popular posts from this blog

1995 IMO #2

Inequality problem I made