Maths Olympiad Prep

Library / /421 of 462

Combinatorics Difficulty 7.2 National Olympiad, round 2 Prove it Ireland

For which positive integers nn is it possible to split the set of integers tt that satisfy 1tn20221 \le t \le n^{2022} into nn sets of equal size such that the sum of the 2021-th powers of the elements is the same for each set?

Solutions — 2

Solution 1

Solution 1. When n=1n = 1 this is obviously possible. We will show that this is possible for all integers n2n \ge 2 by proving a more general version using induction. The number 2021 will be replaced by an integer k0k \ge 0 on which we will carry out the induction. For this approach to work we will consider powers of numbers in a range that does not necessarily start with 1 and we will consider sums of powers lower than kk.
To formulate this more general statement, we first introduce some notation. When a<ba < b are two integers, we denote by [a,b][a, b] the set of integers tt that satisfy atba \le t \le b. When n2n \ge 2 and m0m \ge 0 we let d(m)d(m) be the digit sum of the base nn representation of mm. Given two integers, k0k \ge 0 and n2n \ge 2, let N=nk+1N = n^{k+1}. For i=0,1,,n1i = 0, 1, \dots, n-1 we define subsets of [0,N1][0, N-1] as follows
Si={md(m)i(modn) and 0m<N}. S_i = \{m \mid d(m) \equiv i \pmod n \text{ and } 0 \le m < N\}.
We also let Si(s)={m+smSi}[s,N+s1]S_i(s) = \{m + s \mid m \in S_i\} \subset [s, N + s - 1] be the set obtained by shifting SiS_i by the integer ss. Finally, for 0rk0 \le r \le k we define
σir(s)=mSi(s)mr. \sigma_i^r(s) = \sum_{m \in S_i(s)} m^r.
Here, even when m=0m = 0, we agree that m0=1m^0 = 1. We now fix an integer n2n \ge 2. Theorem. For all integers n,k,r,sn, k, r, s satisfying n2n \ge 2 and 0rk0 \le r \le k we have
σ0r(s)=σ1r(s)==σn1r(s). \sigma_0^r(s) = \sigma_1^r(s) = \dots = \sigma_{n-1}^r(s).
Remark. Setting s=1s = 1 and r=k=2021r = k = 2021 solves the original problem.
Proof. We do induction on k0k \ge 0. We keep nn fixed throughout the proof. The base case, k=0k = 0, is trivially true, because the only possible value for rr is zero, m0=1m^0 = 1 and so σi0(s)=nk\sigma_i^0(s) = n^k is the number of elements in Si(s)S_i(s). Let us now fix k>0k > 0 and suppose that the statement of the theorem holds true when kk is replaced by k1k-1. To avoid confusion, we denote the sets Si(s)S_i(s) that correspond to k1k-1 by S~i(s)\tilde{S}_i(s):
S~i={md(m)i(modn) and 0m<N~} \tilde{S}_i = \{m \mid d(m) \equiv i \pmod n \text{ and } 0 \le m < \tilde{N}\}
where N~=nk\tilde{N} = n^k. Accordingly, we define S~i(s)\tilde{S}_i(s) and σ~ir(s)\tilde{\sigma}_i^r(s). The base nn representation of the numbers in [0,N1][0, N-1] is obtained from those of the numbers in [0,N~1][0, \tilde{N}-1] by prepending digits 0,1,2,,n10, 1, 2, \dots, n-1. Because d(m+cnk)=d(m)+cd(m+cn^k) = d(m)+c for m[0,N~1]m \in [0, \tilde{N}-1] and c=0,1,,n1c = 0, 1, \dots, n-1, we see that
Si=S~i(0)S~i1(nk)S~i2(2nk)S~i(n1)((n1)nk).(11) S_i = \tilde{S}_i(0) \cup \tilde{S}_{i-1}(n^k) \cup \tilde{S}_{i-2}(2n^k) \cup \dots \cup \tilde{S}_{i-(n-1)}((n-1)n^k). \quad (11)
Here we consider the subscripts modulo nn. As we assume for 0r<k0 \le r < k that σ~jr(s)=mS~j(s)mr\tilde{\sigma}_j^r(s) = \sum_{m \in \tilde{S}_j(s)} m^r does not depend on jj, we immediately get that σir(s)\sigma_i^r(s) does not depend on ii, as long as 0r<k0 \le r < k.
We are left to prove that σik(s)\sigma_i^k(s) does not depend on ii. Using (11) we obtain
mSi(s)mk=mS~i(s)mk+mS~i1(s+nk)mk++mS~i(n1)(s+(n1)nk)mk=mS~i(s)mk+mS~i1(s)(m+nk)k++mS~i(n1)(s)(m+(n1)nk)k. \begin{aligned} \sum_{m \in S_i(s)} m^k &= \sum_{m \in \tilde{S}_i(s)} m^k + \sum_{m \in \tilde{S}_{i-1}(s+n^k)} m^k + \dots + \sum_{m \in \tilde{S}_{i-(n-1)}(s+(n-1)n^k)} m^k \\ &= \sum_{m \in \tilde{S}_i(s)} m^k + \sum_{m \in \tilde{S}_{i-1}(s)} (m+n^k)^k + \dots + \sum_{m \in \tilde{S}_{i-(n-1)}(s)} (m+(n-1)n^k)^k. \end{aligned}
We now expand the expressions (m+jnk)k(m + jn^k)^k using the binomial theorem. What we obtain is of the form mk+c1mk1++ck1m+ckm^k + c_1m^{k-1} + \dots + c_{k-1}m + c_k where each coefficient cgc_g is a product of a binomial coefficient and a power of jnkjn^k. The exact values of these coefficients are not relevant here, but it is important that they are the same for all mm. Therefore,
mS~ij(s)(m+jnk)k=mS~ij(s)mk+c1mS~ij(s)mk1++ckmS~ij(s)m0=mS~ij(s)mk+c1σ~ijk1(s)+c2σ~ijk2(s)++ckσ~ij0(s). \begin{aligned} \sum_{m \in \tilde{S}_{i-j}(s)} (m + jn^k)^k &= \sum_{m \in \tilde{S}_{i-j}(s)} m^k + c_1 \sum_{m \in \tilde{S}_{i-j}(s)} m^{k-1} + \dots + c_k \sum_{m \in \tilde{S}_{i-j}(s)} m^0 \\ &= \sum_{m \in \tilde{S}_{i-j}(s)} m^k + c_1 \tilde{\sigma}_{i-j}^{k-1}(s) + c_2 \tilde{\sigma}_{i-j}^{k-2}(s) + \dots + c_k \tilde{\sigma}_{i-j}^0(s). \end{aligned}
By inductive assumption, no term that comes with a coefficient cgc_g depends on ii. Therefore,
mSi(s)mk=j=0n1mS~ij(s)mk+terms not depending on i=m[s,s+N~1]mk+terms not depending on i \begin{aligned} \sum_{m \in S_i(s)} m^k &= \sum_{j=0}^{n-1} \sum_{m \in \tilde{S}_{i-j}(s)} m^k + \text{terms not depending on } i \\ &= \sum_{m \in [s, s+\tilde{N}-1]} m^k + \text{terms not depending on } i \end{aligned}
and this does not depend on ii and the proof is complete. The last equality comes from
S~0(s)S~1(s)S~n1(s)=[s,s+N~1] \tilde{S}_0(s) \cup \tilde{S}_1(s) \cup \dots \cup \tilde{S}_{n-1}(s) = [s, s + \tilde{N} - 1]
and S~a(s)=S~a+n(s)\tilde{S}_a(s) = \tilde{S}_{a+n}(s) because we considered subscripts modulo nn. \square

Solution 2

Solution 2. We will again replace 2021 by an integer k0k \ge 0. This solution takes a more structured approach using polynomials. Like in Solution 1, we denote by [a,b][a, b] the set of integers tt that satisfy atba \le t \le b, where a<ba < b are two given integers. When n2n \ge 2 and m0m \ge 0 we let d(m)d(m) be the digit sum of the base nn representation of mm. Given any two integers, k0k \ge 0 and n2n \ge 2, we let N=nk+1N = n^{k+1} and for i=0,1,,n1i = 0, 1, \dots, n-1 we define subsets of [1,N][1, N] as follows
Si={md(m1)i(modn) and 1mN}. S_i = \{m \mid d(m-1) \equiv i \pmod{n} \text{ and } 1 \le m \le N\}.
We are going to prove that for any two integers, k0k \ge 0 and n2n \ge 2,
aSiak=bSjbkfor all i,j. \sum_{a \in S_i} a^k = \sum_{b \in S_j} b^k \quad \text{for all } i, j.
Define f(x)=1+x+x2++xn1f(x) = 1+x+x^2+\dots+x^{n-1} and let fj(x,y)=f(xnjy)f_j(x,y) = f(x^{nj}y) for 0jk0 \le j \le k. We consider the polynomial F(x,y)=xj=0kfj(x,y)F(x,y) = x \cdot \prod_{j=0}^k f_j(x,y) and we think of FF as a polynomial in xx that has coefficients which are polynomials in yy. Note that setting x=1x=1 gives fj(1,y)=f(y)f_j(1,y) = f(y) for all jj. This will be of importance towards the end of the argument.
When we multiply out completely the product that defines FF, we obtain an expression of the form
F(x,y)=m=1Ncm(y)xm F(x,y) = \sum_{m=1}^{N} c_m(y)x^m
with coefficients cm(y)c_m(y) being polynomials in yy. The exponents of xx that appear in fj(x,y)f_j(x,y) are 0,nj,2nj,3nj,,(n1)nj0, n^j, 2n^j, 3n^j, \dots, (n-1)n^j and the coefficient in front of xcnjx^{cn^j} is ycy^c. Therefore, cm(y)=yd(m1)c_m(y) = y^{d(m-1)} where d(m1)d(m-1) is the digit sum of the base nn representation of m1m-1.
Differentiating p(x)=xmp(x) = x^m with respect to xx gives p(x)=mxm1p'(x) = m x^{m-1}. When we differentiate ii times, we get p(i)(x)=(mi+1)(mi+2)(m1)mxmip^{(i)}(x) = (m-i+1)(m-i+2)\cdots(m-1)m x^{m-i}. This is conveniently written using the falling factorial power notation (see for example [1, p. 47])
mi=m(m1)(m2)(mi+1) m^i = m(m-1)(m-2)\cdots(m-i+1)
which allows us to write p(i)(x)=mixmip^{(i)}(x) = m^i x^{m-i} for the ii-th derivative of p(x)=xmp(x) = x^m. This holds true even if i>mi > m, because then both sides are equal to zero. Substituting x=1x=1 we obtain
p(i)(1)=mi.(12) p^{(i)}(1) = m^i. \qquad (12)
Usual powers mkm^k and the falling powers m0,m1,,mk1,mkm^0, m^1, \dots, m^{k-1}, m^k are related in a beautiful way involving the Stirling numbers of the first kind, [1, p. 248]:
mk=i=0k(ki)mi.(13) m^k = \sum_{i=0}^{k} \binom{k}{i} m^i. \qquad (13)
The Stirling numbers (ki)\binom{k}{i} are defined combinatorially as the number of ways to partition a set that contains kk elements into ii non-empty subsets. For k0k \ge 0 and i0i \ge 0, these numbers are determined by the recurrence relation
(ki)=i(k1i)+(k1i1)for k,i>0 \binom{k}{i} = i \binom{k-1}{i} + \binom{k-1}{i-1} \quad \text{for } k, i > 0
together with the initial values (00)=1\binom{0}{0} = 1 and (r0)=(0r)=0\binom{r}{0} = \binom{0}{r} = 0 if r>0r > 0. In our situation, it is sufficient to know that such a formula exists, the exact values of the coefficients do not matter.
Combining equations (12) and (13) we get mk=i=0k(ki)p(i)(1)m^k = \sum_{i=0}^{k} \binom{k}{i} p^{(i)}(1) if p(x)=xmp(x) = x^m. Recalling that we wrote F(x,y)=m=1Ncm(y)xmF(x, y) = \sum_{m=1}^{N} c_m(y)x^m, we now see that
m=1Ncm(y)mk=i=0k(ki)F(i)(y,1)(14) \sum_{m=1}^{N} c_m(y)m^k = \sum_{i=0}^{k} \binom{k}{i} F^{(i)}(y, 1) \quad (14)
where F(i)(y,1)F^{(i)}(y, 1) is the polynomial in yy obtained by setting x=1x = 1 in the ii-th derivative of F(x,y)F(x, y) with respect to xx.
Since we defined F(x,y)=xj=0kfj(x,y)F(x, y) = x \cdot \prod_{j=0}^{k} f_j(x, y), the product rule for derivatives shows that, for iki \le k, F(i)(y,1)F^{(i)}(y, 1) can be written as a sum of products, each having at least one factor of the form fj(1,y)f_j(1, y). Since fj(1,y)=f(y)f_j(1, y) = f(y), as we noted earlier, the polynomial (14) is a multiple of f(y)f(y). In other words
m=1Ncm(y)mk0(modf(y)). \sum_{m=1}^{N} c_m(y)m^k \equiv 0 \pmod{f(y)}.
Because (y1)f(y)=yn1(y-1)f(y) = y^n-1, we can replace yny^n by 1, or more generally, ydy^d by yry^r whenever dr(modn)d \equiv r \pmod{n}, when we work (mod f(y)f(y)). When cm(y)=ydc_m(y) = y^d and 0r<n0 \le r < n is the remainder of dd on division by nn, we let cˉm(y)=yr\bar{c}_m(y) = y^r. We then have m=1Ncˉm(y)mk0(modf(y))\sum_{m=1}^{N} \bar{c}_m(y)m^k \equiv 0 \pmod{f(y)}. This means there exists CZC \in \mathbb{Z} such that
m=1Ncˉm(y)mk=Cf(y)=C(1+y+y2++yn1). \sum_{m=1}^{N} \bar{c}_m(y)m^k = C f(y) = C(1 + y + y^2 + \dots + y^{n-1}).
As we have seen above, cm(y)=yd(m1)c_m(y) = y^{d(m-1)}. Thus, cˉm(y)=yr\bar{c}_m(y) = y^r exactly when d(m1)d(m-1) leaves remainder r[0,n1]r \in [0, n-1] on division by nn and so C=mSimkC = \sum_{m \in S_i} m^k for all i=0,1,,n1i = 0, 1, \dots, n-1.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.