1

The problem in the general case with arbitrary values is likely pretty difficult, so I limit the scope of this question to this specific problem:

Consider a rectangle with width 30 and height 16. Divide it into 12 pieces with equal area, and integer widths and heights. List all possible configurations.

Naturally, the area of each piece is 40. I tried factoring the relevant numbers (12, 16, 30, 40), but wasn't able to see anything interesting. I also tried considering additions of heights along a vertical line, i.e. 16 = 2 + 4 + 10, where each of the terms is a factor of the area 40. I obtained the somewhat useless result:

$$\{(2, 4, 5, 5) , \ (2, 4, 10) , \ (\textrm{tuples containing only 2, 4, 8})\}$$

where all of the values in each tuple adds up to 16. I was hoping this would limit the problem in some way, but that did not happen.

Mateen Ulhaq
  • 1,211
  • You might get more attention to your question if you tag it more accurately (IMO, combinatorics and/or divisibility and/or factoring). – barak manos Nov 30 '16 at 09:46

2 Answers2

1

IF ALL $12$ PIECES ARE OF EQUAL DIMENSIONS:

You need to find all pairs of positive integers $(\color\red{W},\color\green{H})$ such that:

  • $\color\red{W}\color\green{H} = 40$
  • $\color\red{W} \mid30$
  • $ \color\green{H}\mid16$

Analyzing these conditions leads to:

  • $(\color\red{W},\color\green{H})\in\{(1,40),(2,20),(4,10),(5,8),(8,5),(10,4),(20,2),(40,1)\}$
  • $ \color\red{W} \in\{1,2,3,5, 6,10,15,30\}$
  • $ \color\green{H} \in\{1,2,4,8,16 \}$

Intersecting these restrictions leads to:

  • $(\color\red{W},\color\green{H})\in\{(\color\red{1},40),(\color\red{2},20),(4,10),(\color\red{5},\color\green{8}),(8,5),(\color\red{10},\color\green{4}),(20,\color\green{2}),(40,\color\green{1})\}$

Or simply (extracting only the fully-colored pairs):

  • $(\color\red{W},\color\green{H})\in\{(\color\red{5},\color\green{8}),(\color\red{10},\color\green{4})\}$
barak manos
  • 43,109
  • I tried your method with the constraints $WH = 6, \ W | 9, \ H | 4$, but I was able to generate this counterexample. – Mateen Ulhaq Nov 30 '16 at 10:18
  • @MateenUlhaq: That's not a counterexample! You're supposed to take only pieces of $(\color\red{3},\color\green{2})$. One of the pieces there is $(\color\red{6},\color\green{1})$. You can easily fill up the rectangle with $6$ correct pieces. – barak manos Nov 30 '16 at 10:21
  • I mean that the original problem appears to be satisfied by the drawing provided. Both $(3,2)$ and $(6,1)$ are pieces with equal area. We do not require that all pieces must necessarily have the same dimensions. – Mateen Ulhaq Nov 30 '16 at 10:30
  • @MateenUlhaq: Oh, sorry, I must have missed that part of the question. I think that the set of $(W,H)$ certainly defines the possible dimensions of each piece. However, you are right - the combination of pieces doesn't necessarily consists of only one type of (identical) pieces. So there are possibly a lot more combination that simply counting the different types. I will delete this answer after you acknowledge this comment... – barak manos Nov 30 '16 at 10:49
  • Second thought, we might even be able to allow a combination of shapes that are not within this set (but when added together, fill up the rectangle perfectly). My answer is pretty worthless I suppose... – barak manos Nov 30 '16 at 10:51
0

This answer addresses the general problem.

Encode natural numbers $a=\prod_{k\geq1}p_k^{a_k}\geq1$ in the form $a=(a_1,a_2,,\ldots)$, and write $\oplus$ for the componentwise addition of two such codewords.

We are given the length $a$ and the width $b$ of a large rectangle $R$. Its area is then given by $${\rm area}(R)=a\oplus b\ .$$

If we want to divide $R$ into $n$ rectangular pieces of the same integer area then we have to choose $n$ such that $n\leq a\oplus b$, which means that we must have $n_k\leq a_k+b_k$ for all $k\geq1$. If the pieces have to be arranged in the "obvious" way then we need a partition $n=n'\oplus n''$ such that $n'\leq a$ and $n''\leq b$. This means that for each $k\geq1$ we must have $$n_k'+n_k''=n_k,\qquad n_k'\leq a_k,\qquad n_k''\leq b_k\ .\tag{1}$$ Let $N_k$ be the number of solutions of $(1)$. It turns out that $N_k$ is given by $$N_k=1+\min\{a_k,b_k,n_k,a_k+b_k-n_k\}\qquad(k\geq1)\ .$$ After the $N_k$ have been determined the total number $N$ of solutions to the problem defined by the data $a$, $b$, and $n$ is given by $$N=\prod_{k\geq1} N_k\ .$$ In the case at hand we have $a=(1,1,1)$, $b=(4,0,0)$, $n=(2,1,0)$ (referring to the primes $2$, $3$, $5$), and therefore $N_1=2$, $N_2=N_3=1$, which then leads to $N=2$.

Christian Blatter
  • 226,825