The image shown below is a cross with length 2. If length of a cross of length $k$ it is called a $k$-cross. (Each $k$-cross ahs $6k+1$ squares.) Invalid image file a) Prove that space can be tiled with $1$-crosses. b) Prove that space can be tiled with $2$-crosses. c) Prove that for $k\geq5$ space can not be tiled with $k$-crosses.
Problem
Source: Iranian National Math Olympiad (Final exam) 2006
Tags: analytic geometry, algorithm, pigeonhole principle, geometry, combinatorics proposed, combinatorics
14.09.2006 08:52
even $k\geq 4$ is correct .and also for $k=3$ it is not possible to tile space regularly.
08.12.2006 13:51
any solution?
10.03.2007 04:35
1) Let us work not with cubics but with three coordinate system. Denote cross $C_{i}=(a,b,c)$ if it occupies this point and also $(a+1,b,c), (a-1,b,c), (a,b+1,c)(a,b-1,c),(a,b,c+1)(a,b,c-1)$. We want to construct an algorithm for tiling, let us take a plane in 3D space and complete with centers of crosses through lines $y=2x+3k$ where $k \in Z$. Observe that there are points that are not covered by crosses and they from the same picture that we have, but with the shift $(+2,+1)$. Thus on the plane that is one unit up we consider crosses at those spaces. The next shift will be right back, one can easy check that it does not leave any gapes in coordinate system. Thus we can cover by $1\times 1$ the whole space. 2) I think it requires similar, more tricky construction for $2$- crosses, just good feeling of 3D. 3) To prove that we cannot tile with $k \geq 4$ crosses, consider a particular case $4$-cross, the same argument will work for any $k$. Take plane version of the $4$ cross with its center. It is a cross with arm of length $4$. Take one quadrant of it. Near arms we have a field of $16$ squares. That field can covered by at most two crosses from that plane, that take out $4+3$ squares. It follows that remained $9$ squares, that are covered from crosses from the other planes, from upper or from lower planes. By Pigeonhole we have at least $5$ points from upper planes (WLOG). Their height is at most $4$, to touch our field. It means two centers of crosses lie int the same plane in area $4\times 4$, contradiction.
Attachments:
