I would be interested in learning who that friend was, and how he got to the proof.
The Simple Proof of the Tetris Lamp
81–90 of 90 posts
Re: The Simple Proof of the Tetris Lamp
#82Interesting 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.
Re: The Simple Proof of the Tetris Lamp
#83I recently read a similar case in Simon Singh's book Fermat's Enigma 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 Singh claims that Sam Lloyd created the puzzle, secretly proved it was impossible, and offered rewards to anyone who could solve it.
Re: The Simple Proof of the Tetris Lamp
#84Interesting 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.
Exactly 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.
Re: The Simple Proof of the Tetris Lamp
#85If 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.
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
I 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.
Re: The Simple Proof of the Tetris Lamp
#86Re: The Simple Proof of the Tetris Lamp
#87Re: The Simple Proof of the Tetris Lamp
#88Earlier quoted context omitted.
Yes. 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…
Minor 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 :)
"making do" -> "making due" seems to be relatively common among US English speakers, too. In British pronunciation dew
also sounds the same as due but both differ from the US "do"...
Re: The Simple Proof of the Tetris Lamp
#89Speaking 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-...
A 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.
Re: The Simple Proof of the Tetris Lamp
#90Speaking 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-...
A 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.
The 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.