5
$\begingroup$

This is something from Rosen's Discrete Math Textbook that was left for the reader to verify. I tried to prove it but I'm stuck:

I understand that the 4th powers of integers are: $0^{4} = 0, 1^{4} = 1, 2^{4} = 16, 3^{4} = 81, \dots$ and so on. I also understand repetition is allowed here.

So since $3^{4} > 79$, we really can only use $0^{4} = 0, 1^{4} = 1$, and $2^{4} = 16$ to create our sum of 18 4th powers that add to 79.

Hence we have the following equations/inequalities:

$x + 16y = 79$ (where x is number of 1's to 4th power and y is number of 2's to 4th power)

$0 \leq x + y \leq 18$ (since we can have 4th powers of 0's taking up some of the 18 spots)

$0 \leq y \leq 4$ (since at least 5 4th powers of 2 would be $ \geq 80 > 79$)

$0 \leq x \leq 18$ (18 spots for 4th powers of 1's)

Not sure how to proceed from here. I mean I graphed on desmos to see that the line $x + 16y = 79$ doesn't lie in the region of intersection of the inequalities. So there really is no solution that fits these restrictions, let alone an integer one.

However, is there a better way to prove this? I feel if the author left it for the reader to verify themselves it should be much simpler than this. Kindly please do help me here.

$\endgroup$
1

5 Answers 5

8
$\begingroup$

You have $18$ terms. They can only be $0,1,$ or $16$. And $5\times 16 > 79$ you can only have at most four $16$.

If you have four $16$s those add up to $64$. Then you have $14$ remaining terms that must be $0$ or $1$. At most those add up to $14$ so the highest you can add up is $64 + 14=78$. Not enough.

And if you have fewer than four $16$s it's obviously worse!

If you want to be thorough and precise.

Let $n$ be the number of $16$s involved. And $k$ the number of $1$s. And $r= (18 - n -k)\ge 0$ be the number of zeros.

You have the sum $16n + k+ 0\cdot r= 16n + k$. But we can note that $n + k + r=18$ and so $k= 18 - n - r \le 18 - n$.

If $n \ge 5$ then $16n + k \ge 16n \ge 16\cdot 5 = 80 > 79$ and the sum is impossible with $5$ or more $16$s.

If $n \le 4$ then $16n + k \le 16\cdot 4 + k = 64 +k$. Is there any restriction on $k$? $k=18-n-r \le 18 - n$ so $16n + k \le 16n + (18-n)= 15n + 18\le 15\cdot 4 + 18=78 < 79$. So the sum is impossible with $4$ or fewer $16$s.

That's all.

$\endgroup$
3
  • $\begingroup$ Tysm for the answer! Just to be clear though, $(18 - n - k) \geq 0$ because $(n + k) \leq 18$, therefore we can say that $k = 18 − n − (18 − n − k) \leq (18 − n)$, correct? $\endgroup$
    – Bob Marley
    Commented May 26 at 16:13
  • $\begingroup$ It might have been easier for me to introduce and $r =$ number of $0$s and so $n+k+r = 18$ and $r \ge 0$ and $k = (18-n) -r \le 18-n$. That might have made the argument less like spinning cotton candy out of nothing. But I didn't want to introduce $r$ because it is completely superfluous. $\endgroup$
    – fleablood
    Commented May 26 at 17:01
  • $\begingroup$ Nice answer (+1)! A way to rewrite your argument using $g(4)=19$ (because then it is generalizable to bigger numbers) is to say $16n+k=79$ and $n+k+r=19$ so that $15n-r=60$ and hence $r=0$ or $r=15$, but the later case is absurd! $\endgroup$ Commented May 30 at 5:59
4
$\begingroup$

It's a pigeonhole problem. First off, $79<3^4=81$ so the only eligible addends are $0,1,16$. Then to achieve the right residue $\bmod 16$, fifteen of the eighteen terms must be $1$. That leaves only three terms that could be $0$ or $16$, but four $16$ terms would have been needed with the fifteen $1$'s for the sum to reach $79$.

$\endgroup$
6
  • $\begingroup$ Wait wdym by "right residue". I agree 79 mod 16 is 15, but why does that mean we necessarily need 15 ones? $\endgroup$
    – Bob Marley
    Commented May 26 at 1:17
  • $\begingroup$ @BobMarley $79 = 4\times 2^4 +15\times 1^4 $ $= 3 \times 2^4+31 \times 1^4 $ $= 2\times 2^4+47 \times 1^4$ $=1\times 2^4+63\times 1^4 $ $= 79 \times 1^4$ so you need at least $19$ fourth powers as fourth powers of $0$ can only add to these possibilities and fourth powers of $-1$ or $-2$ can only substitute, $\endgroup$
    – Henry
    Commented May 26 at 2:02
  • $\begingroup$ @Henry I'm still not understanding. Also, what do you mean by "as fourth powers of 0 can only add to these possibilities and fourth powers of −1 or −2 can only substitute"? $\endgroup$
    – Bob Marley
    Commented May 26 at 2:17
  • $\begingroup$ @BobMarley $4\times 2^4 +15\times 1^4$ has $19$ fourth powers. $4\times 2^4 +15\times 1^4+5\times 0^4$ has $24$ as an example of including fourth powers of $0$ adding to the number of fourth powers. $3\times 2^4+ 1\times (-2)^4 + 8 \times 1^4+7\times (-1)^4$ has $19$ again as an example of including fourth powers of $-1$ and $-2$ substituting and not changing the number of fourth powers. $\endgroup$
    – Henry
    Commented May 26 at 8:22
  • $\begingroup$ Could you explain where the pigeonhole comes into play? $\endgroup$ Commented May 26 at 23:44
3
$\begingroup$

The region where all the inequalities are true is a significant object. Your solution method is simply a graphical representation of a completely valid approach.

I don't know if that's what Rosen was hoping for, but I think it shows good insight into the problem. Congratulations!

Let's try doing it algebraically instead of graphically. But we can take a hint from the graph: the closest point of the region to the line $x+16y=79$ is the one at the intersection of the lines $y=4$ and $x+y=18,$ the point $(14,4).$ That is, when you apply the inequalities $y\leq 4$ and $x+y\leq 18$ you get a region with this vertex and lying between two rays starting at that vertex. That region is shaded in the figure below.

enter image description here

It is significant that $x+16y=79$ is the equation of a straight line, because that ensures us that the trends we see at the edges of this diagram -- the line is getting farther from the shaded region as you go to the left or go to the right -- will never be reversed, no matter how far out we look, and therefore nothing in the shaded region can ever be closer to the line $x+16y=79$ than the vertex $(14,4)$ is. The remaining inequalities eliminate most of the region between those rays, but the points they eliminate are already far from the line $x+16y=79.$

This suggests (graphically!) that we just need to consider the inequalities $y\leq 4$ and $x+y\leq 18$ and do not need to use any other inequalities in a proof. For some points in the shaded region, the other inequalities will give additional reasons why those points cannot be solutions of the original problem, but we already have enough reasons just by considering what's shown in the graph above.

So let $(x,y)$ be any point for which the inequalities are all true. We have $y \leq 4$ and $x+y\leq 18,$ so $$x + 16y = (x + y) + 15y \leq 18 + 15\cdot4 = 78 < 79.$$ Therefore it is not possible that $x + 16y = 79.$

$\endgroup$
4
  • $\begingroup$ Thank you so much for the answer! I understand how choosing just inequalities $y \leq 4$ and $x + y \leq 18$ gives the result you proved. However, I'm not understanding why the closest point of (14,4) hints at us to just focus on those 2 inequalities. I just want to understand that particular insight of yours! Once again tysm for the answer, truly was very helpful! $\endgroup$
    – Bob Marley
    Commented May 26 at 15:17
  • $\begingroup$ "Since 𝑥 + 16𝑦 = 79 is the equation of a straight line, nothing in that region can ever be closer to that line than that vertex is (this should be obvious from a graph)." Sorry I'm not understand that part. Kindly could you help clarify. $\endgroup$
    – Bob Marley
    Commented May 26 at 16:04
  • $\begingroup$ Also I'm not fully seeing why just because the inequalities 𝑦 ≤ 4 and 𝑥 + 𝑦 ≤ 18 give us the closest point (14, 4) to the line x + 16y = 79 means we don't need to consider any other inequalities. Kindly please help explain $\endgroup$
    – Bob Marley
    Commented May 26 at 16:06
  • $\begingroup$ @BobMarley Adding more inequalities to the mix just makes it less possible solutions, can't become more. So if it's impossible with just these two inequalities, it won't become possible if you add more ones in. $\endgroup$ Commented May 26 at 23:46
3
$\begingroup$

This answer is motivated by the back and forth comments between me and the original poster, following the posted question. I am trying to clarify my analysis. While a valid proof my well be available through a $~\pmod{16}~$ argument, no such approach is necessary.

In order to try to find a satisfying collection of $~18~$ terms, where each term is an element of $~\{0,1,16\},~$ let $~k~$ denote the number of $~16~$ terms that are used. Since $~(5 \times 16) > 79,~$ you must have that $~k \in \{0,1,2,3,4\}.~$

So, assume that exactly $~k~$ terms of $~16~$ are used. Then, you must use the remaining $~(18 - k)~$ terms from the subset $~\{0,1\},~$ to fill the gap of $~[ ~79 - (16 \times k) ~].$

Since the largest element in the subset $~\{0,1\},~$ is the element $~1,~$ the maximum sum that can be achieved by the $~(18 - k)~$ terms is $~(18 - k).~$

Therefore, in order to find a valid solution, you must find some value of $~k~$ in $~\{0,1,2,3,4\},~$ such that it is not the case that

$$[ ~79 - (16 \times k) ~] > (18 - k). \tag1 $$

However, the inequality in (1) above holds when $~k = 4.~$

That is, when $~k = 4,~$ the LHS is 1 greater than the RHS.

Further, you have the pattern that :

  • When $~k = 3,~$ the LHS is 16 greater than the RHS.
  • When $~k = 2,~$ the LHS is 31 greater than the RHS.
  • When $~k = 1,~$ the LHS is 46 greater than the RHS.
  • When $~k = 0,~$ the LHS is 61 greater than the RHS.

So, at each point, as $~k~$ goes to $~(k-1),~$ the difference between the LHS - RHS increases by $~15.~$ This is because at each step, you are adding $~16~$ to the LHS, and only adding $~1~$ to the RHS.

So, you can conclude that since the inequality in (1) above persisted (barely) at $~k = 4,~$ the inequality must also persist for each $~k~$ in $~\{0,1,2,3\}.~$

So, you can conclude, without actually examining the inequality for the various values of $~k \in \{0,1,2,3\},~$ that the closest that the inequality in (1) above will come to not being true will be when $~k = 4.~$

Another way of saying the same thing is that, given the goal of having the inequality in (1) above fail, the optimal value for $~k~$ in trying to achieve this goal must be $~k = 4.$

$\endgroup$
5
  • $\begingroup$ Tysm for the detailed and through answer! I truly appreciate it, and I think I understand your analysis much better now! I guess the key thing I took away was the best casework for this problem so far seems to be considering the mutually exclusive cases of "exactly one 16's, ..., exactly four 16's". $\endgroup$
    – Bob Marley
    Commented May 26 at 15:33
  • $\begingroup$ Just one part I'm a bit nit-picky on is when you said "given the goal of having the inequality in (1) above fail, the optimal value for 𝑘 in trying to achieve this goal must be 𝑘 = 4." Why is k = 4 "optimal"? $\endgroup$
    – Bob Marley
    Commented May 26 at 15:34
  • $\begingroup$ @BobMarley Because my analysis proves that if the inequality in (1) above is true for $~k = 4,~$ then it must be true for any $~k < 4.~$ In fact, that was the whole point of this answer; that once you realized that $~k = 4~$ failed, analysis proves that the problem is solved. $\endgroup$ Commented May 26 at 15:49
  • $\begingroup$ to be clear by analysis you mean the part where you show for each smaller k (by difference of 1), the difference between LHS and RHS increases by 15 each time? $\endgroup$
    – Bob Marley
    Commented May 26 at 15:57
  • 1
    $\begingroup$ @BobMarley Yes, exactly. $\endgroup$ Commented May 26 at 16:07
1
$\begingroup$

You already have good answers, let me just summarize what I wrote in comments, i.e. how to finish the problem from what you found.

Going from your own work and applying mod $16$ to $x + 16y = 79$, we obtain $x\equiv 15\pmod {16}$, i.e. $x=15,31,47,\dots$. Next we use your other inequalities $0\leq x \leq 18$ to conclude $x=15$. Again from $x + 16y = 79$, we get $y=4$. Hence $x+y=19$ and using last of your inequalities $x+y\leq 18$ we reach a contradiction, hence there is no solution.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .