Algorithm to divide a chocolate bar in equal parts

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 goes like this:

Info

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

The problem

Write an algorithm that outputs the optimal configuration (p x q) where the bar can be shared equally between n, n-1, n-2...., 2, 1 people given the following restrictions:

1. A small squares (the unit square) cannot be cut into smaller pieces
2. All breaks have to be made completely along one axis
3. The total number of breaks cannot be more than n (this is to discourage inefficient solutions such as trying to break the whole bar apart into small pieces and dividing the small pieces)
4. p or q cannot be equal to 1. yx pointed out in one of the answers that the problem is easily solvable if one side has 1 bar. This, however is not a good solution for real world situations - which was the intent of solving this problem :)

Example

For n = 4, the optimal configuration is 4 x 3.

 ~~~~ ~~~~ ~~~~ ~~~~
|    |    |    |    |
 ~~~~ ~~~~ ~~~~ ~~~~
|    |    |    |    |
 ~~~~ ~~~~ ~~~~ ~~~~
|    |    |    |    |
 ~~~~ ~~~~ ~~~~ ~~~~

This configuration can be divided among:

4 people in 3 breaks along the vertical axes
3 people with 2 breaks along the horizontal axes
2 people with 1 break right down the middle

Other empirical solutions are (n, p, q) = (1, 1, 1); (2, 2, 1); (3, 3, 2); (4, 4, 3); (5, 5, 12); (6, 6, 10) OR (6, 5, 12)

Clarifications
A break is defined as a cut along one axis for the subset of the bar, if applicable. To better illustrate this, say you have a 2 x 2 chocolate bar like this:

 ~~~~ ~~~~
|    |    |
 ~~~~ ~~~~
|    |    |
 ~~~~ ~~~~

Conventional wisdom says you need to make 2 breaks (the perpendicular axes in the middle - down and across) to divide this bar into 4 pieces. However, in the real world (if it were a chocolate bar), you would first break it in half and then break each half again, separately. This makes a total of 3 breaks - 1 break on the entire bar and 2 breaks on 2 different sub sets of the bar.

I couldn't find solution anywhere on the internet - if anyone feels this is not a programming related question or a solution already exists, feel free to close the question =)

Answer 1

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

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

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

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

############

And can be divided as follows:

1: ############     // 0 cuts
2: ###### ######    // 1 cut
3: #### #### ####   // 2 cuts
4: ### ### ### ###  // 3 cuts (3 being n-1)

Answer 2

Since you can not cut multiple 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 cuts. Each cut creates one more piece, you start with one piece.

Building on the previous solution, I think you were looking intuitively for the following algorithm:

A = LCM(n)
p = greatest divisor of A <= sqrt(A)
q = A/p

The algorithms for this should be trivial, (e.g. start with p = floor(sqrt(A)) and count down until mod(A,p) == 0).

The reason you want sqrt is to limit the amount of numbers you check. After all, you will always have one divisor <= sqrt(A) and one >= sqrt(A)

Answer 3

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

I'd like to add that the rules would enforce which breaks of the chocolate bar are legal and those possible states which are not legal are thrown out from the algorithm.