8
$\begingroup$

How many blocks can you pass through at most in a 10 × 10 grid.

The rules are:

  1. You cannot go over a line
  2. You cannot lift the pencil
  3. You cannot allow the blocks you have passed through to make a 2×2 block of adjacent boxes

I think it would be 71.

enter image description here

$\endgroup$
2
  • 1
    $\begingroup$ It can be 75 in a sense that 100-(5*5) $\endgroup$ Mar 23 '20 at 21:09
  • 2
    $\begingroup$ Excuse my humor - but you violated your own rules (no lifting the pencil - I see it happen at least 2 times ) g $\endgroup$
    – eagle275
    Mar 24 '20 at 13:16
9
$\begingroup$

I solved the problem via integer linear programming, and

71 is indeed optimal. Here's another optimal solution:

enter image description here

Here are optimal values for $n\times n$ grids with $n \le 10$: \begin{matrix} n &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 \\ \hline \text{maximum} &1 &3 &8 &12 &19 &25 &37 &45 &59 &71 \\ \end{matrix}

By the way, you lifted your pencil in row 1, column 4. :)

$\endgroup$
2
  • $\begingroup$ actually he lifted the pencil 2 times^^ 1 further lift in row 3 column 6 $\endgroup$
    – eagle275
    Mar 24 '20 at 13:18
  • 1
    $\begingroup$ @eagle275, that one was a little ambiguous, so I didn't want to falsely accuse. :) $\endgroup$
    – RobPratt
    Mar 24 '20 at 14:47
8
$\begingroup$

If diagonals are allowed, here is a solution with 75.
grid

$\endgroup$
2
  • 3
    $\begingroup$ OCD doesn't like your yellow dots not being all in order. $\endgroup$ Mar 23 '20 at 22:36
  • 3
    $\begingroup$ @DanielMathias It was bothering me too that I started it like that. I have updated it to have a cleaner solution. $\endgroup$ Mar 23 '20 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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