For which positive integers is it possible to split the set of integers that satisfy into 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 this is obviously possible. We will show that this is possible for all integers by proving a more general version using induction. The number 2021 will be replaced by an integer 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 .
To formulate this more general statement, we first introduce some notation. When are two integers, we denote by the set of integers that satisfy . When and we let be the digit sum of the base representation of . Given two integers, and , let . For we define subsets of as follows
We also let be the set obtained by shifting by the integer . Finally, for we define
Here, even when , we agree that . We now fix an integer . Theorem. For all integers satisfying and we have
Remark. Setting and solves the original problem.
Proof. We do induction on . We keep fixed throughout the proof. The base case, , is trivially true, because the only possible value for is zero, and so is the number of elements in . Let us now fix and suppose that the statement of the theorem holds true when is replaced by . To avoid confusion, we denote the sets that correspond to by :
where . Accordingly, we define and . The base representation of the numbers in is obtained from those of the numbers in by prepending digits . Because for and , we see that
Here we consider the subscripts modulo . As we assume for that does not depend on , we immediately get that does not depend on , as long as .
We are left to prove that does not depend on . Using (11) we obtain
We now expand the expressions using the binomial theorem. What we obtain is of the form where each coefficient is a product of a binomial coefficient and a power of . The exact values of these coefficients are not relevant here, but it is important that they are the same for all . Therefore,
By inductive assumption, no term that comes with a coefficient depends on . Therefore,
and this does not depend on and the proof is complete. The last equality comes from
and because we considered subscripts modulo .
Solution 2
Solution 2. We will again replace 2021 by an integer . This solution takes a more structured approach using polynomials. Like in Solution 1, we denote by the set of integers that satisfy , where are two given integers. When and we let be the digit sum of the base representation of . Given any two integers, and , we let and for we define subsets of as follows
We are going to prove that for any two integers, and ,
Define and let for . We consider the polynomial and we think of as a polynomial in that has coefficients which are polynomials in . Note that setting gives for all . This will be of importance towards the end of the argument.
When we multiply out completely the product that defines , we obtain an expression of the form
with coefficients being polynomials in . The exponents of that appear in are and the coefficient in front of is . Therefore, where is the digit sum of the base representation of .
Differentiating with respect to gives . When we differentiate times, we get . This is conveniently written using the falling factorial power notation (see for example [1, p. 47])
which allows us to write for the -th derivative of . This holds true even if , because then both sides are equal to zero. Substituting we obtain
Usual powers and the falling powers are related in a beautiful way involving the Stirling numbers of the first kind, [1, p. 248]:
The Stirling numbers are defined combinatorially as the number of ways to partition a set that contains elements into non-empty subsets. For and , these numbers are determined by the recurrence relation
together with the initial values and if . 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 if . Recalling that we wrote , we now see that
where is the polynomial in obtained by setting in the -th derivative of with respect to .
Since we defined , the product rule for derivatives shows that, for , can be written as a sum of products, each having at least one factor of the form . Since , as we noted earlier, the polynomial (14) is a multiple of . In other words
Because , we can replace by 1, or more generally, by whenever , when we work (mod ). When and is the remainder of on division by , we let . We then have . This means there exists such that
As we have seen above, . Thus, exactly when leaves remainder on division by and so for all .