# Combinatorics using averages

How many solutions exist for $$x+2y+4z=100$$ in non-negative integers?

The author, Martin Erickson, in his book, Aha! Solutions, published by MAA, gives the following brief solution :

There are $$26$$ choices for $$z$$, namely, all integers from $$0$$ to $$25$$. Among these choices, the average value of $$4z$$ is $$50$$. So, on average, $$x+2y=50$$. In this equation, there are $$26$$ choices for $$y$$, namely, all integers from $$0$$ to $$25$$. The value of $$x$$ is determined by the value of $$y$$. Hence, altogether there are $$26^2=676$$ solutions to the original equation.

Can somebody explain to me why this mindblowing solution works using averages?

• Just because you got the numerical answer, doesn't necessarily mean that the solution must have a correct reasoning. Sep 12 '21 at 19:23
• @CalvinLin Is there no reasonable explanation for given solution? Sep 12 '21 at 19:26
• I didn't say that. There could be. But this requires more of an explanation/details than just what i written. Sep 12 '21 at 19:27
• @CalvinLin Unfortunately the author gives only this much solution to above problem. Sep 12 '21 at 19:28

There are $$26$$ choices for $$z$$ in $$\{0,1,\ldots,25\}$$.

Given $$z$$, we have $$x+2y=100-4z$$, which leaves $$\frac{1}{2}(100-4z)+1=51-2z$$ choices for $$y$$ in $$\{0,1,\ldots,\frac{1}{2}(100-4z)\}$$. Having fixed $$y$$, we must have $$x=100-4z-2y$$.

The total number of solutions is therefore $$\sum_{z=0}^{25} (51-2z) = 1 + 3 + \cdots + 49 + 51.$$ Note that the average value of the addends here is $$26$$. Because the addends form an arithmetic sequence, you can replace the addends with $$26$$ via $$1 + 3 + \cdots + 49 + 51 = 26 + 26 + \cdots + 26 + 26 = 26 \cdot 26.$$ This can be seen by noting that $$1+51=26+26$$ and $$3 + 49 = 26 + 26$$, and so on.

Although the solution in the book is correct, it omits justification of several steps.

• Thank you for your explanation. It seems ultimately it boils down to what are the coefficients of the equation, $1,2,4$ and their relation with the sum , $100$. Sep 13 '21 at 16:15

Consider the cartesian product $$S=\{0,1,\ldots, 50\}\times\{0,1,\ldots, 25\}$$, which represents choosing $$y$$ to be at most $$50$$, and $$z$$ to be at most $$25$$. We call elements of $$S$$ solutions, though they may not actually give solutions to the equation. We say $$(y,z)\in P$$ is valid if $$2y+4z\leq 100$$, since we can then choose $$x$$ to be $$100-2y-4z$$, and invalid otherwise. I'll show a way to match invalid solutions with valid ones. If $$(y,z)$$ is an invalid solution, then $$(50-y, 25-z)$$ is a valid solution. This is because $$\color{red}{2y+4z}+\color{blue}{2(50-y)+4(25-z)}=200$$, so if one of the two colored terms is greater than $$100$$, the other is less than $$100$$. Two invalid solutions are never matched this way, and if two valid solutions are matched this way, it's because $$2y+4z=100$$. There are $$26$$ solutions for which this can occur.

Hence, there are $$51\cdot 26$$ solutions in $$S$$. Of these, $$26$$ of these solutions are valid and are matched with another valid solution. All other $$51\cdot 26-26$$ solutions can be grouped into pairs, consisting of one valid solution, and one invalid one. Hence, the number of valid solutions is $$\frac{51\cdot 26-26}{2}+26=26\cdot 26$$.

• Thanks, you have detailed what Calvin Lin said in one sentence. Sep 13 '21 at 16:13
• @MyMolecules this is distinct from my solution. It's a great solution IMO. However, it doesn't truly convey the "average value of 4z" in the original solution. $\quad$ Kevin, you can modify this slightly to solve for $2y+4 + 2 (51-y)+4(25-z ) = 202$ which allows for a bijection of valid and invalid solutions. Sep 13 '21 at 18:23

Claim: The number of solutions to $$x + 2y = 50-2k$$ plus the number of solutions to $$x + 2y = 50+2k$$ is the constant 52.

We can prove this via counting: The number of solutions to $$x + 2y = K$$ is $$\lfloor \frac{K}{2} \rfloor + 1$$.

IMO the "on average" part is dubious. I don't see this as an "Aha!" solution, unless there's more of an explanation like that above.

• So essentially the author is taking the advantage of coefficients, $1,2,4$? If the coefficients were say $1,2,3$ in the equation, ($3$ being coprime to $100$), then the method using averages would fail? Sep 12 '21 at 19:49
• @MyMolecules The main coefficient we are using is the "1". I believe this extends to solving $x + Ay + Bz = k$ (but should still check through the details). EG For $x+2y+3z = 100$, because we're studying $x+2y = 1, 4, \ldots 97$, the number of solutions to $x+2y=49 \pm 3k$ is $\lfloor (49 - 3k) / 3 \rfloor + \lfloor (49+3k) / 3 \rfloor + 2 = 34$, which is the same as $2\times ( \lfloor (49) / 3 \rfloor + 1 )$. Sep 13 '21 at 18:19
• Thank you. That is great insight! Sep 13 '21 at 18:38

Generating function for $$x$$ is equal to $$\frac{1}{1-x}= x^0 +x + x^2 +x^3+...$$
Generating function for $$2y$$ is equal to $$\frac{1}{1-x^2}= x^0 +x^2 +x^4+..$$
Generating function for $$4z$$ is equal to $$\frac{1}{1-x^4}= x^0 +x^4 +x^8+..$$
Then find the coefficient of $$x^{100}$$ in the expansion of $$\frac{1}{1-x} \times \frac{1}{1-x^2} \times \frac{1}{1-x^4}$$ such that https://www.wolframalpha.com/input/?i=expanded+form+of+%281+%2F+%281-x%29%29%281+%2F+%281-x%5E2%29%29%281+%2F+%281-x%5E4%29%29
So , answer is $$676$$