2
$\begingroup$

Is it possible to place $n$ sets of five free tetrominoes on a $K \times K$ square grid, such that:

  • No two tetrominoes overlap.
  • Tetrominoes can be rotated or flipped.
  • Every row, column and two main diagonals contain the same number of cells covered by a tetromino.

What are the smallest positive $n$ and $K$ for which this is possible?

$\endgroup$
5
  • $\begingroup$ I have a solution, but it has a large $n$. Hopefully that can be reduced. $\endgroup$ Commented Mar 17, 2022 at 14:11
  • $\begingroup$ Just to clarify, the square grid can be arbitrary size? (independent of n). $\endgroup$
    – hexomino
    Commented Mar 17, 2022 at 14:30
  • $\begingroup$ What is the smallest positive n and K for which this is possible. $\endgroup$
    – Florian F
    Commented Mar 18, 2022 at 12:09
  • $\begingroup$ @DmitryKamenetsky just curious: how large was the n in your solution? $\endgroup$
    – Oliphaunt
    Commented Mar 21, 2022 at 9:48
  • 1
    $\begingroup$ @Oliphaunt like 8, so it is not even worth discussing. $\endgroup$ Commented Mar 21, 2022 at 10:03

1 Answer 1

2
+50
$\begingroup$

I believe this does the trick:

n=2, k=10
Each row, column and main diagonal has 4 cells covered.
enter image description here
Perhaps this can be improved, with the same tetrominos covering 5 cells per row/column/diagonal on an 8x8 square grid.

And with a bit of programming, we find this:

n=2, k=8
Each row, column and main diagonal has 5 cells covered.
enter image description here
This is just one of several hundred solutions with the two square tetrominoes together in the top left corner. There are no doubt thousands of other solutions, but I did not optimize the search to enumerate them within any reasonable timeframe.

$\endgroup$
8
  • $\begingroup$ That's a great solution! $\endgroup$ Commented Mar 18, 2022 at 1:48
  • $\begingroup$ What about n=1 and K=5? Can we show that it's impossible? $\endgroup$ Commented Mar 18, 2022 at 2:08
  • 3
    $\begingroup$ A standard parity argument shows that an n=5,k=10 filled grid is impossible. (With checkerboard colouring, all but the T tetromino cover two black and two white squares each. So you need your five T tetrominos to cover the remaining 10 black + 10 white squares, which isn't possible when each covers 1 black + 3 white or 3 black + 1 white) $\endgroup$
    – fljx
    Commented Mar 18, 2022 at 9:01
  • 1
    $\begingroup$ I have ruled out the n=1, k=5 case by essentially trying all possibilities for where the holes are. I don't have a neat argument for impossibility, though some are ruled out by a similar parity argument as above. $\endgroup$ Commented Mar 18, 2022 at 12:54
  • 1
    $\begingroup$ @DanielMathias you total legend! Well that saves me from coding it up :) $\endgroup$ Commented Mar 20, 2022 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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