Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:

  1. Find all the multiples of $4.5 \leq 48/4.5$
  2. Find all the multiples of $3 \leq 48/3$
  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$)
  4. 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:

  1. 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$")
  2. 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$).
  3. 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!

share|improve this question
    
This post is a pain to read; it will not attract many answers like this. I'll give a quick stab at the formulas, but you could do some effort in extracting a problem in purely mathematical form. For instance, it is of no relevance that units are inches, and you could divide all widths by $1.5$ inch to make thing integral. –  Marc van Leeuwen Nov 16 '12 at 9:49
    
Hi Marc Thanks for taking the time to edit my post. I didn't know how to write formulas, and couldn't find the right formatting. I'm going to take a look at the raw text so that next time I post something in this section, it will be easier to read. On the other hand, thanks for the tip about dividing all widths by 1.5! I didn't notice that, and from the computation point of view, it is faster to handle integral numbers rather than floating point number! Again I'm sorry for the formattin, I'll do it better next time. Thanks for your time. –  AlanChavez Nov 16 '12 at 15:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.