6
$\begingroup$

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?

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

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.

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$ Sep 13 '21 at 16:15
5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thanks, you have detailed what Calvin Lin said in one sentence. $\endgroup$ Sep 13 '21 at 16:13
  • 2
    $\begingroup$ @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. $\endgroup$
    – Calvin Lin
    Sep 13 '21 at 18:23
4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Sep 12 '21 at 19:49
  • $\begingroup$ @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 )$. $\endgroup$
    – Calvin Lin
    Sep 13 '21 at 18:19
  • $\begingroup$ Thank you. That is great insight! $\endgroup$ Sep 13 '21 at 18:38
1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.