10
$\begingroup$

Alice and Bob were playing Oh-Tetris-Oh!, when they decided that every game must be a draw (played intelligently).

Can you prove this?

(Oh yes, the rules: A $10\times10$ grid, you can pick any Tetris piece you like from an infinite pool, into any position fully on the grid with no overlapping. The first player to make a horizontal line wins.)

Improve this question
$\endgroup$
3
  • $\begingroup$ Are they only playing to get a draw? If so, then Alice plays only on the left and Bob plays only on the right. It will always end Up in a draw. $\endgroup$
    – Alain Remillard
    Commented Jan 30, 2020 at 3:37
  • 3
    $\begingroup$ Do the players have different colours? And if yes, do you need to make a line in your own color? Or is it just enough to make a line without any empty spaces in it, no matter who put which piece? $\endgroup$
    – mihomir
    Commented Jan 30, 2020 at 10:18
  • $\begingroup$ @mihomir; Orignally, it was the second one. But having your own colour makes sense, and also I suppose easier to prove it's always a draw. $\endgroup$
    – JMP
    Commented Jan 30, 2020 at 10:26

1 Answer 1

Reset to default
4
$\begingroup$

If Alice can win, Bob should attempt to force a draw. If Bob can win, Alice should attempt to force a draw. So long as either player can force a draw, the game must end in a draw. Either player can indeed force a draw by making every line unable to be completed. You can use the "L" pieces along the edge of the board to make a 1x2 or 2x1 "nook" of empty space than cannot ever be filled in, making it impossible to complete that line (or two lines). There is no way to block the edge of the board to prevent this from happening, since if you put a piece there, it becomes the new board edge against which a "nook" can be created. Either player is able to create an unfillable hole on every line, making it impossible to complete any line, and forcing the game to end in a draw.

EDIT: I think this proof is a little incomplete, since unlike Tetris, the grid doesn't have to fill from the bottom. If you put an L piece like a 7 in the bottom left corner, for example, the opposition could attempt to complete Line 3, but there's not a very obvious way to orphan any Line 3 squares in one move if Lines 1 and 2 are mostly empty.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I can see how to make a nook on the top two lines and the bottom two lines, but the next player can put an I horizontally on another row. I you try to make a nook the other player can fill it with another L. $\endgroup$
    – Ross Millikan
    Commented Jan 29, 2020 at 21:54
  • 1
    $\begingroup$ You could keep stacking L pieces on top or below one another in the left/rightmost columns to block 2 out of 3 lines with every piece, but the tricky part is ensuring you can block that third line somewhere else. I think there's a way to either force an empty square, or force an empty but unplayable square that could be filled in but would let the opponent win, although I'm not sure how to show that with the interaction between rows. $\endgroup$
    – Nuclear Hoagie
    Commented Jan 29, 2020 at 22:01
  • $\begingroup$ You can block a line by placing a T tetromino, the stem on the line and the crossbar on a line next to it. It is impossible for the other player to fill both squares on either side of the stem in one move, so as soon as he fills one you can surround the other to make the line unfillable. In this way you can block any particular line, but it is still unclear to me how much the opponent's moves can interfere with blocking the other lines. This technique is probably sufficient to be able to block every third line, but I don't know how to prove that. $\endgroup$
    – Jaap Scherphuis
    Commented Jan 30, 2020 at 15:12

Not the answer you're looking for? Browse other questions tagged or ask your own question.