0
$\begingroup$

This is a problem from Discrete Mathematics and its Applications enter image description here

Here is my work so far enter image description here

It's similar to this other question I had Next step to take to reach the contradiction?.

I am assuming that I what I am trying to prove is false, that is there is a positive perfect cube less than 1000 that is the sum of the cubes of two positive integers. From here I need to take logical steps to show that assuming that what I am trying to prove is false leads to a contradiction(false no matter what is passed in).

The first algebraic step I took was saying that if s^3 < 1000, cubing root both sides, s < 10. The next logical step i took was saying that if a^3 + b ^3 = s ^ 3, a^3 + b^3 < 1000 as well. If a ^ 3 + b ^ 3 < 1000, I implied that a ^ 3 < 1000 and b ^ 3 < 1000 because if either component >= 1000, the result will also be >= 1000. Going off of that, repeating(recursion) the step I did for s^3 < 1000. I got that b < 10 and a < 10.

In the end i have three intervals 0 < s < 10, 0 < a < 10, and 0 < b < 10. I don't where to go from here though. I think it be too brute force to test every s from 1 to 9 and showing that there is no a^3 and b^3 that will add to it.

What's the next step I should take to reach the contradiction that would be more efficient/not as exhaustive?

$\endgroup$
  • $\begingroup$ The number of cases is small, and one can use shortcuts. "Brute force" is not at all brutal. $\endgroup$ – André Nicolas Jan 22 '15 at 2:27
  • $\begingroup$ Thanks for disclosing the course that you're taking; it helps provide good answers. Textbooks are usually named with their authors since their titles are so similar. Is that Ensley and Cawley's book? $\endgroup$ – Matthew Leingang Jan 22 '15 at 2:28
  • $\begingroup$ think so McGraw Hill? $\endgroup$ – committedandroider Jan 22 '15 at 21:35
1
$\begingroup$

An analytic proof is probably beyond the scope of your discrete math course. I suspect brute force is the intended approach from here.

$\endgroup$
  • $\begingroup$ but for this you would still have to check (9,8), (9,7), ....(9,1), (8,8),...(8,1), all the way down to (1,1) which i think is too many cases... $\endgroup$ – committedandroider Jan 22 '15 at 21:37
0
$\begingroup$

As M. Leingang says, this is likely intended to be a brute force problem. But there are ways to pare the solution set down.

For instance, note that if $a$ and $b$ are both even or both odd, then $s$ must be even, and must be odd otherwise. Also note that we can interchange $a$ and $b$ without loss of generality, so we only need to check for $a \leq b$. These two facts alone should make the problem very manageable.

$\endgroup$
  • $\begingroup$ can you say change interchange a and b without loss of generality because a^3 + b^3 is the same as b^3 + a ^3? $\endgroup$ – committedandroider Jan 22 '15 at 21:29
  • $\begingroup$ Yes, exactly. Once you have checked e.g. $3^3 + 5^3$ there is no need to check $5^3 + 3^3$. $\endgroup$ – Michael Cromer Jan 22 '15 at 21:34
  • $\begingroup$ but for this you would still have to check (9,8), (9,7), ....(9,1), (8,8),...(8,1), all the way down to (1,1) which i think is too many cases... $\endgroup$ – committedandroider Jan 22 '15 at 21:36
  • $\begingroup$ It is 45 cases. But even $9^3 + 8^3 = 1241 > 1000$, so you can discard some anyway - I count 41 valid cases. Just write down a list of these 41 numbers, then a list of the nine cubes $1^3, \ldots, 9^3$ - 50 numbers in all. If these two lists do not have any numbers in common, you have proved it. $\endgroup$ – Michael Cromer Jan 22 '15 at 21:51
  • $\begingroup$ I feel like the question is supposed to get you to leverage proof by cases which is what you mentioned to get less than 10 cases like all the other problems. I feel like even 41 valid cases is too many to consider. $\endgroup$ – committedandroider Jan 22 '15 at 21:53
0
$\begingroup$

List the cubes less than 1000. There are only 9 of them. Now if $a^3+b^3 = 1000$, then of course $a^3 = 1000-b^3$ and so you only have to check 10 cases, one for each $b$, seeing whether $1000-b^3$ is in your list or not. This would take no more than 1 minute if you already have the list.

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