Results 1 to 13 of 13

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

  1. #1
    Super Member bigwave's Avatar
    Joined
    Nov 2009
    From
    honolulu
    Posts
    580

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

    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.

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


    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by bigwave View Post
    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.

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


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

    CB
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member bigwave's Avatar
    Joined
    Nov 2009
    From
    honolulu
    Posts
    580
    Quote Originally Posted by CaptainBlack View Post
    The greedy algorithm will generate a solution for this with a minimum number of boxes.

    CB
    what is a "greedy algorithm"
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member bigwave's Avatar
    Joined
    Nov 2009
    From
    honolulu
    Posts
    580
    Quote Originally Posted by emakarov View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    The sum of digits in 102010 is 1 + 0 + 2 + 0 + 1 + 0 = 4.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member bigwave's Avatar
    Joined
    Nov 2009
    From
    honolulu
    Posts
    580
    ok, but how do you know which 4 boxes are used.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    I think you mean 3^m and not m^3.

    Quote Originally Posted by bigwave View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    *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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Nov 2009
    Posts
    37
    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.
    <br />
\boxed{81}+\boxed{81}+\boxed{81}+\boxed{27}+\boxed  {27}+\boxed{3}<br />
    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?
    Last edited by orange gold; January 15th 2011 at 04:27 PM.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by snowtea View Post
    *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
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    Quote Originally Posted by CaptainBlack View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Tide removing sand from a beach
    Posted in the Calculus Forum
    Replies: 2
    Last Post: January 23rd 2011, 05:09 PM
  2. Replies: 1
    Last Post: November 8th 2010, 08:35 AM
  3. sand problem
    Posted in the Calculus Forum
    Replies: 1
    Last Post: February 27th 2010, 04:26 PM
  4. Sand Moisture Problem
    Posted in the Algebra Forum
    Replies: 4
    Last Post: November 4th 2009, 07:45 AM
  5. Volume of Sand in a Pyramid
    Posted in the Calculus Forum
    Replies: 2
    Last Post: September 4th 2007, 01:12 AM

Search Tags


/mathhelpforum @mathhelpforum