Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Fundamental theorem of counting

  1. Oct 15, 2011 #1
    1. The problem statement, all variables and given/known data
    How many natural numbers are there with the property that they can be expressed as the sum of the cubes of two natural numbers in two different ways.

    2. Relevant equations

    3. The attempt at a solution
    I don't understand how should i start. :(

    Can somebody give me some ideas?
  2. jcsd
  3. Oct 15, 2011 #2
    I would run a few numbers in a table and get a feel for how your numbers would work. What if n = a^3 + b^3 is an even number? What does that say about a and b? Also, your problem sounds like an "or" problem, as in n = a^3 + b^3 or n = c^3 + d^3, where a, b, c, d are distinct.

    Not an expert in combinatorics or discrete math. Just about to graduate to teach high school math. All my books are in boxes, just moved. Good luck!
  4. Oct 15, 2011 #3


    User Avatar
    Homework Helper

    I did this problem by trial-and-error method. So here's how I would start.
    • Firstly is to notice that there can only be two possible answers to this problem:
      + There's no such natural number.
      + If there happens to be some natural number a, which can be expressed as the sum of two cubes in two different ways, then for every natural number b, the number a.b3 should also satisfy the requirement. (Do you know why?)​
    • Then, by trial-and-error method, I found out that [itex]1^3 + 12^3 = 9^3 + 10^3[/itex].

    So, how many natural numbers can satisfy the problem's requirement? Can you go from here?

    I know that trial-and-error method is not a very good way to go. I think there should be some more elegant way to tackle this problem.

  5. Oct 15, 2011 #4
    Hi VietDao29!!
    Thanks for the reply!! :)

    No i don't know why is that. :uhh:

    BTW, i went like this. There are infinitely many natural numbers. So the answer to the question can be infinite. Isn't it? :)
  6. Oct 15, 2011 #5

    I like Serena

    User Avatar
    Homework Helper

    Hmm, I wouldn't know where to start either. :frown:

    You seem to have shifted to upper level university problems in number theory.
    I suspect that on PF there is only a very limited number of people who can help you with stuff like that.
    It is certainly not "Precalculus Mathematics"! :wink:

    Don't you have a few problems that I can actually help you with?
    Remember I'm only a poor guy with a limited understanding of math and physics. :shy:
  7. Oct 15, 2011 #6
    Hi ILS!! :smile:

    What? Is it upper level university problem?
    Lol, i don't really think so. :D
    This problem was stated under "Permutations and Combinations" category. There is a chapter too on this topic in my textbook.

    Yes i do have. :)
    But just when i finish off with this topic i will post problems on Complex Numbers.

    ROFL! :rofl:
    The best joke ever.
  8. Oct 15, 2011 #7

    I like Serena

    User Avatar
    Homework Helper

    Do you have a couple of relevant equations or (names of) methods/theorems then?

  9. Oct 15, 2011 #8
    I don't think we do really need theorems here. Its all about logic.
    Are you talking about those simple formulae like what is nPr and nCr? Yep they are in my textbook and i know what do they mean. Here is the chapter from my textbook.
  10. Oct 15, 2011 #9

    I like Serena

    User Avatar
    Homework Helper

    It wouldn't hurt to mention those may be relevant...

    However, I don't see your current problem mentioned in this chapter.
    And I don't think you can solve it with the information in it.

    I suspect there is less than a handful of solutions for your problem, but I don't think permutations and combinations are going to help you to proof it.

    Probably the best way to go about it, is to simply try and find solutions until you see a pattern that no more solutions can be found.
  11. Oct 15, 2011 #10
    Yeah its not in that chapter. :)
    When i said that this is a problem from my textbook?

    So what should be the solution to it?

    Btw, i managed to get the answer key. It says the answer is infinitely many. :uhh:
  12. Oct 15, 2011 #11

    I like Serena

    User Avatar
    Homework Helper

    You didn't. ;)

    I just read VietDao29's post more carefully and he effectively gave the solution. :wink:
  13. Oct 15, 2011 #12
    And i posted a reply too to the VietDao29's post. :)
  14. Oct 15, 2011 #13

    I like Serena

    User Avatar
    Homework Helper

    VietDao29 gave you a solution: a = 13 + 123 = 1729

    And he claimed that a.b3 would also be a solution for any b.

    [tex]a \cdot b^3 = (1^3 + 12^3) \cdot b^3[/tex]

    Can you find numbers p and q such that [itex]a \cdot b^3 = p^3 + q^3[/itex]?
  15. Oct 15, 2011 #14
    That's only possible by trial and error method only. :uhh:

    Isn't there any simpler way? :)
  16. Oct 15, 2011 #15

    I like Serena

    User Avatar
    Homework Helper

    No, not by trial and error.
    Just by using algebraic properties of numbers.

    Can you rearrange the parentheses in the expression?
  17. Oct 15, 2011 #16
    Are you talking about this expression?
    [tex]a \cdot b^3 = (1^3 + 12^3) \cdot b^3[/tex]

    If yes, what i can do is:-
    [tex]a \cdot b^3 = (1 \cdot b)^3+(12 \cdot b)^3[/tex]
  18. Oct 15, 2011 #17

    I like Serena

    User Avatar
    Homework Helper

    Aaaaah! :smile:
    Do you get it now?
  19. Oct 15, 2011 #18
    If i put a value for b in 1b , then it is the value for p and if i put the value of b in 12b then its for q.

    But how VietDao29 arrived at this equation? :confused:
  20. Oct 15, 2011 #19

    I like Serena

    User Avatar
    Homework Helper

    Yes, so for any b we find that the number n given by:
    [tex]n = 1729 \cdot b^3 = (1 \cdot b)^3 + (12 \cdot b)^3 = (9 \cdot b)^3 + (10 \cdot b)^3[/tex]
    is a solution.

    He realized that if he found one solution he could construct another solution by using exactly this algebraic property.
    I don't really know what inspired him.
    Probably trial and error combined with some experience.
  21. Oct 15, 2011 #20
    So is the answer infinite? right..?

    But aren't there any steps to VietDao's solution? It would have been too difficult for VietDao to find that solution. :uhh:
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook