The Simple Proof of the Tetris Lamp(jackm.co.uk) |
The Simple Proof of the Tetris Lamp(jackm.co.uk) |
(on second thoughts, you could probably get away with rotating your solution if you're willing to forfeit the '4 width' condition)
It is too bad the lamp wasn't made of pentominoes (the 12 Tetris-like pieces with 5 squares vs. your tetrominoes with 4 squares.). See http://en.wikipedia.org/wiki/Pentomino. There are 2339 ways to form these into a perfect 6x10 rectangle (more if you include rotations and reflections).
FYI: The creator of Tetris actually got the idea for his game pieces from Solomon W. Golomb's book "Polyominoes" that introduced all kinds of variations on tiling puzzles and proofs. Chapter one starts using checkerboard reasoning right off the bat. So, you are in good company.
http://www.thinkgeek.com/product/f034/
(I realize we all have access to Google, but if I save 100 people 10 seconds, then I just saved 1000 seconds!)
[1] http://www.amazon.com/review/R10BVZ9OBT3IW3
[2] http://www.amazon.co.uk/Tetris-Version-2-Tetrimino-Light/dp/...
A small technical detail, dew to professional deformation. The article says that the numbers of squares of each color must be the same, but that only happens if the total number is even, like in this case 13+15=28. If the total number of squares is odd, then you get one extra square of one of the colors.
I wouldn't be mad at the designer. That person designed a lamp and proposed an impossible puzzle that at first glance looked plausible.
It is the best way to troll people... ever!
2233ffff
72233ddd
7744eaad
7114eaag
5114eegg
555bbccg
6666bbcc
https://3dwarehouse.sketchup.com/model.html?id=u2d94f70c-682... (there's a webgl viewer)
1) Why limit yourself to 4x7? The 1988 NES version of Tetris is 10 units wide.
2) There isn't any malicious design, you simply get 1 of each shape (one of the L pieces in the author's photo is reflected, should be turned the other way).
3) In Tetris, a full row is removed immediately so having a complete rectangular shape that occupies the full available width is unrealistic.
Pedantry aside, you'd have to ask Alexey Pajitnov if there was any devilry involved in choosing the shapes since the makers of the lamp have faithfully included a full set. Also, I personally prefer the aesthetic of a lamp arranged in such a way as to leave a hole in each row rather than a plain wall of coloured squares.
No devilry, there's just only so many ways you can connect four squares together to make a shape.
Presumably, the objective is to arrange the tetriminos into a pleasing rectangle shape. Unfortunately, the factors of 28 are 1, 2, 4, 7, 14 and 28, so 4x7 is the closest you can get to a square, and 2x14 has a similar problem of having the same number of 'white' squares as 'black' squares. The closest one can get is 5x6 with two holes removed.
Every engineer who has this lamp on their desk has thought of this.
There's no "design" involved in the choice of pieces: there are seven different ways to connect four squares in an orthogonal grid, "tetrominoes", assuming you allow for pieces to be rotated but not reflected. Tetris uses all seven, and so does the lamp. (Although the lamp's design apparently allows pieces to be reflected, i.e. rotated outside of the grid, so the S and Z pieces can be considered the same, as can L and J.)
Proof: Any rectangle made of Tetris pieces must have an even number of squares (in fact, a multiple of 4) and hence the same number of black/white squares. Every Tetris piece except the T has the same number of black/white squares, hence the T cannot be used in any arrangement of a subset of Tetris pieces into a rectangle.
Every even x even rectangle has equal dark and light squares.
Every even x odd rectangle has equal dark and light squares.
Every odd x odd rectangle has one more odd then even, or one more even then odd. (1x1 square is obvious, any odd x odd rectangle can be reduced to 1x1 square by removing only odd x even rectangle.)
Since the T piece creates a odd-even difference of 2, any number of other tetris pieces (including repeats) that only contains a single T piece can never form a rectangle with no holes.
Interestingly, his account is rather different than that on wikipedia http://en.wikipedia.org/wiki/15_puzzle Singh claims that Sam Lloyd created the puzzle, secretly proved it was impossible, and offered rewards to anyone who could solve it.
Answer (ROT13): Vg qrcraqf ba gur cnevgl bs gur ahzore bs fdhnerf, juvpu qrcraqf ba jurgure gur qvzrafvbaf bs gur tevq fvqrf ner obgu bqq be abg. Vs gur ahzore bs fdhnerf vf bqq, gurer nera'g nf znal juvgr fdhnerf nf oynpx fdhnerf, naq n plpyr zhfg tb sebz juvgr gb oynpx naq sebz oynpx gb juvgr, fb ab plpyr rkvfgf. Vs vg vf rira, lbh pna rnfvyl pbzr hc jvgu n trareny fpurzr gb pbafgehpg n plpyr.
The max area I'm having to tile is fairly small (maybe 100x100 at most) so an actual solution could be fairly easily brute-forced in the last step of the process. I just want to avoid having to backtrack as much as possible since it increases the cost substantially.
All this from memory, so it might be totally wrong.
Maybe it only proves the negative, but not that there must be a solution.
Edit: there seems to be a solution for a 4x6 rectangle.
rr Z [] S LL
r ZZ [] SS L
r Z IIII S L
rr Z [] S LL
r ZZ [] SS L
r Z IIII S L
rrZ[]SLL
rZZ[]SSL
rZIIIISL ZZLL
IZZL
IOOL
IOOJ
ISSJ
SSJJ OOZZ
OOSZZ
LLSS
ILTS
ILTT
IJT
IJJJ
edit: Actually I'm not sure my previous statement was true. You can make it more pleasing such as this though: http://nterm.co.uk/content/images/tetris.png
