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?

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ That's a great solution! $\endgroup$
    – Dmitry Kamenetsky
    Mar 18, 2022 at 1:48
  • $\begingroup$ What about n=1 and K=5? Can we show that it's impossible? $\endgroup$
    – Dmitry Kamenetsky
    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
    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$
    – Jaap Scherphuis
    Mar 18, 2022 at 12:54
  • 1
    $\begingroup$ @DanielMathias you total legend! Well that saves me from coding it up :) $\endgroup$
    – Dmitry Kamenetsky
    Mar 20, 2022 at 14:10

Your Answer

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

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