On Fri, 20 Jun 2003, Hugh Everett wrote:
Dean Hickerson suggested the game: Player 1 chooses a tetromino, and player 2 then places it according to the rules of tetris (any sequence of rotate, left, right, down). With optimum strategy, can Player 1 force the board to fill?
This is the usual game of Tetris, except that in normal Tetris, player 1 is "nature" in the sense that it plays stochastically. [See Christos Papadimitriou's paper "Games Against Nature".] It is known that nature can foil player 2, with some simple distributions on pieces. This result implies what you want, if you allow randomized strategies for player 1. There are also deterministic strategies, e.g., alternating between Z and S eventually dooms player 2 for boards of width 2n for odd n. Here are the references: John Brzustowski. Can you win at Tetris? Master's thesis, University of British Columbia, 1992. Heidi Burgiel. How to lose at Tetris. Mathematical Gazette, July 1997. See the bottom of page 3 of this paper: http://theory.lcs.mit.edu/~edemaine/papers/Tetris_COCOON2003/ Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/