8 ms·
The Simple Proof of the Tetris Lamp
- davecap1 12y agoThat's exactly how they get you to buy TWO lamps! :)
- deleted 12y ago[deleted]
- rndn 12y agoIs that really obvious? I think the checkerboard pattern only says something about the neighborhoods of the pieces and the amounts of tiles of each color used, not whether there exists is a rectangle configuration.
- rmetzler 12y agoIf you buy 2 lamps, you've got 2 of all the 7 pieces. Piece 7 (the T-shaped piece) is doubled and you can switch the pattern for the second set. You'll have 15x color A and 13x color B in the first set and 13x color A and 15x color B in the second set. I'm pretty sure this would enable you to create a rectangular lamp.
- nemetroid 12y agoHaving the same number of both colours is not sufficient. 14 Z pieces will give you 28 of each color, but you can't make a rectangular lamp (of any size) from only Z pieces.
- eterm 12y agoNot in 2D, but you can in 3D! 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 http://nterm.co.uk/content/images/tetris.png
- penguat 12y ago<nitpick>rectangle specifies 2d</nitpick> I believe you could form a hollow cuboid, but I don't think you could complete a solid cuboid.
- dkersten 12y agoSo the obvious next question is: how many sets do you need to create a perfect rectangle?
- evanb 12y agoThat's true, but here's a construction: OOZZ OOSZZ LLSS ILTS ILTT IJT IJJJ That's built out of one full set of OZSLJTI. If you take two of those, one rotated by 180˚, you get a rectangle.
- JoshTriplett 12y agoThe proof in the article is a proof by contradiction. Having equal numbers of each colored square is a necessary but not sufficient condition to form a rectangle.
- deleted 12y ago[deleted]
- ecesena 12y agoHere's an example. The trick I used was creating the extra block and the hole on the same side (so, not like the pic). With the pieces numbered as in the post: 2233ffff 72233ddd 7744eaad 7114eaag 5114eegg 555bbccg 6666bbcc Note that, as in the post, I'm not "respecting" Tetris in 2d: pieces 2 and 3 have been "3d rotated" and are "looking in the same direction".
- deleted 12y ago[deleted]
- deleted 12y ago[deleted]
- mjs 12y agoSimilar to: https://en.wikipedia.org/wiki/Mutilated_chessboard_problem https://en.wikipedia.org/wiki/Mutilated_chessboard_problem
- carussell 12y agoThe problem and its proof are mentioned in EWD 1036: On the cruelty of really teaching computing science. < http://www.cs.utexas.edu/users/EWD/transcriptions/EWD10xx/EWD1036.html http://www.cs.utexas.edu/users/EWD/transcriptions/EWD10xx/EW... >
- webnrrd2k 12y agoThat is a really great paper! It should be required reading for all computer science types.
- gus_massa 12y agoYes. Every time you get a problem with a rectangle table, you must paint it like a chessboard. If that is not enough to find the solution, you must try to think. 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.
- j2kun 12y agoYou must paint it, but it is sometimes better to choose a pattern specific to the problem you're trying to solve. E.g. http://jeremykun.com/2011/06/26/tiling-a-chessboard/ http://jeremykun.com/2011/06/26/tiling-a-chessboard/
- pja 12y agoMinor derail - I know I mistype 'their' as 'they're' and likewise for other similar homonym pairs all the time, but due -> dew is a particularly nice example of the genre :)
- rndn 12y agoIsn't the lamp simply designed to contain all of the seven types of Tetris pieces?
- pharke 12y agoA few things: 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.
- vinceguidry 12y ago> 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. No devilry, there's just only so many ways you can connect four squares together to make a shape. http://en.wikipedia.org/wiki/Tetromino http://en.wikipedia.org/wiki/Tetromino
- pharke 12y agoHe could have chosen pentominoes instead. http://en.wikipedia.org/wiki/Pentomino http://en.wikipedia.org/wiki/Pentomino
- eps 12y agoBtw, the Tetris field is always exactly 10x20.
- prezjordan 12y agoThis is not an exercise in "valid" tetris configurations, per se. It's a matter of arranging these blocks to make a clean square - plain and simple. The "malicious design" is tongue-in-cheek. Every engineer who has this lamp on their desk has thought of this.
- AlexMax 12y ago> 1) Why limit yourself to 4x7? The 1988 NES version of Tetris is 10 units wide. 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.
- kcanini 12y agoWhat's more annoying is that it has two identical L pieces, instead of having one that is a mirror-image of the other, as they appear in Tetris.
- sadawi 12y agoLooks like the pieces are reversible, so the two L's and two S's are actually L, J, S, and Z.
- bjackman 12y agoWell it looks like you can rotate them (I mean in the 3rd dimension not present in actual Tetris)
- Luc 12y agoThere's also two S pieces instead of an S and a Z. Irritating indeed. There must be order!
- otikik 12y agoSo if you ignore piece number 7, can you form a rectangle with the remaining pieces?
- mistercow 12y agoWell, this proof doesn't mean you can't. It's not sufficient to prove that you can.
- mc808 12y agoIt can be done, at least if you're allowed to flip one of the 'L' pieces into a 'J'. 1112 1322 3324 3554 6554 6664
- JonRB 12y agoThe power goes into the bottom piece so that gravity ensures good electrical connection between the pieces. I imagine here may still be a solution but your 4444 piece needs to be the base. (on second thoughts, you could probably get away with rotating your solution if you're willing to forfeit the '4 width' condition)
- tintamarre 12y ago:-) https://lh4.googleusercontent.com/-dTGQKj2JHKo/VLOsol5kN3I/AAAAAAAAwWM/VJj9ECvKBKo/w878-h1184-no/IMG_20150112_121439.jpg https://lh4.googleusercontent.com/-dTGQKj2JHKo/VLOsol5kN3I/A...
- jones1618 12y agoTerrific reasoning! That same "checkerboard coloring" strategy is used a lot for figuring out tiling problems. 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 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.
- jimmaswell 12y agoYou could rotate some pieces such that they're partially jutting out of the back of the lamp, which might make it possible.
- archagon 12y agoSpeaking of Tetris proofs, I've had the following problem on the back-burner for a while: is there a way to check whether an arbitrary contiguous space comprised of squares can be filled in by tetrominoes? I don't have a math background so reasoning about it is difficult. Here's the question on StackOverflow: http://stackoverflow.com/questions/20083552/tetromino-space-filling-need-to-check-if-its-possible http://stackoverflow.com/questions/20083552/tetromino-space-...
- praptak 12y agoI vaguely remember someone having proved Tetris NP-hard but I think the problem wasn't filling a fixed shape but rather maximizing the number of erased lines given a board and an upcoming sequence of pieces. All this from memory, so it might be totally wrong.
- jones1618 12y agoA lot depends on your specific rules of the game. Does "filled by tetrominoes" mean you have to use every tetromino at least once? If not, then you can always fill your contiguous square space with 2x2 tetrominoes. Also, whatever your rules, it is generally a lot easier to prove it is possible (or not) to fill a space than find an actual solution.
- archagon 12y agoThe main rule I'm trying to follow is "as random a tiling as possible". So unless absolutely necessary, no picking certain pieces just because it's easier. 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.
- ezl 12y agoyou should turn that link into an affiliate link. i would love to know how many (other) people also bought that tetris lamp after reading the article.
- pmelendez 12y ago>"Maybe now I can shift my irritation from the lamp itself to whoever designed it to possess such a property. " 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!
- runn1ng 12y agohttp://en.wikipedia.org/wiki/File:15-puzzle-loyd.svg http://en.wikipedia.org/wiki/File:15-puzzle-loyd.svg :)
- Russell91 12y ago"Some later interest was fuelled by Loyd offering a $1,000 prize for anyone who could provide a solution for achieving a particular combination specified by Loyd, namely reversing the 14 and 15.[13] This was impossible, as had been shown over a decade earlier by Johnson & Story (1879), as it required a transformation from an even to an odd combination."
- megamark16 12y agoI came here looking for a link to someplace where I can buy this lamp. Since no one has posted such a link yet, here it is: http://www.thinkgeek.com/product/f034/ 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!)
- martin_ 12y agoThe article links to it in the first sentence also: http://www.amazon.co.uk/Lychee-Tetris-Constructible-Three-dimensional-squares/dp/B00JZGD930 http://www.amazon.co.uk/Lychee-Tetris-Constructible-Three-di...
- toast0 12y agoIf only it were underlined so we would have known it was a link?
- debacle 12y agoIs that responsive?
- andyjohnson0 12y agoAccording to this [1] comment on Amazon US, the Lychee product is a cheaper version of the official Tetris product [2]. [1] http://www.amazon.com/review/R10BVZ9OBT3IW3 http://www.amazon.com/review/R10BVZ9OBT3IW3 [2] http://www.amazon.co.uk/Tetris-Version-2-Tetrimino-Light/dp/B009USUO68 http://www.amazon.co.uk/Tetris-Version-2-Tetrimino-Light/dp/...
- fastball 12y agoAnd for those in Europe: http://www.firebox.com/product/5339/Tetris-Light http://www.firebox.com/product/5339/Tetris-Light
- jimmaswell 12y agoHere's one nice-looking configuration I found. You seem to be implicitly assuming you can only have a depth of one unit but that's possibly an unnecessary limitation. I'm working on seeing if some kind of perfect cuboid can be made. https://3dwarehouse.sketchup.com/model.html?id=u2d94f70c-6825-4fed-bc3d-bfc700d99eec https://3dwarehouse.sketchup.com/model.html?id=u2d94f70c-682... (there's a webgl viewer)
- osense 12y agoI'm not sure, but i think the lamp wouldn't work anymore - it seems like the front and back metal strips might have different polarity.
- jimmaswell 12y agoMight not light up anymore, yeah. Maybe with some rewiring.
- qb45 12y agoThis is to prevent customers from accidentally assembling the lamp in an unspectacular way.
- asgard1024 12y agoYeah, if you form a perfect rectangle, all the pieces will disappear.
- jakethedog 12y agoYou can make a rectangle as long as you don't use all of the pieces (maybe that is part of the puzzle?). For example, from http://www.amazon.co.uk/Lychee-Tetris-Constructible-Three-dimensional-squares/dp/B00JZGD930 http://www.amazon.co.uk/Lychee-Tetris-Constructible-Three-di..., remove the purple piece, shift the red piece to the left one space and flip it, then place the blue piece vertically on the right hand side.
- peeters 12y agoThe argument in the article was that it's the purple piece (the "T") that is the problem (or least that makes the proof trivial). Can you make a rectangle with a subset that includes the T?
- throwaway183839 12y agoTheorem: No. 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.
- deleted 12y ago[deleted]
- kazagistar 12y agoNo. 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.
- h_a 12y agoReminds me of Knuth's Dancing Links algorithm: http://arxiv.org/pdf/cs/0011047.pdf http://arxiv.org/pdf/cs/0011047.pdf
- deleted 12y ago[deleted]
- PhasmaFelis 12y ago> Maybe now I can shift my irritation from the lamp itself to whoever designed it to possess such a property. 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.)
- bbcbasic 12y agoWow so weird to see the tetris lamp on HN. One of my 2 year-old's favourite toys!
- a3_nm 12y agoA similar trick can be used to solve the following problem: considering a rectangular grid, is it possible to find a cycle that goes from adjacent squares to adjacent squares and visits each square exactly once? 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.
- theoh 12y agoThis is called a Hamiltonian circuit.
- lern_too_spel 12y agoYour friend read Martin Gardner's aha! Insight, which has exactly this proof in it and is a popular book for young mathematical puzzle enthusiasts.
- staffordrj 12y agoVery relevant to the video game Sigils of Elohim http://store.steampowered.com/app/321480/ http://store.steampowered.com/app/321480/
- izzydata 12y agoMaybe now you will have to buy a second one in order to make a perfectly rectangle then get rid of the excess pieces. Genius design.
- Spoygg 12y agoNerdgasm :)
- robinhouston 12y agoIf you remove the T piece, is it possible to assemble the other six into a rectangle? I suspect not, but the checkerboard proof does not suffice for this.
- pjtr 12y agorr 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
- robinhouston 12y agoInteresting! I just came here to say that I’ve found a 4x6 packing. I love the fact you can also do 3x8! ZZLL IZZL IOOL IOOJ ISSJ SSJJ
- Dove 12y agoI would think rotating this sideways and placing the troublesome T on top would give a pleasingly neat and symmetrical shape, if not a rectangular one.
- jpeggg 12y agoAuthor here - slightly overwhelmed by the response, but thanks for everyone's feedback! I never thought so many people would be as interested as I am in the lamp...
- paxcoder 12y agoI would be interested in learning who that friend was, and how he got to the proof.
- DominikR 12y agoInteresting concept. However, is it really a proof? If I removed piece #7 I'd have 24 boxes (12 white, 12 black) with which I could theoretically build a 6x4 rectangle, but I don't see how this would be actually possible with those pieces. 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.
- jpeggg 12y agoExactly that - it's a proof that in this case a solution can't be found. Having a collection of pieces that doesn't violate the assumption in the article isn't a sufficient requirement for a solution to exist.
- analyticsjam 12y agoI recently read a similar case in Simon Singh's book Fermat's Enigma http://www.amazon.com/reader/0385493622?_encoding=UTF8&query=15 http://www.amazon.com/reader/0385493622?_encoding=UTF8&query... about the 14-15 puzzle. It was similarly unsolvable and provable the same way. Interestingly, his account is rather different than that on wikipedia http://en.wikipedia.org/wiki/15_puzzle 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.