Fundamental theorem of counting

  • Thread starter Saitama
  • Start date
  • #1
3,812
92

Homework Statement


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.


Homework Equations


N/A


The Attempt at a Solution


I don't understand how should i start. :(

Can somebody give me some ideas?
 

Answers and Replies

  • #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!
 
  • #3
VietDao29
Homework Helper
1,423
2

Homework Statement


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.


Homework Equations


N/A


The Attempt at a Solution


I don't understand how should i start. :(

Can somebody give me some ideas?
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.

Regards,
 
  • #4
3,812
92
Hi VietDao29!!
Thanks for the reply!! :)

+ 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?)[/INDENT]
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? :)
 
  • #5
I like Serena
Homework Helper
6,577
176
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:
 
  • #6
3,812
92
Hi ILS!! :smile:

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

Don't you have a few problems that I can actually help you with?
Yes i do have. :)
But just when i finish off with this topic i will post problems on Complex Numbers.

Remember I'm only a poor guy with a limited understanding of math and physics. :shy:
ROFL! :rofl:
The best joke ever.
 
  • #7
I like Serena
Homework Helper
6,577
176
This problem was stated under "Permutations and Combinations" category. There is a chapter too on this topic in my textbook.
Do you have a couple of relevant equations or (names of) methods/theorems then?


ROFL! :rofl:
The best joke ever.
:blushing:
 
  • #8
3,812
92
Do you have a couple of relevant equations or (names of) methods/theorems then?
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.
 
  • #9
I like Serena
Homework Helper
6,577
176
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.
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.
 
  • #10
3,812
92
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.
Yeah its not in that chapter. :)
When i said that this is a problem from my textbook?

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.
So what should be the solution to it?

Btw, i managed to get the answer key. It says the answer is infinitely many. :uhh:
 
  • #11
I like Serena
Homework Helper
6,577
176
Yeah its not in that chapter. :)
When i said that this is a problem from my textbook?
You didn't. ;)



So what should be the solution to it?

Btw, i managed to get the answer key. It says the answer is infinitely many. :uhh:
I just read VietDao29's post more carefully and he effectively gave the solution. :wink:
 
  • #12
3,812
92
I just read VietDao29's post more carefully and he effectively gave the solution. :wink:
And i posted a reply too to the VietDao29's post. :)
 
  • #13
I like Serena
Homework Helper
6,577
176
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]?
 
  • #14
3,812
92
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]?
That's only possible by trial and error method only. :uhh:

Isn't there any simpler way? :)
 
  • #15
I like Serena
Homework Helper
6,577
176
No, not by trial and error.
Just by using algebraic properties of numbers.

Can you rearrange the parentheses in the expression?
 
  • #16
3,812
92
No, not by trial and error.
Just by using algebraic properties of numbers.

Can you rearrange the parentheses in the expression?
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]
 
  • #17
I like Serena
Homework Helper
6,577
176
Aaaaah! :smile:
Do you get it now?
 
  • #18
3,812
92
Aaaaah! :smile:
Do you get it now?
Maybe.
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.
Right..?

But how VietDao29 arrived at this equation? :confused:
 
  • #19
I like Serena
Homework Helper
6,577
176
Maybe.
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.
Right..?
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.



But how VietDao29 arrived at this equation? :confused:
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.
 
  • #20
3,812
92
He realized that if he found one solution he could construct another solution be using exactly this algebraic property.
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:
 
  • #21
I like Serena
Homework Helper
6,577
176
So is the answer infinite? right..?
Well, the solution works for b=1.
It works for b=2, and for b=3, and for b=4, and... for b=10000, and...
How many different solution do you think there are?


But aren't there any steps to VietDao's solution? It would have been too difficult for VietDao to find that solution. :uhh:
Well, he said he used trial and error to find one solution.

I imagine he did something like:
Let's see if I can write [itex]1^3+1^3[/itex] as the sum of two other cubes.
No that's not possible.
Okay, let's try [itex]1^3+2^3[/itex].
Nope again.
Then [itex]1^3+3^3[/itex].
And then [itex]2^3+3^3[/itex].
And then ...
And then ...

It does take some systematic counting, but sooner or later you'd find a solution (if there is one).
And in the process, if you're observant, you might notice some patterns...
 
  • #22
3,812
92
Well, the solution works for b=1.
It works for b=2, and for b=3, and for b=4, and... for b=10000, and...
How many different solution do you think there are?
Infinite. :D

Well, he said he used trial and error to find one solution.

I imagine he did something like:
Let's see if I can write [itex]1^3+1^3[/itex] as the sum of two other cubes.
No that's not possible.
Okay, let's try [itex]1^3+2^3[/itex].
Nope again.
Then [itex]1^3+3^3[/itex].
And then [itex]2^3+3^3[/itex].
And then ...
And then ...

It does take some systematic counting, but sooner or later you'd find a solution (if there is one).
And in the process, if you're observant, you might notice some patterns...
Ok ok, i get it now. :)
I really don't like the trial and error method, that's why i asked on how did he start off with the question? :)
 

Related Threads on Fundamental theorem of counting

  • Last Post
Replies
13
Views
1K
Replies
2
Views
2K
  • Last Post
Replies
1
Views
2K
Replies
13
Views
4K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
745
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
4
Views
463
  • Last Post
Replies
8
Views
3K
Top