In this question that I posted yesterday (11/15):
I am solving a programming puzzle that consists of finding all the possible ways to build a brick wall of $48$" $\times$ $10$" (width $\times$ height respectively) with two types of blocks:
block a: $4.5$" $\times$ $1$"
block b: $3$" $\times$ $1$"
so that the spaces between the blocks must not line up in adjacent rows.
I managed to compute all the possible combinations (including the ones that line up blocks in adjacent rows) in paper, but right now I'm trying to transform my "mental algorithm" into a general formula so that I can write a program to solve it.
My algorithm is as follows:
- Find all the multiples of $4.5 \leq 48/4.5$
- Find all the multiples of $3 \leq 48/3$
- Sum all the possible combinations of between the multiples of $4.5$ and $3$ and keep the ones whose result is exactly equal to $48$ (e.g. $4.5*10 + 3*1 = 48$)
- Add the multiplicands of the multiples of $4.5$ and $3$ to figure out the number of bricks needed of each kind to build a wall of $48$" long.
In those 4 steps I was able to come up with 5 different scenarios:
Scenario 1: block A = $4.5$" block B = $3.0$"
- $10$ blocks A and $1$ block B. $11$ bricks in total.
- $8$ blocks A and $4$ blocks B. $12$ bricks in total.
- $6$ blocks A and $7$ blocks B. $13$ bricks in total.
- $4$ blocks A and $10$ blocks B. $14$ bricks in total.
- $2$ blocks A and $13$ blocks B. $15$ bricks in total.
Thus, in order to know all the possible combinations of bricks, is just a matter of adding:
$ \binom{15}{2} + \binom{14}{4} + \binom{13}{6} + \binom{12}{8} + \binom{11}{10} = 3328 $ When I was trying to make a general formula I noticed the following pattern: $ \binom{k-i}{2i} $ I also noticed that $2$ blocks of length $4.5$" are equal to $3$ blocks of length 3"
($2*4.5 = 3*3$)
therefore it has a ratio of two thirds ($2/3$)
I came up with the following formula:
Let $w$ = width of the wall ($48$")
$r$ = ratio of the bricks ($2/3$)
$k = \lfloor(w*r)/2\rfloor$
I can easily build the pattern: $ \binom{k-i}{2i} $ That generalization holds true for values of $w = 12$ and $48$
however I'm still having a hard time making sense out of the line of thought because it was more than a hunch than an actual thinking processes. In other words:
I multiplied the width of the wall time the ratio of the bricks, because I had a hunch, and then I noticed that $32$, was $16*2$, and noticed how it perfectly fit in the previous pattern I detected $(k-i, 2i)$ so I thought that $wr/2$ made sense.
I tested that "epiphany" and held true for the value of $12$ as well, but I'm not really sure what is the logic behind it.
So my questions are:
- In common english what do I get when I multiply the width of the wall times the ratio of the bricks? (e.g. The ratio of the bricks is $2:3$ because $2$ bricks of length $4.5$" are as long as $3$ bricks of $3$")
- Why do I need to divide it by two, and why does it hold true for different widths? (I yield to right answers using the $12$ as width, as well as using $48$).
- How can I figure out the maximum value of $i$? (e.g. let $w=48$, $r=2/3$, $k = wr/2$, the maximum value of $i$ would be $5$ so that
$\sum_{i=1}^{k/3}\binom{k-i}{2i+j} = 3328$ )
Any help or orientation in this matter will be greatly appreciated! Thanks a lot!