WakeUp wrote:

I got lost on your disproof of $y = 4$, so I'm not sure where you (or I) went wrong, but you can put a 4 by 4 grid of tetrominoes in the center and then fill the border with the triominoes. Here's a diagram, with G H M N as the tetrominoes. ABCCCDDD ABEEEFFF ABGGGHIJ KLMGHHIJ KLMMNHIJ KLMNNNOP QQQRRROP SSSTTTOP For (b), I think you would want to prove that the above configuration, with the $4 \times 4$ grid in the center and triominoes filling the border, is the only way, from which it should follow there are just four possibilities.

Here's an argument (essentially WakeUp's idea in the proof of a related problem) why a $4\times 4$ block of T-shaped tetrominos must be in the center of the chessboard. Three-color the chessboard in the two different ways below (attachment). In one coloring there are $22$ blues, $21$ fuchsias, and $21$ whitesand in the other coloring there are $22$ As, $21$ Bs, and $21$ Cs. A tiled triomino necessarily covers one of each color and one of each letter, so $16$ triominos cover $16$ squares of each color and of each letter. Thus the remaining $4\times 4$ block must cover $6$ blue squares and $6$ A squares (and $5$ squares for each of the other colors and for each of the other letters). This means the corners of the $4\times 4$ block must be blue As. That occurs only at the center. But why must a tiling with $4$ T-shaped tetrominos and $16$ triominos have a $4\times 4$ block of T-shaped tetrominos? I suppose with some case work we can figure out how the $4$ tetrominos must be placed keeping in mind that two of the tetrominos must cover two blue squares each, two of the (not necessarily different) tetrominos must cover two A squares each, and the four blue As must be covered.

In addition to your mistake in the $y=4$ case, I have found a flaw in your $y=1$ case as well. However, your result for $y=1$ is correct, since I have an alternate proof for this case. I don't like to quote the entire post before, but I am doing so and highlighting the portion I mentioned just to be absolutely clear what I am referencing. The line I highlighted is an incorrect statement. Indeed, place the T-tetromino on squares (e7,f7,f6,g7) of the chessboard (where a1 is lower left corner). Then we see that in all three of your colorings, this tetromino is of the form (3,1). WakeUp wrote: Call the $3\times 1$ rectangles $A$-pieces and the T-shaped tetronimoes $B$-pieces. Let there be $x$ $A$-pieces and $y$ $B$-pieces present on the board. Clearly it is a case of maximising $x$, or minimising $y$. Now $3x+4y=64$ by considering the area. Evidently, $4|x$ and $y=1\pmod{3}$ so $y\in\{1,4,7,\ldots ,16\}$. To show that $y\not= 1$, assume the contrary, and colour the board like so:

This means the sole $B$-piece either covers 2 black square and 2 white squares or 3 black squares and 1 white square. If it covers the 2 black squares and 2 white squares then this leaves 19 white squares and 41 black squares for the 20 $A$-pieces left. However, each $A$-piece covers exactly 2 black squares and 1 white squares, and thus is incapable of covering the board (the ratio of black squares:white squares needs to be 2:1). As a result, the $B$-piece must cover 3 black squares and 1 white square. This next step reminds me of this problem. Consider the board reflected both in a vertical and horizontal mirror, so that the colouring becomes:

Placing a $B$-piece so that it covers 3 black squares, 1 white square on one board means it covers 2 black squares, 2 white squares on one of the other boards. But exactly the same argument as before applies to why the $B$-piece cannot cover 2 black, 2 white on the two new boards, contradiction. Hence $y\not= 1$. Next up is $y=4$. Then $x=16$ and so the $16$ $A$-pieces occupy 16 white squares, 32 black squares. This leaves 5 white squares and 11 black squares for the 4 $B$-pieces. This can only happen in a configuration which has 1 $B$-piece covering up 2 black, 2 white while the other 3 $B$-pieces cover up 3 black, 1 white. Now the nature of these three colourings is such that in a position where a $B$-piece covers up 2 black, 2 white squares on one board, it will cover up 3 black, 1 white on the other two colourings. If the $B$-piece is in a position where it covers up 3 black, 1 white then on exactly one of the other colourings it will still cover 3 black, 1 white and will cover 2 black, 2 white on the third colouring. So, for $y=4$, on every colouring of the board, 1 $B$-piece covers up 2 black, 2 white while the other 3 $B$-pieces cover up 3 black, 1 white. Assume the $B$-pieces (let's name them $B_1,B_2,B_3,B_4$) are on one board. Assume $B_1$ covers up 2 white, 2 black on this board, while $B_2,B_2,B_4$ each cover 3 black, 1 white. Replace the board with another one. Then $B_1$ now covers 3 black, 1 white. Hence exactly one of $B_2,B_3,B_4$ becomes the sole $B$-piece covering 2 black, 2 white. We will assume $B_2$ does this. Now we replace the current board with the last (previously unused) board. Then both $B_3,B_4$ cover up 2 black, 2 white squares as they didn't on the previous two boards. This is a contradiction. So $y\not= 4$. If $y=7$ then $x=12$. These 12 $A$-pieces cover a total of 24 black squares and 12 white squares, leaving 19 black squares, 9 white squares for the 7 $B$-pieces. It is easy to prove the only way this can happen is when there are 2 $B$-pieces each covering 2 black, 2 white while 5 $B$-pieces each cover 3 black, 1 white. So on one board, let $B_1,B_2$ be the two $B$-pieces that each cover 2 black, 2 white, let the rest be called $B_3,B_4,\ldots ,B_7$. Replace the original board with another board. Then exactly two of $B_3,B_4,\ldots B_7$ now cover 2 black, 2 white since $B_1,B_2$ each now cover 3 black, 1 white. Let the two be $B_3,B_4$, without loss of generality. But then, for the final board, $B_5,B_6,B_7$ all cover 2 white, 2 black, a contradiction, since there can only be 2 such squares. If $y=10$ then $x=8$. These 8 $A$-pieces cover a total of 16 black squares, 8 white squares, leaving 27 black squares, 13 white squares for the 10 $B$-pieces. It is easy to prove that the only way this can happen is when there are 3 $B$-pieces each covering 2 black, 2 white while 7 $B$-pieces each cover 3 black, 1 white. So on one board, let $B_1,B_2,B_3$ be the three $B$-pieces that each cover 2 black, 2 white, let the rest be called $B_4,B_5,\ldots ,B_{10}$. Replace the original board with another board. Then exactly three of $B_4,B_5,\ldots B_{10}$ now cover 2 black, 2 white since $B_1,B_2,B_3$ each now cover 3 black, 1 white. Let the three be $B_4,B_5,B_6$, without loss of generality. But then, for the final board, $B_7,B_8,B_9,B_10$ all cover 2 black, 2 white, a contradiction, since there can only be 3 such squares. If $y=13$ then $x=4$. These 4 $A$-pieces cover a total of 8 black squares, 4 white squares, leaving 35 black squares, 17 white squares for the 13 $B$-pieces. It is easy to prove that the only way this can happen is when there are 4 $B$-pieces each covering 2 black, 2 white while 9 $B$-pieces each cover 3 black, 1 white. So on one board, let $B_1,B_2,B_3,B_4$ be the four $B$-pieces that each cover 2 black, 2 white, let the rest be called $B_5,B_6,\ldots ,B_{13}$. Replace the original board with another board. Then exactly four of $B_5,B_6,\ldots B_{13}$ now cover 2 black, 2 white since $B_1,B_2,B_3,B_4$ each now cover 3 black, 1 white. Let the four be $B_5,B_6,B_7,B_8$, without loss of generality. But then, for the final board, $B_9,B_{10},B_{11},B_{12},B_{13}$ all cover 2 black, 2 white, a contradiction, since there can only be 4 such squares. So the only possible value for $y$ is $y=16$, forcing $x=0$. This is in fact plausible. It is easy to tile 4 $B$-pieces so that they over a $4\times 4$ board. Do this $4$ times, forming an $8\times 8$ board, using 16 $B$-pieces. Hence the maximum value, and only value, of pieces that can be used is $16$. I haven't done part b) yet, feel free anyone to join in, the answer is at least 20, however.

Yeah, I've just deleted my post seeing as the core idea was mistaken. And it has been quoted for reference.. me@home, what was your disproof for $y=1$? I think Shu has nailed part b), albeit with a bit of casework.

a) By simple counting you need at least one tetromio, and in fact that's all you need ABCCCDDD ABEEEFFF ABGHIIIK LMGHJJJK LMGHOOOK LMNNNOTU PPPQQQTU RRRSSSTU

ocha beat me to it; after my post yesterday I found a mistake in my 'proof' of $y=1$. I used some lemmas to reduce the tiling to the tiling of a (5,5) sub-board. When I was thinking about it today, I realized one of the lemmas had a subtle mistake in the proof. The rest of my proof held up for (5,5) sub-boards, and indeed we see that any tiling involving a single tetromino is a fault-free tiling, in particular lacking any (5,5) sub-board. However, I am still in time to post part b). Suppose there exists a tiling with a single tetromino. From color analysis previously posted, and working up to symmetry, the tetromino must be placed either on the squares (e7,f7,f6,g7) or on the squares (e5,e6,e7,f6). In the former, after placing the forced triomino on squares (g4,g5,g6), we are left with two cases based on the tiling of the h8 square. Both cases yield a forced sequence of placements that end up in contradictions. In the latter, there exists a forced sequence of placements that end up in a unique tiling. Therefore, there is a unique tiling up to reflections and rotations. Obviously, ignoring reflections and rotations there are 8 such tilings. EDIT: Allow me to clarify my post. When I say a "forced sequence", I mean the following. After placing the tetromino, each remaining square on the board is covered by a single triomino. In general, there are 6 distinct triomino placements that cover a square. However, in a cluttered board many of these placements are ruled out. Let $n(s)$ denote the number of distinct triomino placements for a square $s$. When $n(s)=1$, we complete the board by placing the unique triomino covering square $s$. Then a forced sequence is an ordered set of squares $S$ such that $n(s_1)=1$ and after completing the board $n(s_2)=1$ and so on all the way to the end of $S$.

Even though we have found the "maximal" tiling, I am still interested in the remaining tilings. Using a similar method, I have found 5 unique tilings in the case $y=4$ and 1 unique tiling in the case $y=7$. (Unique means up to reflections and rotations of the chessboard) I am pretty confident that there are only 5 tilings in the $y=4$ case, but the case $y=7$ is still wide open. What do you guys think?