|HubPages Device ID||This is used to identify particular browsers or devices when the access the service, and is used for security reasons.|
|Login||This is necessary to sign in to the HubPages Service.|
|HubPages Traffic Pixel||This is used to collect data on traffic to articles and other pages on our site. Unless you are signed in to a HubPages account, all personally identifiable information is anonymized.|
|Remarketing Pixels||We may use remarketing pixels from advertising networks such as Google AdWords, Bing Ads, and Facebook in order to advertise the HubPages Service to people that have visited our sites.|
|Conversion Tracking Pixels||We may use conversion tracking pixels from advertising networks such as Google AdWords, Bing Ads, and Facebook in order to identify when an advertisement has successfully resulted in the desired action, such as signing up for the HubPages Service or publishing an article on the HubPages Service.|
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?
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.
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
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.
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.
by Quilligrapher5 years ago
From a CNN report GOP divide over Obama tax plan goes public, November 28, 2012:"A CNN/ORC International poll released Monday also showed that a solid majority of respondents -- two thirds -- supports the...
by Beverly Anderson23 months ago
Easy ways to cut hairI want simplified ways to cut hair
by billd016035 years ago
Why is the liberal media making such a big deal about the sequester cuts?They are not cuts, but a lessening of the rates of increase.
by Marie Alana5 years ago
What do you think of the recent federal money cuts?They have cut billions of dollars from the federal funding. How do you feel about this? What specific cut means the most to you?
Copyright © 2018 HubPages Inc. and respective owners.
Other product and company names shown may be trademarks of their respective owners.
HubPages® is a registered Service Mark of HubPages, Inc.
HubPages and Hubbers (authors) may earn revenue on this page based on affiliate relationships and advertisements with partners including Amazon, Google, and others.