Why are candy bars divided into squares

DISABLE ADBLOCK

ADBlock blocks some content on the website

question

A random thought popped into my head (when I was sharing a chocolate bar of course!). I was wondering if there is a generic algorithm to solve this problem.

The problem is as follows:

info
1. You have arranged a chocolate bar with small squares in a rectangular matrix
2. There are n people in the room

The problem
Writing an algorithm that gives the optimal configuration (p x q) where the rod can be shared evenly between people given the following constraints:
1. A small square (unit square) cannot be broken into smaller pieces 2
get cut. All breaks complete
3 can be made along an axis. The total number of breaks cannot be more than n (this is inefficient to discourage solutions like trying to break the entire bar apart into small pieces and subdividing the small pieces)
4. p or q not equal to 1. yx pointed out in one of the answers that the problem can be easily solved if one side shows 1 bar. However, this is not a good solution for real world situations - that was the intent of solving this problem :)
example
For n = 4, the optimal configuration is 4 x 3.


4 people in 3 breaks along the vertical axes
3 people with 2 breaks along the horizontal axes
2 people with 1 break exactly in the middle <:>

This configuration can be divided among other empirical solutions
Clarifications
a fraction is defined as the section along an axis for the subset of the rod, if applicable. To better illustrate this, say you have a 2 x 2 candy bar like this:

Conventional wisdom says that if you take 2 breaks (the vertical axes in the middle - down and across) you have to divide this bar into 4 pieces. However, in the real world (if it was a candy bar) you'd break it in half first and then break each half again, separately. That makes a total of 3 breaks -. 1 break on the entire bar and 2 breaks on 2 different bases of the bar
I couldn't find solution anywhere on the internet - if someone feels this is not a programming related question or a solution already exists, feel free to answer the question =)

shut down

solution

It seems to me that you are looking for numbers that are evenly divisible by all numbers between 1 and n inclusive. That is denoted the least common multiple of 1, ..., n. A square contains the least common multiple of 1, ..., n squares by definition would be evenly divisible into pieces of size 1, ..., n. You are looking for a maximum of n splits, which adds additional complexity to the problem, which are not possible or not.

Your example for n = 4 is the LCM (4,3,2,1), the 12th LCM is (5,4,3,2,1) is 60th LCM (6,5,4,3,2, 1) is also 60.

They can always be laid as 1xLCM (n, ..., 1) rectangles and always divisible into 1, ..., n even piles in n-1 or fewer divisions.

For example, if n = 4, LCM (4,3,2,1) = 12. The rectangle is

And can be divided as follows:

OTHER TIPS

Since you can't cut more pieces at once, for any number of pieces m you want, where m is in the set (1..n), you will always need m-1 cut. Each cut creates one more piece to get you started with one piece.

Based on the previous solution, I believe you are intuitively looking for the following algorithm:

The algorithms for this should be trivial, (for example with p = floor (sqrt (A) start) and countdown to mod (A, p) == 0).

The reason you want sqrt is to limit the amount of numbers you check. After all, you will always have a divider <= sqrt="" (a)="" und="" ein=""> = sqrt (A)

A great way to answer this question would be to use a breadth-first search algorithm. The algorithm would try to find every possible break of the whole candy bar. Then for each of these possible states of the problem, try all possible pauses and this would continue while keeping track of the evenness of the pieces.

I would add that the rules would enforce which the candy bar breaks lawfully and those possible states that are not legal are thrown out of the algorithm.

Get answers to millions of questions and give back by sharing your knowledge with others.

Sign up for an account.

The contents are licensed under creative commons.

If you find copyright violations, you can contact us at info-generacodice.com to request the removal of the content.