7
$\begingroup$

What is the smallest number of cells you need to paint in an 10x10 grid, such that it contains no unpainted hexominoes? Note that a hexomino is a set of 6 adjacent cells (horizontally or vertically).

Here is a similar puzzle for pentominoes on an 8x8: 8x8 grid with no unpainted pentominoes

Good luck!

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ This doesn't appear to me like it has a natural 'path' to the solution - are you sure it does? It looks like this is best solved with programming rather than any sort of human insight. $\endgroup$
    – Deusovi ♦
    Commented Oct 13, 2019 at 17:42
  • 2
    $\begingroup$ @Deusovi This is not a logic puzzle. It does not necessarily have a single best solution, let alone a 'natural path'. The solution I have posted was found entirely with pen and paper, and I enjoyed it. It might not be optimal, but that's not the point. If you enjoy this kind of puzzle, have at it. If not, just pass it by. Your criticism seems contrary to acceptance without any real purpose. $\endgroup$
    – Daniel Mathias
    Commented Oct 13, 2019 at 18:28
  • 2
    $\begingroup$ @DanielMathias I agree that it's not a logic puzzle! But I think all questions should have some sort of 'path' to the solution, whether that's hints built into a "What Is A ___ Word™" question. As for optimality, the question literally asks for the "smallest number of cells you need" -- optimality is the whole point. And I'm not sure optimality can be found in any other way than by computer search. $\endgroup$
    – Deusovi ♦
    Commented Oct 13, 2019 at 18:31
  • 3
    $\begingroup$ @Deusovi The search (manual or otherwise) for the best solution is the point. Whether we find an optimal solution, or prove it optimal if we do, is in my opinion secondary. Not knowing if my solution is optimal will allow me to enjoy an attempt to find a better. I agree that puzzles with a specific or singular solution should have a logical path, this puzzle simply isn't in that category. $\endgroup$
    – Daniel Mathias
    Commented Oct 13, 2019 at 18:42

3 Answers 3

Reset to default
8
$\begingroup$

One very efficient way to separate areas by squares is to put them in diagonal lines. This utilises the diagonal, which is the longest dimension of the square.

Also, you can divide the plane into separate X-pentominoes (which have the maximum allowed connected area) by using diagonals of squares only.

That pentomino pattern has the annoying property that choosing any 10x10 square tends to bring in an overly paint-filled edge row. However, it's possible to "change the parity" of the pattern at one of the diagonals, which gives edges with no more than 3 painted squares on any of them.

While I have no proof that this is the best answer, the above observations give a reason to guess that this is likely to score pretty well:

enter image description here

The pattern has a total of

35 coloured squares.

EDIT: After giving it a couple of tries, any variation based on the X-pentomino seems to result in this exact solution after a couple of optimisations.

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

My best, but is it optimal?

Thirty seven painted tiles.

thirty-seven

Improve this answer
$\endgroup$
1
$\begingroup$

By using integer linear programming as in my answer to Least number of marked symbols, I found the following optimal values for $n\in\{1,\dots,10\}$: \begin{matrix} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline \min & 0 & 0 & 3 & 5 & 8 & 12 & 17 & 22 & 28 & 35 \\ \end{matrix}

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for your nice work. Please consider adding this to the OEIS. $\endgroup$
    – Dmitry Kamenetsky
    Commented Aug 27, 2020 at 1:22
  • $\begingroup$ perhaps this is related to this sequence: oeis.org/A282513 $\endgroup$
    – Dmitry Kamenetsky
    Commented Aug 30, 2020 at 10:14
  • $\begingroup$ @DmitryKamenetsky I submitted oeis.org/A337520, as well as the corresponding sequences for smaller polyominoes: oeis.org/A337501, oeis.org/A337502, oeis.org/A337503 $\endgroup$
    – RobPratt
    Commented Aug 30, 2020 at 13:52
  • $\begingroup$ That's great work! Perhaps we can add a file with all the best solutions. I've submitted a comment to A282513. It hasn't been approved yet, so should I remove it? $\endgroup$
    – Dmitry Kamenetsky
    Commented Aug 30, 2020 at 14:09

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