Seems like Jumpy snuck onto the PSC and applied a move to Problem 1 See Theorem 1 here.

on a mock IMO I made for the 2020 USA IMO team. I also sent this mock IMO to the 2021 team, so let's see how they do...

Seems like I posted on the wrong P6 thread, so I'm copying this over here. First of all, here is the key idea for the solution of this problem: You need to have some experience with linear algebra (and have some intuition about it). More precisely: Suppose $|A|=k$. Let's view the $B_i$ as vectors $v_i$ in $\{ 0, 1 \} ^k$. If $k$ would be small, then we would be able to find a linear combination of $v_i$ with small integer coefficients. But then we would get a contradiction with the fact that there is a linear combination of numbers $m, m^2, ..., m^m$ with small integer coefficients. Now, the solution: Lemma: Suppose that $v_1, ..., v_m$ are vectors in $\{ 0, 1 \}^k$ where $k<m/2$. Then there exist integer $a_1, ..., a_m$, not all zero, such that $a_1v_1 + ... + a_m v_m = 0$ and all $|a_i| < m$. Proof of the lemma: For a vector $v$ denote $v_1, v_2, ..., v_k$ its coordinates. Then for each $(c_1, ..., c_m)$ consider the ugly sum $(c_1 v_{11} + ... c_m v_{m1}) + (c_1 v_{11} + ... c_m v_{m1})m^2 + ... + (c_1 v_{11} + ... c_m v_{m1}) m^{2k-2}$. It is not that ugly actually! Anyway, each such sum is at least $0$ and less or equal to $m(m-1)(1+m^2...+m^{2k-2}) = m(m-1) \cdot \frac{m^{2k}-1}{m^2-1} < m^m$ and we have $m^m$ different ways to pick $(c_1, ..., c_m)$. Then for some two of those ways, say $(c_1, ...., c_m)$ and $(c_1',...,c_m')$ the ugly-sum will be the same. Let $a_i = c_i - c_i'$. Then we will be done, cause if the ugly-sum is equal to zero then each of the things in parentheses must be zero (cause each thing in parentheses is between $-m^2$ and $m^2$ and we have a linear combination of powers of $m^2$ that is zero). Sorry for not writing down all the algebra, but I hope it is clear. Now, let's use the lemma to solve the problem. Suppose $|A| =k$ and let $v_i$ be the vector in $\{ 0, 1 \}^k$ such that $v_{ij} = 1$ if the $j-th$ biggest element of $A$ is in $B_i$, and $v_{ij} = 0$ otherwise. Suppose that $k < m/2$. Apply the lemma above to $v_i$ and find the corresponding $a_i$. But then if we multiply elements of $B_1$ by $a_1$, elements of $B_2$ by $a_2$ ... and add the numbers we will get that $a_1 m + a_2 m^2 + ... a_m m^m = 0$ where $a_i$ are not all zero and $-m < a_i < m$. This is impossible. Contradiction. So done.

I happened to get the main idea at the very first moment because I've seen something related to the lemma. I will first write up my solution and then lay out the detailed motivation behind it. Also this is the only problem I enjoy in Day 2... plus is this problem misclassified again? Feel like this is classified to N but it should've been C.

This technic is really common in China,so I think it is not difficult for Chinese team to solve it.

Looks a bit easy for IMO 6. I guess the $m/2$ can be improved to $m/2+cm/\log m$. It would be interesting to see whether this can be improved further...

Is there a solution that is not based on linear algebra?

kvanta wrote: Lemma: Suppose that $v_1, ..., v_m$ are vectors in $\{ 0, 1 \}^k$ where $k<m/2$. Then there exist integer $a_1, ..., a_m$, not all zero, such that $a_1v_1 + ... + a_m v_m = 0$ and all $|a_i| < m$. This is how I solved it as well. The result follows directly by applying Siegel's lemma, a somewhat well-known techinque in transcendetal number theory (but the proof is just an application of the pigeonhole principle). In the Nordic 2019 IMO camp there was a lecture where Siegel's lemma was discussed.

We in fact have $|A|\ge\left(\frac23-o(1)\right)m$. Assume that $m$ is sufficiently large. As in the solutions above, let $|A|=n$ and consider the indicator vectors $v_1,\ldots,v_n\in\{0,1\}^m$. Previously, we argued that all nonnegative multiples of $m$ less than $m^{m+1}$ can be expressed as $v=c_1v_1+\cdots+c_nv_n$ for nonnegative integers $c_1,\ldots,c_n$ less than $m$, where each coordinate of $v$ is a nonnegative integer less than $m^2$. The key idea in this better bound is that most nonnegative multiples of $m$ less than $m^{m+1}$ can be expressed as $v=c_1v_1+\cdots+c_nv_n$ for nonnegative integers $c_1,\ldots,c_n$ less than $m$, where each coordinate of $v$ lies in some interval of length $O(m^{3/2})$ by applying concentration inequalities. Let $C_1,\ldots,C_n$ be i.i.d. random variables distributed as $C$, a uniform random element of $\{0,1,\ldots,m-1\}$. Note that the $i$th coordinate of $V=C_1v_1+\cdots+C_nv_n$ is the sum of $k$ i.i.d. copies of $C$, where $k\le m$ is the number of sets among $B_1,\ldots,B_m$ that $i$ lies in. Since the range of $C$ is bounded by $m$, we have by the Azuma-Hoeffding inequality that the probability that the $i$th coordinate of $V$ deviates from its expectation by more than $m^{3/2}\log m\ge\lambda=2\sqrt{km^2\log m}$ is at most $2\exp\left(-\frac{\lambda^2}{2km^2}\right)=\frac2{m^2}$. Union bounding over all coordinates, the probability that any coordinate of $V$ deviates from its expectation by more than $m^{3/2}\log m$ is at most $\frac2m$. It follows that at least $m^m-2m^{m-1}$ nonnegative multiples of $m$ less than $m^{m+1}$ can be expressed as $v=c_1v_1+\cdots+c_nv_n$ for nonnegative integers $c_1,\ldots,c_n$ less than $m$, where each coordinate of $v$ is an integer constrained to be in some interval of length $2m^{3/2}\log m$ centered at the expectation of the corresponding coordinate of $V$. Thus, we have that $(2m^{3/2}\log m+1)^n\ge m^m-2m^{m-1}$, from which it easily follows that $n\ge\left(\frac23-o(1)\right)m$, as desired.

Awesome! Probabilistic methods always come in handy.

Is the solution in #4 correct? Because it's the simplest one here I think.

Let $k$ denote the number of elements of $A$. Suppose $2k<m$.

Now, let $x_1, \ldots, x_k$ be the elements of $A$, and let $v_j$ be the vector adjoined to the subset $B_j$ for each $j\leq m$. Finally, let $(a_1, \ldots, a_m)$ be the integer $m$-tuple satisfying the lemma applied to $v_1,\ldots, v_k$. Note that the dot product of $(x_1, \ldots, x_k)$ and $v_j$ equals $m^j$. Then the dot product of $(x_1,\ldots, x_k)$ and $0=\sum a_j v_j$ equals $\sum a_jm^j$ which cannot be zero due to the bounds on $|a_j|$ (take the largest $j$ such that $a_j$ is nonzero, and then the remaining nonzero $a_i$ are too small to reach zero). Hence, we've reached a contradiction.

Loppukilpailija wrote: kvanta wrote: Lemma: Suppose that $v_1, ..., v_m$ are vectors in $\{ 0, 1 \}^k$ where $k<m/2$. Then there exist integer $a_1, ..., a_m$, not all zero, such that $a_1v_1 + ... + a_m v_m = 0$ and all $|a_i| < m$. This is how I solved it as well. The result follows directly by applying Siegel's lemma, a somewhat well-known techinque in transcendetal number theory (but the proof is just an application of the pigeonhole principle). In the Nordic 2019 IMO camp there was a lecture where Siegel's lemma was discussed. Nice observation. Also by refinement of Siegel's lemma made by Bombieri and Vaaler in 1983 (theorem 1.3 here: https://arxiv.org/pdf/1707.05941.pdf) one can prove that $|a_i|\leq k^{k/(2(m-k)}$. That helps to prove that $k>2m/3$ unconditionally.

I wonder if this problem is classified as A or NT in the shortlist.

Justanaccount wrote: I wonder if this problem is classified as A or NT in the shortlist. What exactly makes you wonder?

Solved with Michael Gao and Kevin Wu Let the elements of $A$ be $a_{1}, a_{2}, \ldots a_{n}$. Observe that for some number $0 \leq T \leq m^{m+1} - m$, where $m | T$, we can take integers $c_{1}, c_{2}, \ldots c_{m}$ such that $0 \leq c_{i} < m$, and \[T = c_{1}m + c_{2}m^{2} + \ldots + c_{m}m^{m}\]This is true by dividing both sides by $m$, then expressing $T$ in base $m$. Now, we can express $T$ as the sum of elements in $A$, where duplicates are allowed. Observe that for each element $a_{i}\in A$, $a_{i}$ will be included at most $m(m-1)$ times (for each $c_{j}$, $a_{i}$ will be included at most $c_{j}$ times, and $c_{j} \leq m-1$ for $m$ values of $j$0. Now, observe that there are $m(m-1) + 1$ ways to choose the total number of duplicates of element $a_{i}$, so the total number of distinct sums is at least \[(m(m-1) + 1)^{|A|}\]However, there are $m^{m}$ values of $T$, so we get \[(m^{2})^{|A|} \geq (m(m-1) + 1)^{|A|} \geq m^{m} \Rightarrow m^{2|A|} \geq m^{m} \Rightarrow |A|\geq \frac{m}{2}\]

hyx wrote: This technic is really common in China,so I think it is not difficult for Chinese team to solve it. Someone told me that all six Chinese team member solved question 1,4,5,6.

Solved with Elliott Liu. Also got 3 very cryptic hints from Jeffrey Chen (stuff like "linear algebra" and "base m") We double count the number of ways to express numbers as repeat-sums of $B_k$ and repeat-sums of $a_k$ Note that we can express all multiples of $m$ in the range $[0,m^{m+1}-m]$ as pseudosums of $B_k$. Basically if, \[S_{B}(m-1) = \{\sum_{k=1}^{m} e_k B_k: \forall k, e_k\in [0,m-1]\}\]Then, we have $S_{B}(m-1)$ exactly covers all multiples of $m$ in $[0,m^{m+1}-m]$, of which there are $m^m$. However, this set of pseudosums can all be written as sums of elements of $A$ with repeats of at most $m^2-m$. \[S_A(m^2-m) = \{\sum_{k=1}^{|A|}d_k a_k: \forall k, d_k\in [0,m^2-m]\}\] This gives us \[(m^2-m+1)^{|A|} \geq S_{A}(m^2) \geq S_{B}(m-1) =m^m\]Thus, $|A|\geq \frac{m}{2}$ and we're done.

pavel kozlov wrote: Nice observation. Also by refinement of Siegel's lemma made by Bombieri and Vaaler in 1983 (theorem 1.3 here: arxiv/pdf/1707.05941.pdf) one can prove that |a_i| > k^{k/(2(m-k)}. That helps to prove that k>2m/3 unconditionally. Could you please elaborate on how to apply Siegel's lemma to solve this problem? I currently cannot see, how to use it, since the RHS to our system of equations is the vector (m, m^2, ..., m^m), not (0, 0, ..., 0), as required by Siegel's lemma. I tried to add a "fictive" variable a_{k+1} = 1 to a_1, ..., a_k, so that we have equalities ...a_1 + ... + ...a_k - m^i a_{k+1} = 0 for each i, but the determinant of MM^{T} does not seem to be well-bounded, where M is a matrix of ones and zeros with the last column equal to (m, m^2, ...). (no latex, because it is my first post here, and the website does not allow to insert "images" and links).

Aliaksei wrote: Could you please elaborate on how to apply Siegel's lemma to solve this problem? Please read solution of kvanta in post #3

pavel kozlov wrote: Aliaksei wrote: Could you please elaborate on how to apply Siegel's lemma to solve this problem? Please read solution of kvanta in post #3 Somehow overlooked it. Thank you! However, I fail to repeat the way you obtain the bound k > 2m/3. As far as I understand, the refinement of Siegel's lemma suggests us to consider a matrix M of dimension k х m, consisting of 0's and 1's. We want to find a = (a_1, a_2, ..., a_m) such that Ma = (0, ..., 0). Then we consider a matrix M M^{T}, which has dimension k x k, and where each entry is bounded by m. I only see how to estimate det (MM^T) by (m\sqrt{k})^k, which gives bound max |a_i| <= (m\sqrt{k})^{k/2(m-k)}, from where I can only deduce the inequality k > (4/7 - o(1))m, which is a weaker bound. Could you please elaborate on how to obtain the bound k > 2m/3 with Siegel's? (Still, no latex, since new users cannot post images)

thinker123 wrote: BTW, to be honest this was wayyy too easy for IMO P6. Does anyone else feel this way? Ah yes, problems really feel easy after reading the solutions

Aliaksei wrote: However, I fail to repeat the way you obtain the bound k > 2m/3. just look at square matrix $M$ of size $k$ formed by vectors $v_i$. Here $det(M\cdot M^T)\leq k^{k/2}$ and so on...

pavel kozlov wrote: Aliaksei wrote: However, I fail to repeat the way you obtain the bound k > 2m/3. just look at square matrix M of size k formed by vectors v_i. Here det MM^T <= k^{k/2} and so on... Siegel's lemma is not applicable to square matrices. Based on your bound k^{k/2(m-k)}, it seems to me that you apply Siegel's lemma to the matrix M of dimension k х m. But I see no way to estimate det MM^T better than (mk^{1/2})^k for such M.

If \(A=\{a_1,\ldots,a_n\}\) has \(n\) elements then we are given each \(m^k\) may be expressed in the form \[m^k=\varepsilon_{k1}a_1+\varepsilon_{k2}a_2+\cdots+\varepsilon_{kn}a_n\quad\text{where}\quad0\le\varepsilon_i\le1.\] Consider the \(m^m\) nonnegative multiples of \(m\) less than \(m^{m+1}\). Each \(mj<m^{m+1}\) may be represented in base \(m\) as \[mj=d_m\cdot m^m+d_{m-1}\cdot m^{m-1}+\cdots+d_1\cdot m\quad\text{where}\quad0\le d_i\le m-1.\] Now consider \[w_j:=\sum_{i=1}^md_i\varepsilon_{ij}\le m(m-1),\]defined so that \[mj=w_1a_1+w_2a_2+\cdots+w_na_n\quad\text{where}\quad0\le w_i\le m(m-1).\] Expressions of the above form may describe at most \((m^2-m+1)^n\) distinct numbers, so we have the inequality \[m^m\le(m^2-m+1)^n<m^{2n}.\]from which it is clear \(n\ge m/2\).

Solution (this should be quite short and simple): For A consisting of p elements, where p is prime, consider the characteristic vectors of subsets as 0-1 vectors in the vector space F_p^p (each coordinate of the length-p vector is modulo p) and we can see that all p-ary linear combinations of the characteristic vectors of the subsets are different as they have different (weighted) sums. Therefore p^(number of subets) <= p^p and thus number of subsets is at most p. In other words, for m prime, A contains at least m elements. To complete the proof, take p as the largest prime that is at most m (there is one at least m/2, small cases can be covered separately), and note monotonicity since we might as well increase the number of subsets from p to m, and we might as well have coefficients for subsets in {0,1,...,m-1} instead of its subset {0,1,...,p-1}. Or actually why not look at the module Z_m^m, coefficients modulo m, think of the set {0,1,...,m-1} and we have a similar proof that m^(number of subsets) <= m^m and thus number of subsets at most m. So size of A is at least m (looking at vectors of length |A| with entries modulo |A|). Am I missing something here? Is there a counterexample?

A better estimate can be proven. The set $A$ contains at least $ \displaystyle \frac{2m}{3}$ elements. Or even slightly sharper: It contains at least $ \displaystyle \left(\frac{2}{3}+\frac{c}{\log m} \right)m$ elements, where $c>0$ is some absolute constant. The problem boils down to prove the following pure linear algebra claim. Claim. Let $ v_1,v_2,\dots,v_m$ be $ n$ dimensional binary vectors (their coordinates are only $0$'s and $1$'s ) and $ n<\frac{2}{3}m$. Then, for some $k, 2\le k\le m$ the vector $ v_k$ can be represented as $$ \displaystyle v_k=\sum_{i=1}^{k-1} \alpha_i v_i\,;\, |\alpha_i|<m,i=1,2,\dots,k-1 \qquad(1)$$The proof of this claim and more detailed discussion can be found in my blog. Here, in order to sketch the main idea, I'll provide a proof for the particular case when the first $n$ vectors $v_1,v_2,\dots,v_n$ are linearly independent and thus are basis vectors in $\mathbb{R}^n$. We denote by $\det(v_1,v_2,\dots,v_n)$ the determinant which columns are the vectors $v_1,\dots,v_n$ in this order. Obviously $\left|\det(v_1,v_2,\dots,v_n)\right|\ge 1$ since it is a non-zero integer. We can write $$v_{n+1}=\sum_{i=1}^n \alpha_i v_i, \alpha_i\in \mathbb{R} $$If $|\alpha_i|<m,i=1,\dots,n$ we are done, so suppose $|\alpha_k|\ge m$ for some $k,1\le k\le n.$ Cramer's rule yields $$|\alpha_k|=\frac{\left|\det(v_1,v_2,\dots,v_{k-1},v_{n+1},v_{k+1},\dots,v_n) \right|}{\left|\det(v_1,v_2,\dots,v_n) \right| } \ge m$$hence $${\left|\det(v_1,v_2,\dots,v_{k-1},v_{n+1},v_{k+1},\dots,v_n) \right|}\ge m.$$Note that the vectors $$v_1,v_2,\dots,v_{k-1},v_{n+1},v_{k+1},\dots,v_n$$are also linearly independent, so $v_{n+2}$ can be written as some linear combination of them. If some of those coefficients has absolute value at least $m$ we again apply the same trick and get some permutation of those vectors with determinant in absolute value at least $m^2.$ So, proceeding in this way for $v_{n+1},v_{n+2},\dots,v_m$ either we get a representation as in $(1)$ or we find a permutation of binary vectors with determinant in absolute value at least $m^{(m-n)}$. The latter case is impossible if $n<2m/3.$ Indeed, the determinant of any $n\times n$ matrix that consists only of $0$'s and $1$'s can have an absolute value at most $n^{n/2}.$ (see here) It yields $$n^{n/2}\ge m^{(m-n)}\ge n^{(m-n)}$$hence $n\ge 2m/3$ which contradicts the imposed constraint of our claim.

Could someone explain to me why immediately they see this they think of it as a linear algebra problem? is it because of Siegel's motto? Maybe knowing him my question answers itself but I don't know him

Solved with rama1728. Say $|A| = N$ and $A = \{a_1,a_2, \dots , a_n\}.$ Let $S$ be the set of (at most) $(m^2-m+1)^N$ integers that can be written as $$c_1a_1 + c_2a_2 + \dots + c_{N}a_N$$Where $c_1,c_2, \dots c_N$ are integers between $0$ and $m^2-m$ inclusive. We claim all nonnegative multiples of $m$ less than $m^{m+1}$ are in $S.$ Each such integer has sum of its digits in base $m$ at most $m(m-1),$ and its units digits is $0.$ So it equals the sum of the sums of the elements of at most $m(m-1)$ (not necessarily distinct) subsets taken from $\{B_1,B_2, \dots B_m\},$ each of which encompasses distinct elements in $S,$ so the desired linear combination exists. There are $m^m$ of these multiples, so $(m^2-m+1)^N \ge m^{m} \implies N \ge \frac{m}{2}.$ $\square$

2000th post! Let $|A|=n$, and treat the $B_i$ as vectors $v_i$ in $\{0,1\}^n$, where $v_{ij}=1$ if the $j$th element of set $A$ is in $B_i$ and $v_{ij}=0$ otherwise. Henceforth suppose FTSOC that $n<\frac{m}{2}$. Claim: There exist integers $a_1, a_2\ldots, a_m$ so that $a_1v_1+a_2v_2+\ldots+a_mv_m=0$ and $|a_i|<m$ for any $i$. Proof: We have a sequence $b_i$, where $1\le i\le m$, and all the elements (non necessarily distinct) are integers from $0$ to $m-1$, inclusive. Consider the sum\[(b_1 v_{11}+b_2 v_{21}+\ldots+b_m v_{m1})+(b_1 v_{12}+b_2 v_{22}+\ldots+b_m v_{m2})m^2+\ldots+(b_1 v_{1n}+b_2 v_{2n}+\ldots +b_m v_{mn})m^{2n-2}\]This sum is less than or equal to $m(m-1)\left(\frac{m^{2n}-1}{m^2-1}\right)=m\frac{m^{2n}-1}{m+1}< m^{2n}-1<m^m$. This sum is also greater than or equal to $0$. Since there are $m^m$ ways to make sequence $b_i$, for some such distinct sequences $b_i$ and $b'_i$, the sum will be equal for both of them. We can see that\[b_1v_{11}+b_2v_{21}+\ldots+b_mv_{m1}=b'_1v_{11}+b'_2v_{21}+\ldots+b'_mv_{m1},\]and so on (because they are less than or equal to $m(m-1)<m^2$). So a valid sequence $a_i$ is just $b_i-b'_i$. In fact the minimum value is $0-(m-1)=-m+1$ and the maximum value is $m-1$. This implies $-m<a_i<m$. $\blacksquare$ Multiply each element in $B_i$ by $a_i$ and we get $a_1 m+a_2m^2+\ldots+a_m m^m=0$. This is a contradiction as it implies $m\mid a_1\implies |a_1|\ge m$.

let A={a_{1},....,a_{n}} where n=|A| denote by t(Z) the transposite of Z=(z_{1},...,z_{m}) X=(a_{1},....,a_{n}) and Y_{k} for 0<=k<=m such that X.t(Y_{k})=m^k let M=(t(Y_{1}),....,t(Y_{m})) and Y=(m,.....,m^m) then we have X.M=Y S={Z=(z_{1},.....,z_{m})/ 0<=max{z_{i} / 1<=i<=m} <=m-1} D={Σx_{i}.m^i / for all i in[|1,m|] 0<=x_{i}<=m-1} C={M.Z / Z in S} define φ(t(Z))=Y.t(Z)=X.M.t(Z) from S to D then φ is injective ( uniqueness of the writing in base of m) thus m^m<=|Im(φ)|<=|C| but : M.Z as a vector it has for every coordinate m(m-1)+1 choice ( z_{i} 's range in [|0,m-1|] and M contains 0 or 1 as a coordinate so the range of any coordinate of M.Z is [|0,m(m-1)|] which is m(m-1)+1choice) so m^m<=(m(m-1)+1)^n<=m^(2n) therefore n>=m/2 qed

Assume by opposite that $A=\left \{ a_1,a_2,...,a_n\right \}$ for $n<\frac m2$. Let $s_i=m^i$ denotes sum of elements of $B_i$. Note that all $m^m$ numbers of type $\sum_{k=1}^m s_k \alpha_k$ (for $\alpha_i \in \left \{ 0,1,...,m-1\right \}$) are different, because there is unique representation of number in $m-\text{base}$ system. On the other hand, all this numbers can be represented as $\sum_{k=1}^n a_k\beta_k$ for $\beta_k\in \left \{ 0,1,...,m(m-1)\right \}$, so there are at most $(m^2-m+1)^n<m^{2n}<m^m$ distinct numbers between them, contradiction.

Let $n = |A|$. Represent $B_i$ as vectors in ${\mathbb Z}^n$. Claim: If we have $m \ge 2c$ vectors $a_1, \dots, a_m$ in ${\mathbb Z}^c$, then some nontrivial linear combination of $a_i$ with coefficients of absolute magnitude less than $m$ sums to $0$. Proof. Note that for each $i = 1, \dots, m - c$ it follows that $a_i, a_{m-c+1}, \dots a_m$ has a nontrivial solution in ${\mathbb F}_2^m$, which by scaling gives $m$ nontrivial solutions. As such, we get at least $m^(m-c)$ nontrivial solutions in ${\mathbb F}_m^n$ over all vectors. However, the multiset $\mathcal L = \{\sum e_ia_i \mid 0 \le e_i < m \}$ has at most $m^c$ elements that get mapped to $0$ through embedding in ${\mathbb F}_m^n$. Since, $m^(m-c) \ge m^c$, it follows that either the zero vector is in $\mathcal L$, in which case we are done, or that two elements in $\mathcal L$ are equal, in which case subtracting them gives the desired result. $\blacksquare$ Now, for any $-m < e_i < m$, we have that $\sum e_ia_i$ has a sum of $\sum e_i m^i$, which is only $0$ if each $e_i$ is $0$. By the lemma, this can only hold if $n \ge \frac{m}{2}$.

Let $S=\{s_1,s_2,\dots,s_l\}$ have $l$ elements, and let the vector $S=[s_1,\dots,s_l]$. Let the vector $b_i=[a_{i,1},a_{i,2},\dots,a_{i,l}$ with $a_{i,j}=1$ if $_j$ is used in the sum for $b_i$ to be $m^i$ and $0$ if it is not used in that sum. Now, consider $\sum_{i=1}^m a_i(S\cdot b_i)$ where $0\leq a_i\leq m-1$ for all $i$. Note that this simply is a base $m$ representation, and all $m^m$ multiples of $m$ between $0$ and $m^{m+1}-m$ can be expressed this way. However, looking at it from each $s_i$ individually, we get that each $s_i$ appears anywhere between $0$ and $m(m-1)$ times. Thus, this sum takes at most $(m(m-1)+1)^l$ distinct values. Then, combine this with above to get $m^{2l}>(m^2-m+1)^l\geq m^m$ which finishes. Remark: Is this alg, combo, or nt lmao

Let $A$ be $\{a_1,a_2,\dots,a_n\}$. For each $1\le i\le m$, let $m^i=a_1\varepsilon_{i1}+a_2\varepsilon_{i2}+\dots+a_n\varepsilon_{in}$ where $\varepsilon_{ij}\in \{0,1\}$ for all $(i,j)\in \{1,2,\dots,m\}\times \{1,2,\dots,n\}$. We can represent all integers from $0\le k\le m^m-1$ as \[k=\frac{1}{m}\left(b_1m+b_2m^2+\dots+b_mm^m\right)\]Where $0\le b_i\le m-1$. If we substitute in the representation of $m^i$ as a sum of elements in $A$ then we are left with \[k=\frac{1}{m}\sum_{i=1}^{n}{a_i(b_1\varepsilon_{1i}+b_2\varepsilon_{2i}+\dots+b_m\varepsilon_{mi})}\]Note that $k$ takes $m^m$ different values, so there must be $m^m$ different values representable by the right hand side through different choices of the coefficient $b_1\varepsilon_{1i}+b_2\varepsilon_{2i}+\dots+b_m\varepsilon_{mi}$. Note that this coefficient is between $0$ and $m(m-1)$ therefore there are at most $m^2-m+1<m^2$ ways to represent each coefficient. There are $n$ coefficients, so the number of different numbers the RHS can produce is less than $m^{2n}$ so $n>\tfrac{m}{2}$ as desired.

Let $|A|=n$ and the elements be $A=\{a_1, a_2, \ldots, a_n\}$. Claim: Every non-negative integer multiple $mt$ of $m$ less than $m^{m+1}$ can be written as: \[mt=t_1a_1+t_2a_2+\cdots+t_na_n\]where $0\leq t_j\leq m^2-m$ for each $1\leq j\leq n$. Proof. (Constructive) Note that since $mt\leq m^{m+1}$, we have $mt=(b_mb_{m-1}\ldots b_10)_m$ in base $m$ where each $0\leq b_i\leq m-1$ for $1\leq i\leq m$. So, we may write \[mt = b_mm^m + b_{m-1}m^{m-1}+\cdots+b_1m+0 \]\[= b_m(\text{sum of elements of }B_m)+b_{m-1}(\text{sum of elements of }B_{m-1})+\cdots+b_1(\text{sum of elements of }B_1)\]Expanding out, we get that we can write $mt=t_1a_1+t_2a_2+\cdots+t_na_n$. The fact that $t_j\leq m^2-m$ follows from the fact that any element of $A$ can appear in at most $m$ sets from $B_1, B_2, \ldots, B_m$, and the coefficients $b_1, b_2, \ldots, b_m$ are at most $m-1$, which means the final coefficient of that element is at most $m(m-1)$. The claim is therefore true. $\blacksquare$ Note that $(t_1, t_2, \ldots, t_n)\in\{0,1,\ldots,m^2-m\}^n$, which means there are at most $(m^2-m+1)^n$ distinct sums possible which can be written as \[\text{sum}=t_1a_1+t_2a_2+\cdots+t_na_n\]However, we have given a construction that there are at least $m^m$ distinct sums possible as there are $m^m$ non-negative integer multiples of $m$ less than $m^{m+1}$. This means $(m^2-m+1)^n \geq m^m$ and hence $n\geq \frac m2$. $\blacksquare$

Let $A = \{a_1 < a_2 < \dots a_k\}$. Our problem condition implies that for all $1 \le i \le m$, there exist $\varepsilon_{(i, 1)}, \varepsilon_{(i, 2)}, \dots, \varepsilon_{(i, k)} \in \{0, 1\}$ such that $a_1\varepsilon_{(i, 1)} + a_2\varepsilon_{(i, 2)} + \dots + a_k\varepsilon_{(i, k)} = m^i$. Take any nonnegative integer $M$ between $0, m^{m+1} - 1$ that is divisible by $m$. We can write $M = b_sm^s + b_{s-1}m^{s-1} + \dots + b_1m^1$ for some positive integer $s$ and some nonnegative integers $b_1, b_2, \dots, b_s \le m-1$. Thus, we get $M = \sum_{i=1}^{k} a_i(b_s\varepsilon_{(s, i)} + b_{s-1}\varepsilon_{(s-1, i)} + \dots + b_1\varepsilon_{(1, i)})$ and note that $b_s\varepsilon_{(s, i)} + b_{s-1}\varepsilon_{(s-1, i)} + \dots + b_1\varepsilon_{(1, i)} \le (m-1)s \le (m-1)m$, so we can write any nonnegative integer $M$ that is divisible by $m$ into a form $a_1x_1 + a_2x_2 + \dots + a_kx_k$ where $x_i$ are nonnegative integers that are not exceed $m(m-1)$. There are exactly $m^m$ nonnegative integers that are divisible by $m$ between $0$ and $m^{m+1}-1$, and $x_i$ can take at most $m(m-1) + 1$ values, we derive $m^m \le (m(m-1) + 1)^k < m^{2k}$, thus $\frac{m}{2} \le k$, as wanted. $\blacksquare$

Let $A = \{ a_1, a_2, \dots, a_k \}$ and define \[ \epsilon_{i, j} = \begin{cases*} 1 & $a_j \in B_i$ \\ 0 & $a_j \not\in B_i$ \end{cases*} \]We can therefore model \begin{align*} S_i = \sum_{x \in B_i} x = \epsilon_{i, 1} a_1 + \epsilon_{i, 2} a_2 + \cdots + \epsilon_{i, k} a_k = m^i \end{align*}By using base $m$, one can choose a unique tuple $\{ C_1, C_2, \dots, C_m \}$ and $0 \le C_i \le m-1$ such that $\sum S_iC_i$ can generate any number from $m$ to $m^{m+1} - 1$. We let \begin{align*} C'_j = \sum_{i} C_i\epsilon_{i, j} \end{align*}such that \begin{align*} C'_1a_1 + C'_2a_2 \cdots + C'_ka_k \end{align*}can generate any value between $m$ and $m^{m+1}-1$. Therefore the number of tuples of $(C'_1, C'_2, \dots, C'_k)$ must be at least $m^{m+1} - m$. There are $m^2-m$ possibilities for each value of $C'_i$ so we have $m^{2k} > (m^2 - m)^k \ge m^{m+1} - m \ge m^m$ so $k > \tfrac{m}{2}$ and we are done.