A carrot measures 100mm long and needs to be sliced into 100 1mm thick slices.

1. 94

   CWanamakerposted 11 years ago

   A carrot measures 100mm long and needs to be sliced into 100 1mm thick slices.
   
   What is the minimum number of cuts required to do so if you are allowed to cut multiple pieces (from a previous cut) during a single slice?
   
   

   replyreport
2. 85

   SidKempposted 11 years ago

   Fun question!
   There are at least 2 ways to do it in 8 cuts. The simplest is:
   1st  cut in halves,    2 x 50cm pieces
   2nd cut in quarters, 4 x 25 cm pieces
   3rd cut cut 1cm off,  4 x 24 cm pieces & 4 x 1cm pieces
          the 4 x 1cm pieces are done, set them aside
   4th cut creates 4 x 16cm pieces and 4 x 8 cm pieces -cut each 24cm piece 1/3 & 2/3
   5th cut only on 4 x 16cm pieces, creating 8 x 8 cm pieces
        we now have 12 x 8cm pieces (and 4 finished 1cm pieces set aside)
   6th cut - all 8cm pieces in half gives us 24 x 4cm pieces
   7th cut - in half again, now we have 48 x 2cm pieces
   8th cut - in half again, we now have 96 x 1cm pieces, plus the 4 x 1cm pieces set aside in step 3
   Is a total of 100 1cm pieces created in 8 cuts.
   
   I found another way to do it in 8 pieces, very complicated to describe. It's the same through step 4. Then each remaining piece is either 16 or 8cm, and cut in half again and again until it reaches 1cm and is set aside.
   
   This second method can be proven to be the minimum number of cuts, since every piece that is not 1cm long is cut every time the knife is used. So, although there are multiple ways to do it in 8 slices, I think 8 slices must be the minimum possible.
   
   It is interesting to think of this problem in terms of prime factors.
   The prime factoring of 100 is 2 x 2 x 5 x 5.
   The cutting solution is to slice in half whenever you can, so 2 slices creates 4 x 25cm pieces (or 2x2 pieces, each 5x5 in length)
   by trimming the 25 inch pieces to 24cm and 1cm pieces, we can set the 1cm pieces aside.
   Then we have to finish the remaining 4 x 24cm pieces.
   The prime factoring of 24 is 2 x 2 x 2 x 3
   At this point, cutting in thirds gives pieces that are all a length of powers of 2 (8cm or 16cm each), and any way of cutting these in 4 or fewer slices finishes the job.

   replyreport
   1. 0

      calculus-geometryposted 11 years agoin reply to this

      I like your analysis of the prime factors.  I think you can improve on the 3rd cut's efficiency by going 16 & 9 instead of 24 &1. 24 requires 5 cuts to get it down to 1, but 16 & 9 require 4 cuts. That would bring your solution down to 7

      replyreport
3. 55

   tussinposted 11 years ago

   I can prove that the minimum number of cuts needed is at least 7 since the base-2 logarithm of 100 is greater than 6.  This is an existence proof, not a constructive proof, so I'll leave it to someone else to figure out the right sequence of cuts...
   
   After the nth cut, there are at most 2^n pieces on the cutting board.  The number can be less than 2^n since you might choose not to divide certain pieces on the nth cut. Therefore, the average length of a piece after the nth cut is at least 100/(2^n).  This is because the sum of the lengths is 100 and the number of cuts is no more than 2^n.
   
   When the entire carrot is cut into 1mm slices, the average length (or thickness more like) is 1.  When you solve the inequality
   
   100/(2^n) lessthanorequalto 1
   
   you get n greaterthanorequalto 6.644. (sorry, can't make appropriate symbols) But since n has to be an integer, this implies that n is greater than or equal to 7.
   
   Unfortunately, I can't demonstrate a solution in which only 7 cuts are needed, but I feel confident that such a solution must exist.

   replyreport
4. 0

   calculus-geometryposted 11 years ago

   This is a 7-cut solution:
   
   1st cut yields two pieces of length 64mm and 36mm.
   2nd cut: Simultaneously cut the 64mm piece in half and cut the 36mm piece into 32mm and 4mm. This yields three pieces of length 32mm and one piece of length 4mm.
   3rd cut: Cut everything in half simultaneously.  Yields six 16mm pieces and two 2mm pieces.
   4th cut: Cut everything in half again. Yields twelve 8mm pieces and four 1mm pieces.  Set these 1mm pieces aside.
   5th cut: Cut the 8mm pieces in half to yield twenty-four 4mm pieces.
   6th cut: Cut the 4mm pieces in half to yield forty-eight 2mm pieces.
   7th cut: Cut the 2mm pieces in half to yield ninety-six 1mm pieces. Fin.
   
   My idea was to get to a point where all the pieces had a length that was a power of two so that the operation would boil down to halving.  This occurs after the 2nd cut when you have 32, 32, 32, and 4.  I agree with Tussin's argument that this has to be the minimum.

   replyreport
   1. 85

      SidKempposted 11 years agoin reply to this

      I think you got it - I could prove the 8 cut, and find 2. I thought there might be a 7-cut, but I wasn't sure.

      replyreport