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$ Commented Sep 12, 2021 at 19:23
  • $\begingroup$ @CalvinLin Is there no reasonable explanation for given solution? $\endgroup$ Commented Sep 12, 2021 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$ Commented Sep 12, 2021 at 19:27
  • $\begingroup$ @CalvinLin Unfortunately the author gives only this much solution to above problem. $\endgroup$ Commented Sep 12, 2021 at 19:28

4 Answers 4

Reset to default
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$ Commented Sep 13, 2021 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$ Commented Sep 13, 2021 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$ Commented Sep 13, 2021 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$ Commented Sep 12, 2021 at 19:49
  • 1
    $\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$ Commented Sep 13, 2021 at 18:19
  • $\begingroup$ Thank you. That is great insight! $\endgroup$ Commented Sep 13, 2021 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$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.