Combinatorics using averages

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

This answer was written to give you another tricky approach. It may help you for expanding your perspective.

Lets use generating functions.

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$

Answer 4

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$.