Help! Cuboid shapes made from cubes

mantissa · 2007-06-25 05:36:54

My daughter has been set a challenge in 3D!!

Given a number of cubes, how many different sized cuboid shapes can be made. How is this related to the number of cubes used?

OK, so for example given 2 cubes, there is only one arrangement: 1 X 2

with 6 cubes, there can be: 1 X 1 X 6, 2 X 3 X 1
with 49 cubes, there can be: 7 X 7 X 1, 1 X 1 X 49
with 7 cubes, there is only: 1 X 1 X 7
but with 20 cubes, there can be: 1 X 1 X 20, 1 X 2 X 10, 1 X 4 X 5, 2 X 2 X 5

I am really struggling with a relationship between the number of cubes and the number of cuboid arrangements - can anyone help?

It looks to be something to do with factors, or even prime factors, but it doesn't work for all cases.

Thanks in advance

John

Ricky · 2007-06-25 05:45:16

You're right on the money with prime factors, including 1's. But it isn't just that, there is something more going on. Where can you put each prime factor? Well, simply put, you can put a prime factor into any side of the cube. So you have 3 bins to place each prime factor. How many different ways can you place the prime factors? This is a combinatorial problem with a very simple answer. If you don't know much combinatorics, you probably won't get it. But give it a shot, and if you need help, just ask.

But that isn't just it either. Cause for example, if you have 8 cubes, you would be counting 2x2x2 and 2x2x2 as different combinations. When its a prime to a power, you get duplicates involved. These must be removed. But I recommend solving this piece wise, start with the problem above, then we'll move on to removing the duplications.

mantissa · 2007-06-25 06:58:12

wow! That was quick... many thanks

OK, so I am close with the prime factor thing....I'm not sure why this is the case, but I was thinking about factors in general, hit the web and saw the 'reverse division' method for determining prime factors and liked the numbers it was coming up with, so tried it. It worked for most cases, except the one with 6 cubes. I don't have a lot of hair on my head in the first place, so tearing more out in the pursuit of this was not doing my image any good - hence my question here!!

To address your combinatorics point, I am not too concerned about the complete set of possible arrangements, just shape types, so 1 X 2 X 3 is the same as 3 X 2 X 1 as far as I am concerned...

Is there a logical reason why prime factors are the key here, or is it just one of those things?

J

Ricky · 2007-06-25 08:57:14

To address your combinatorics point, I am not too concerned about the complete set of possible arrangements, just shape types, so 1 X 2 X 3 is the same as 3 X 2 X 1 as far as I am concerned...

Yep, and the combinatorics problem that I told you (number of ways to put k balls into n boxes) takes that into account because it doesn't order the boxes.

Is there a logical reason why prime factors are the key here, or is it just one of those things?

Do you know the fundamental theorem of arithmetic? Every positive integer may be expressed as the product of prime powers. So for example, 120 = 2^3 * 3 * 5, where 2, 3, and 5 are the primes and they can be to different powers. Also, by taking the prime factorization, you are breaking numbers up into pieces that can't break down any more. So the question is asking you to find three numbers that when multiplied give you your n, and should be easy to see that each of three numbers, when put together (multiplied), must be composed of exactly the same primes as the whole number itself.

So since that is the case, and you can't split a prime between two different sides (it has no divisors other than 1 and itself), the primes tell you how many ways there is to do this.

mantissa · 2007-06-25 11:35:36

Well, I appreciate your help so far, but my grounding in mathematics is from an engineering perspective rather than a pure maths background. I *didn't* know that all numbers could be expressed as a product of primes, but I can see that now.

I have tried (with 12, 16, 10, 7, 9, 5, 49, & 20 for 'n') deriving the number of prime factors, but they don't add up to the number of cuboid arrangements that I have arrived at empirically.

12 [2, 2, & 3] - 3 prime factors - but 4 cuboid shapes (3x2x2, 1x1x12, 1x2x6, 1x3x4)
16 [2, 2, 2,& 2] - 4 prime factors - and 4 cuboid shapes (4x4x1, 1x1x16, 1x2x8, 2x2x4)
10 [2,5] - 2 prime factors - and 2 cuboid shapes (1x1x10, 1x2x5)

etc etc, but it doesn't work for 12 or 64 for example.

I must be missing something (other than a good mathematics background!)

J

Ricky · 2007-06-26 05:43:18

I have to get to classes right now, so I'll post the answer later on today. But the reason why you're having trouble is that you are looking for a simple relationship between the number of prime factors and the number of combinations. There isn't one. It will involve some combination ( n!/r!(n-r!) ) or permutation ( n!/(n-r)! ) in some way because of the duplications, for example where 2 is a prime factor three times.

Ricky · 2007-06-26 10:37:26

This is a much harder problem than I first imagined. I've come up with several different solutions, all with some fatal flaw.

Avon · 2007-06-28 12:25:01

I have found this to be a nice problem, with what I consider to be a pretty solution.
Let g(n) be the number of cuboids that can be made from n cubes.

Write n as a product of powers of distinct primes, say

Then we have

where

Math Is Fun Forum

#1 2007-06-25 05:36:54

Help! Cuboid shapes made from cubes

#2 2007-06-25 05:45:16

Re: Help! Cuboid shapes made from cubes

#3 2007-06-25 06:58:12

Re: Help! Cuboid shapes made from cubes

#4 2007-06-25 08:57:14

Re: Help! Cuboid shapes made from cubes

#5 2007-06-25 11:35:36

Re: Help! Cuboid shapes made from cubes

#6 2007-06-26 05:43:18

Re: Help! Cuboid shapes made from cubes

#7 2007-06-26 10:37:26

Re: Help! Cuboid shapes made from cubes

#8 2007-06-28 12:25:01

Re: Help! Cuboid shapes made from cubes

Board footer