85 of 100: Tic Tac Sabotage

First, remove one square (colored red in this image) per column. Remove them in a zigzag fashion. Then, remove another square (colored purple) from row #2. It should take $\boxed{6}$ removed squares to block any winning line.

$\textbf{Generalization}$

Let's say we have a $3 \times m$ tic-tac-toe. Now, we are trying to generalize the minimum number of squares that need to be removed.

$Claim:$

For a $3 \times 3$ tic-tac-toe, only $3$ squares need to be removed. And, for a $3 \times m$ tic-tac-toe (where $m \neq 3$ ), the number of squares that need to be removed is $m+\lfloor{\frac{m}{3}}\rfloor$

The idea goes like this:

For $m=3$ , removing the diagonals is optimal. For $m \neq 3$ , the following process turns out to be good enough.

For every column, we need to remove 1 square. These are colored in red. So, $m$ red squares are removed. Also, we need to remove 1 square from every 3 squares in row #2. These are colored in purple. Number of purple squares is $\lfloor{\frac{m}{3}}\rfloor$ . Therefore, we need to remove $m+\lfloor{\frac{m}{3}}\rfloor$ squares in total.

[Thanks goes to @Mark Lama for helping me in this.]

In every column there has to be at least 1 unit square removed, because otherwise that specific column gives the opportunity to put three X's in it. So at least 5 unit squares must be removed. But is it possible with only 5? If you start removing 1 unit square from the first column and 1 unit square from the second column then there are two options. They are in the same row or they are not. 1) If they are in the same row then from the third column there has to be removed 2 unit squares, namely the 2 unit squares from the other two rows. 2) If they are not in the same row then it's more complicated. It depends on which unit square you have removed from the first column and also the second column. Below you see a picture of the (basically) three different options. The green unit squares are the ones you choose and the red unit squares are the ones necessary (depends on what you have chosen). So you see that sooner or later there have to be 2 unit squares removed from one column. The conclusion is that it's not possible with only 5 unit squares removed. Is it possible with 6 then? Yes.

At first, we have to remove at least one square from each of 5 columns​,.
so that, no 3 squares can be joined vertically.
THIS PROCESS MUST BE DONE IN SUCH WAY, SO THAT NO 3 SQUARES CAN BE JOINED DIAGONALLY.
As shown in the figure,
now, after this process, there is a possibility to join 3 squares horizontally in the middle row.
So to avoid this situation, we have to remove the middle most square of the middle row.
Hence, minimum number of removed squares is=(5+1)=6

As the $3 \times 5$ case has been well answered, I'd like to look at the limiting case, where the rectangle grows in both dimensions without bounds. What is the lower bound of the ratio of the total squares that have to be removed so that no connected horizontal, vertical, or diagonal sets of three squares remain? I would maintain that the minimum ratio approaches $\frac{1}{2}$ . Consider the following $16 \times 16$ array that illustrates what I believe to be the closest packed tiling of allowed squares. Allowed squares are white; squares that must be removed are blue. Clearly, in each row, half of the squares are being removed. Again, in each column, clearly half of the squares are being removed. I challenge you to find a closer packing!

I. Six boxes is possible.

But for a complete answer, we must prove that less than six is not possible.

II. To prevent a win, we need to remove at least one box in every column . Clearly, that requires a minimum of five boxes .

III. Moreover, in each row we must remove at least

• either the middle box

• or two boxes, but not on opposite edges.

The only way to do this with five boxes is as follows:

• remove box 3 (the middle box) from any row;

• remove boxes 1 and 4 from another row;

• remove boxes 2 and 5 from the remaining row.

IV. However, we must also take care of the six "long diagonal" (i.e. of three boxes in a row). Diagonals in opposite directions overlap, so in principle it seems possible to do this by removing five boxes. However, it is impossible! To see this, consider that steps II and III above leave essentially two different situations (up to mirror image):

In either case, there are two winning diagonals. It is therefore not possible to do it with five boxes.

As many solved correctly, there is a solution with 6 removals looking thus:

where X is a removal.

Can we prove that it's minimal? Easy enough, it follows from the pigeonhole principle that the minimal number is at least 5 (one removal for each column). Lets assume that there's a solution with 5 removals. As said before, each removal will occur at a distinct column, so we're covered with the columns, and left with rows and diagonals.

Without loss of generality, lets give values to columns:

So we can represent the board with a ternary sequence with length 5. For example, a board looking thus:

will be represented by the sequence 02101. While it's not necessary to use a new representation, it makes life easier.

To make a winning row impossible, we need no horizontally consecutive 3 rows without any removal. In our new representation, it means that all the three subsequences of length 3 should be made of all 3 digits. For example, let's look at the previous example board 02101. It's subsequences are 021, 210, 101. The two first meet that criterion, but the third does not, as 2 is not there. It means that there are 3 legal places in the end of the bottom row, and you can see that there is a legal win there (Three empty places in a row). Assume we want to build a board blocking all the rows. If we choose two different digits at the beginning (they must be different otherwise the first subsequence won't meet our criterion), the third digit must be the one we haven't used. Looking at the second subsequence, we see that the fourth digit must be the first one, and likewise looking at the 3rd subsequence the 5th digit is the second one. We really find here that our pattern must be periodic, and is determined by the first two digits.

For example, let's start the sequence with 02: 02???. The next one must be 1, looking at the subsequence 02?. So now we have 021??. Looking at the next subsequence 21?, we see it must be zero. Now we have 0210?, and make sure you understand why the last digit is 2.

So the two first digits determine the others, leaving us with 6 different boards: 01201,12012, 20120, 21021, 10210, 02102. They look very similar, right? You can imagine what will it look like for a 3xN board - it'll just go periodically like that forever.

Now lets talk about diagonals. A board is free of diagonal wins if any 3-subsequence shares at least one common digit with the sequences 012 and 210. In our earlier example, 02101, 210 has no common digit with the subsequence 021, thus it allows a diagonal win from bottom left to the right.

It can be seen that all possible 6 boards allow such diagonals, as they all contain a subsequence of the kind 021 or 201. Thus, It's impossible to use only 5 removals and so 6 is the minimum.

Q.E.D.

**One of the solutions I thought was this one. This prevents any 3 in a row possibilites.

Why 5 doesn't work: Let's remove 5 squares so that 3 in a row will be impossible horizontally or vertically, then prove that we can get 3 in a row diagonally.

As others observed, each column would only have one square removed. At least one row will have no more than one square removed. In that row the middle square has to be removed. That can only happen in one row, so other two rows will have to have each 2 squares removed. The square removed from the first column is in a row that needs another square removed so it's not the middle one, because that's in the row that only had one square removed. It can therefore only be the 4th square.

That means one row has squares 1 and 4 removed, one squares 2 and 5, and one just square 3. We'll put the first X into the square 3 of a row that is touching the row with square 3 removed (so either just below or just above the removed square in the middle column). If that removed square is in the middle row we do (1) otherwise we do (2).

(1) Let's put X into the middle of the top row. In the bottom row another X has to go into square 1 or 5, one of them is available because they haven't been both removed. If it's in square 1, we put the final X in the middle row in square 2. If 5 then 4. Both 2 and 4 are available in the middle row because only square 3 has been removed.

(2) The X must be In the middle row. In the other row with 2 squares removed either square 2 or square 4 has not been removed, we put the second X there. 3 in a diagonal will then be complete by putting the third X into the row where just the square 3 has been removed. It will have to go either into square 2 or into square 4 (opposite from the second X), which are both available because only square 3 has been removed.

See Tic Tac Toe Warmup in Logic > Deterministic Games.