Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Simple Proof of the Tetris Lamp

jackm.co.uk

Post reply on HN
Print view View original

41–50 of 90 posts

Re: The Simple Proof of the Tetris Lamp

#41

Post by [deleted] »

throwaway183839 wrote: post #38
peeters wrote: post #35

Earlier quoted context omitted.

The 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?

Theorem: 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]

Re: The Simple Proof of the Tetris Lamp

#42

Post by eterm »

nemetroid wrote: post #26
rmetzler wrote: post #25

Earlier quoted context omitted.

If 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.

Having 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.

Not 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

Re: The Simple Proof of the Tetris Lamp

#43

Post by JoshTriplett »

rmetzler wrote: post #25
rndn wrote: post #8

Earlier quoted context omitted.

Is 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.

If 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.

The 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.

Re: The Simple Proof of the Tetris Lamp

#47

Post by runn1ng »

pmelendez wrote: post #28

>"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!

http://en.wikipedia.org/wiki/File:15-puzzle-loyd.svg

:)

Re: The Simple Proof of the Tetris Lamp

#48

Post by praptak »

archagon wrote: post #24

Speaking 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-...

I 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.

Re: The Simple Proof of the Tetris Lamp

#49

Post by PhasmaFelis »

> 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.)

Post reply on HN