Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

True story: the Cambridge Maths Society, The Archimedeans, had a journal called Eureka (of course). It happily published interesting but not important bits of mathematics. One student wrote a proof of an impossible sequence for any width board. It's even impossible if you have perfect knowledge of the sequence. All you need is to drop Ss and Zs in an irrational order.

I think this got published in 1990, but I can find little evidence even if the journal's existence online.



I think you mean this one? Of course it's also possible that multiple people have published multiple proofs.

https://www.researchgate.net/publication/2347389_How_to_Lose...

The proof itself is quite self-evident: given a perfectly randomly block generator, and infinite play time, eventually you're going to produce a very long sequence of left- (or right-) facing S-blocks. Since those are impossible to eliminate (there's always one block left open on a row) eventually you lose.


This actually isn't true for modern variants of Tetris. A correct implementation of the random number generator requires that the 7 pieces be shuffled into a bag and then drawn randomly, ensuring an even distribution, and disallowing long runs without a desired piece. (Maximum of 12.) The bag is re-shuffled every 7 blocks in the sequence.

https://tetris.wiki/Tetris_Guideline

https://tetris.wiki/Random_Generator

Thus, in a game of Tetris adhering to these official guidelines, the longest sequential run of S and Z pieces would be 4, in the following sequence:

[5 Random Blocks] [Z and S in any order] [Z and S in any order] [5 Random Blocks]

I'd be very curious to see a proof of an impossible sequence which adheres to the official rules, as that would be quite a feat indeed!


In that case it would probably still be possible, but the proof would have to be found by example. It seems like an advanced version of the Eight Queens puzzle: which sequence of bags guarantees a losing board state?


>I'd be very curious to see a proof of an impossible sequence which adheres to the official rules, as that would be quite a feat indeed!

It sounds like, given enough piece previews, you can play without ever losing: http://tetris.wikia.com/wiki/Playing_forever


> [5 Random Blocks] [Z and S in any order] [Z and S in any order] [5 Random Blocks]

Any dab hands at regex out there? I think this is the regex to match, but something feels wrong about it

    (([^sz]){5}[sz]{2})([sz]{2}([^sz]){5})


Not that one. It's from 1996, the one I'm thinking of was 1993 latest and I think 1990. There was also a previous article that demonstrated that the player always won for 3-omino Tetris (not a massively interesting result).

As observed elsewhere, neither work according to official Tetris rules.


I misunderstood "board" as blackboard and thought that a Cambridge student had written a proof that, for any arbitrarily wide blackboard, there was a sequence which it was impossible to write on the board.

This seems like the sort of theorem that a college student might be inclined to prove.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: