what is the least # of boxes that will hold exactly 300 cu m of sand.

**bigwave** · January 9th 2011, 04:53 PM

the supply of boxes is in volumes of $1, 3, 9, 27,$ and $81, m^3$
Given that the boxes must be filled completely, what is the least number of boxes that will hold exactly 300 cubic meters of sand?

I tried just guessing thru this but there must be method of deriving it.

$ 300-([3]\times81)=243\rightarrow300-243=57\rightarrow57-([2]\times27)=1\rightarrow[1]-1=0 $
so $3+2+1 = \boxed{6}$ boxes

**melese** · January 9th 2011, 05:24 PM

If I understand correctly the volume values are powers of 3...
I've found a way to fill completely a fewer number of boxes. My motive is to consider at each stage the largest power of 3, subtract it, and then do the same with the remainder.
So, $300=\boxed1\cdot243+57$ ; $57=\boxed2\cdot27+3$ ; $3=\boxed1\cdot3$ . Therefore $1+2+1=5$ boxes are enough.

The goal, I believe, is to subtract large number as possible in order to keep to the number of boxes low.
I think that this is similiar to what you did.

**CaptainBlack** · January 10th 2011, 04:55 AM

Originally Posted by bigwave

the supply of boxes is in volumes of $1, 3, 9, 27,$ and $81, m^3$
Given that the boxes must be filled completely, what is the least number of boxes that will hold exactly 300 cubic meters of sand?

I tried just guessing thru this but there must be method of deriving it.

$ 300-([3]\times81)=243\rightarrow300-243=57\rightarrow57-([2]\times27)=1\rightarrow[1]-1=0 $
so $3+2+1 = \boxed{6}$ boxes

The greedy algorithm will generate a solution for this with a minimum number of boxes.

CB

**emakarov** · January 10th 2011, 05:39 AM

If boxes in all powers of 3 are available, then the problem is writing the given number to the base 3. For example, $300=102010_3$ . The number of boxes then is the sum of digits.

**bigwave** · January 14th 2011, 01:33 PM

Originally Posted by CaptainBlack

The greedy algorithm will generate a solution for this with a minimum number of boxes.

CB

what is a "greedy algorithm"

**bigwave** · January 14th 2011, 01:36 PM

Originally Posted by emakarov

If boxes in all powers of 3 are available, then the problem is writing the given number to the base 3. For example, $300=102010_3$ . The number of boxes then is the sum of digits.

so by this the answer is 6 that is by sum you mean how many digits?

**emakarov** · January 14th 2011, 01:38 PM

The sum of digits in 102010 is 1 + 0 + 2 + 0 + 1 + 0 = 4.

**bigwave** · January 14th 2011, 01:46 PM

ok, but how do you know which 4 boxes are used.

**snowtea** · January 14th 2011, 02:09 PM

I think you mean $3^m$ and not $m^3$ .

Originally Posted by bigwave

what is a "greedy algorithm"

The greedy algorithm is to stuff the largest box possible into the remaining volume.
So for a volume of 300.
Largest box possible is 3^5 = 243.
Volume remaining is 300 - 243 = 57.
Largest box possible is 3^3 = 27.
Volume remaining is 57 - 27 = 30.
...

You continue this until you get 0. This always works because you have the unit volume 1^3 = 1.
You should get the same answer that emakarov hinted at.

This is optimal because the numbers are powers of 3. You can use a proof by contradiction. To get intuition think about making change with coins. How do you make change with the minimum number of coins? For most currencies the greedy algorithm gives the least number of coins because when you have too many smaller coins they normally can be combined into a larger coin.
Similarly if you have 3 boxes of volume 3^2, then you could've just used 1 box of volume 3^3.

**snowtea** · January 14th 2011, 02:15 PM

*side note*
In general, if you did not have nice numbers like powers of 3...
This is the bin packing problem which is NP-complete.
This means to find the minimum number of boxes, you probably can't do much better than just to consider all possibilities.

**orange gold** · January 15th 2011, 04:12 PM

The boxes must be completely filled?
To get the minimum number you would have to start from the biggest boxes and use as many as you can to logically find a minimum.
3x 81 boxes will do, 4x 81 boxes goes over 300.
now we have 243 filled and 57 left to go.
2x 27 boxes is just under 57. 3x 27 boxes goes over so we have to move onto the next largest box.
we now have 293 filled and 57 left to go.
1x 9 box goes over so we have 0x 9 boxes and we have to go onto the next largest.
1x 3 box fills us up to 300 exactly, all boxes use are filled to the top.
$ \boxed{81}+\boxed{81}+\boxed{81}+\boxed{27}+\boxed {27}+\boxed{3} $
6 boxes is the answer. Just remember to work from the max number of biggest boxes to smaller boxes and you will get your minimum.

I was confused by everyone elses answers because they seemed to use boxes bigger than 81 meters cubed, which seemed to be the max box size you gave?

**CaptainBlack** · January 16th 2011, 02:09 AM

Originally Posted by snowtea

*side note*
In general, if you did not have nice numbers like powers of 3...
This is the bin packing problem which is NP-complete.
This means to find the minimum number of boxes, you probably can't do much better than just to consider all possibilities.

It is sufficient that the size of boxes increase sufficiently fast (and I am not going to check the necessary condition at this time) for the greedy algorithm to be optimal, but sizes that are powers of some integer >1 will in general be OK. Though that does not guarantee that you will not have a part filled box or some filling left over.

CB

**snowtea** · January 16th 2011, 06:22 AM

Originally Posted by CaptainBlack

It is sufficient that the size of boxes increase sufficiently fast (and I am not going to check the necessary condition at this time) for the greedy algorithm to be optimal, but sizes that are powers of some integer >1 will in general be OK. Though that does not guarantee that you will not have a part filled box or some filling left over.

CB

Yeah, CB you are right. I was just making a remark. Not challenging your observation.

I have proved before that a greedy algorithm is always optimal with the bin sizes $a_0 < a_1 < a_2 < ...$
if $a_0 = 1$ , and $a_n = \sum_{i=0}^{n-1} k_ia_i$ for some natural numbers $k_i$ and $k_{n-1} > 0$ .

If you think about it, this condition works for powers of numbers > 1, and also for most currency.

Thread: what is the least # of boxes that will hold exactly 300 cu m of sand.

LinkBack

Thread Tools

Display

what is the least # of boxes that will hold exactly 300 cu m of sand.

Similar Math Help Forum Discussions

Tide removing sand from a beach

1 ) Sand dunes on a desert island move as sand is swept up the windward side to settl

sand problem

Sand Moisture Problem

Volume of Sand in a Pyramid

Search Tags