2
$\begingroup$

Is it possible to fill a box with dimensions $10\times10\times10$ using bricks of dimensions $1\times1\times4$?

If yes, how?

I think De Bruijn's theorem on harmonic bricks could be helpful, but I don't know if this theorem can be applied when 2 edges have length 1. I am not sure that the brick can be considered as harmonic. More info on De_Bruijn's theorem can be found here.

http://en.wikipedia.org/wiki/De_Bruijn%27s_theorem

I don't have aceess to any paper where the theorem is explained in more detail.

$\endgroup$
6
$\begingroup$

No, it is not. This can be seen via generating functions. We can position the box in 3-space with one corner at the origin so that it occupies $(a,b,c)$ for $0\leq a,b,c \leq 9$. Let us associate each point $(a,b,c)$ with the polynomial $x^ay^bz^c$. The sum of the points in the box can then be expressed as:

$$\mathrm{BOX}(x,y,z) = \sum_{a=0}^9 \sum_{b=0}^9 \sum_{c=0}^9 x^ay^bz^c$$

On the other hand, each brick can be expressed as either $x^ay^bz^c(1+x+x^2+x^3)$, $x^ay^bz^c(1+y+y^2+y^3)$, or $x^ay^bz^c(1+z+z^2+z^3)$ for some integers $a,b,c$, depending on the brick's orientation. The sum of the points in the union of the bricks can be expressed as:

$$\mathrm{BRICKS}(x,y,z) = F(x,y,z)(1+x+x^2+x^3) + G(x,y,z)(1+y+y^2+y^3) + H(x,y,z)(1+z+z^2+z^3)$$

for some polynomials $F, G, H$.

But $\mathrm{BOX}(i,i,i) = -2+2i$ while $\mathrm{BRICKS}(i,i,i)=0$, implying that the two polynomials are not identical, and thus that the desired partitioning is impossible.

$\endgroup$
  • $\begingroup$ Beautiful solution! Is it possible that $\mathrm{BOX}(i,i,i)=(i-1)^3=2+2i$? $\endgroup$ – wnvl Oct 5 '14 at 21:50
  • $\begingroup$ I just found out that it is $(i+1)^3=-2+2i$. Please, ignore my previous remark. $\endgroup$ – wnvl Oct 5 '14 at 22:14
  • 1
    $\begingroup$ @wnvl Thanks! This is a technique I learned for this type of problem back in my olympiad days. It can be used to solve a variety of tiling problems in any number of dimensions. $\endgroup$ – dshin Oct 5 '14 at 23:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.