10
$\begingroup$

What is the minimum number of 1×3 tiles that can be put on a 5×5 table so that no more 1×3 tiles can be put on it?

Borders of a tiles are parallel to sides of the table.

It is 5 but I can not prove that if we put 4 tiles there is still room for one more.

Improve this question
$\endgroup$
2
  • $\begingroup$ Did you find this problem from somewhere else, or is it original? $\endgroup$
    – HTM
    Commented Apr 4, 2021 at 20:55
  • 2
    $\begingroup$ Original, but I don't think it is hard to think about it after you see a thousand of souch problems. @HTM $\endgroup$
    – nonuser
    Commented Apr 4, 2021 at 21:00

5 Answers 5

Reset to default
9
$\begingroup$

Assuming you mean that the tiles must consist of grid squares, this is the independent domination number in a graph with one node per tromino and an edge between each pair of conflicting trominoes. You can solve the problem via integer linear programming, as shown in my answer for $1 \times 4$ in an $n \times n$ grid.

Unfortunately, the linear programming bound of this formulation for your instance is $4$, so the LP relaxation does not immediately yield an optimality certificate.

See also OEIS A226918.

Improve this answer
$\endgroup$
23
$\begingroup$

UPDATE 2: To put OP out of their misery find now at the very bottom of this post an answer to what they probably mean.

UPDATE: OP has changed the rules, so this is no longer valid, but see bottom of this post for an answer to the modified question which I assume is still not what OP has in mind.

I say it is

2.

"Proof":


enter image description here

With the new rules the answer is

3.

"Proof":

enter image description here

If we require tiles to be on grid then the answer is

5.

Proof:

We have to cover at least one square of each 3x1 subgrid, in particular
enter image description here
the four shaded subgrids. No tile can overlap with more than one of those. So we need at least one for each shaded subgrid.

We now show that we need one additional tile. Indeed, we also need to cover each row and each column of the central 3x3 subgrid. As the 4 so far allocated can each cover at most one row and two columns or one column and two rows, at least two of them must "point inside" (not straddle the edge of the table). At least one must therefore be off-centre:
enter image description here
On the larger (right in example) side we have another 3x3 subgrid which cannot be covered without adding a fifth tile.

Almost forgot (thanks @justhalf):

5 is sufficient:
enter image description here

Improve this answer
$\endgroup$
19
  • 4
    $\begingroup$ @Greedoid: The relative sizes of the table and tiles is specified. $\endgroup$
    – Ross Millikan
    Commented Apr 4, 2021 at 15:18
  • 3
    $\begingroup$ @Greedoid: the table is $5 \times 5$ and the tiles are $1 \times 3$, presumably in the same units. $\endgroup$
    – Ross Millikan
    Commented Apr 4, 2021 at 15:22
  • 7
    $\begingroup$ Well, until 15 minutes ago it wasn't specified. But to be fair, this seems to be a joke answer. $\endgroup$
    – justhalf
    Commented Apr 4, 2021 at 15:41
  • 2
    $\begingroup$ "I give are within how a reasonable person could understand the question as it stands or stood. It's not even lateral thinking, just plain English." right. That's a person doing lateral thinking would say. =p $\endgroup$
    – justhalf
    Commented Apr 5, 2021 at 2:55
  • 3
    $\begingroup$ @smci I'm sorry but I'm really not buying this. Natural language is not maths there are lots of implied, understood and default things. No one in their right mind could reasonably assume that cutting tiles was meant to be allowed based on how the question is posed. $\endgroup$
    – loopy walt
    Commented Apr 5, 2021 at 5:16
9
$\begingroup$

Assume you manage to solve the problem with four tiles only.

  • If there is no horizontal tiles, you cover at most four columns, hence one column is still free
  • If there is exactly one horizontal tile, there are four potential positions for parallel tiles in the same three columns, and it takes at least two of the vertical tiles to block these. Then the last vertical tile can block only one of the two remaining columns
  • If there are exactly two horizontal and two vertical tiles, and neither of the horizontal tiles is in the top or bottom row, then no vertical tile can block an additional horizontal tile in the top/bottom row in the same columns as the nearest given horizontal tile.
  • Exploiting symmetry, we are left with: Two horizontal tails with wlog one of them in the top row and two vertical tiles with one of them in the left column. That is, one horizontal and one vertical tile shall block the remaining $4\times 4$ board - but they can't: The vertical tile would have to be placed in the (at least) one column not covered by the horizontal one and vice versa.
Improve this answer
$\endgroup$
1
$\begingroup$

I'd like to give an alternative answer in the style of Hagen von Eitzen.

  • If there is a horizontal blocking tile on row 3, then there are 2 horizontal tiles aligned above and 2 aligned below that can only be blocked by horizontal tiles. Covering all these requires 5 blocking tiles.
  • If there is a horizontal blocking tile on line 2, the same tile just above can only be covered by another horizontal blocking tile. And there is a row of 5 vertical tiles below that cannot be covered by just 2 blocking tiles, unless these are horizontal. But if they are horizontal you have 4 horizontal blocking tiles and they don't cover all rows. You need a fifth one.
  • In the remaining case, by symmetry, you can only have blocking tiles around the border. But then the central 3x3 square is not covered.

That 5 is sufficient has been shown already.

Improve this answer
$\endgroup$
-3
$\begingroup$

The permutations of X linear tile placements in Y symmetrical array grid depends on the qty of Y-X combinations >= X to determine the minimum qty of X tiles in Y array.

4x X=3 on a Y=5 2D array will never block insertion of another 1x3 tile without straddling.

Many solutions exist. The proof requires permutation simplification.

Here’s another solution.

enter image description here

Improve this answer
$\endgroup$
6
  • 4
    $\begingroup$ This area argument is not correct. Consider $1 \times 3$ tiles on a $1 \times 7$ board. One tile suffices even though its area is $<50\%$. $\endgroup$
    – RobPratt
    Commented Apr 6, 2021 at 15:25
  • $\begingroup$ I shudda specified my assumption of a symmetrical 2D grid and tile >1 area $\endgroup$
    – Tony Stewart EE75
    Commented Apr 6, 2021 at 15:41
  • 1
    $\begingroup$ A single 3x3 tile suffices to block a 5x5 or 7x7 grid, again showing that the 50% area argument is not generally true on 2D grids. $\endgroup$
    – Jaap Scherphuis
    Commented Apr 6, 2021 at 15:49
  • $\begingroup$ Crap, I”lol have to guess at another formula $\endgroup$
    – Tony Stewart EE75
    Commented Apr 6, 2021 at 18:00
  • $\begingroup$ Another proposition created... $\endgroup$
    – Tony Stewart EE75
    Commented Apr 6, 2021 at 18:07

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