4
$\begingroup$

Let's have a 10x10 square grid with 7 empty small squares. This grid is to be filled with skinny trominoes which have arrows at their ends (see figure 1). What is the maximum number of arrows which can point at the empty squares? You can place the 7 empty squares anywhere on the grid. Below is a 10x10 grid with 4 arrows pointing at the empty squares.

10X10 grid with empty squares and skinny trominoes

$\endgroup$
3
  • $\begingroup$ It only counts if the arrows are directly adjacent to the empty squares, then? $\endgroup$
    – Deusovi
    Oct 16 at 19:14
  • $\begingroup$ Also, do you have reason to believe there is a 'nice' logical solution here? This seems like a tricky optimization problem that doesn't necessarily have a clean deductive path. $\endgroup$
    – Deusovi
    Oct 16 at 19:15
  • $\begingroup$ The arrows point directly at the empty squares. They are numbered in the diagram. $\endgroup$ Oct 16 at 19:23
6
$\begingroup$

The maximum is

$2+1+3+4+3+4+4=21$

 1  2  2  3  3  .  4  4  5  5  
 1  1  2  3  6  6  .  4  5  7  
 8  8  .  9  6 10 10  .  7  7 
 8 11 12  9  9 10 13 14 15 15 
11 11 12 12  . 13 13 14 14 15 
16 16 17 17 18 19 20 20 21 21 
22 16 17 18 18 19 19 20 21 23 
22 22  . 24 24 25 25  . 23 23 
26 26 27 28 24 25 29 30 31 31 
26 27 27 28 28 29 29 30 30 31 

I obtained this solution via integer linear programming, with a binary decision variable $x_t$ for each of the $(10-1)^2 \cdot 4=324$ possible trominoes, a binary decision variable $y_{i,j}$ for each of the $10^2=100$ cells to indicate whether that cell is empty, and a binary decision variable $z_{t,i,j}$ to indicate whether tromino $t$ is selected and points to empty cell $(i,j)$. Let $T_{i,j}$ denote the set of trominoes that contain cell $(i,j)$. The problem is to maximize $\sum_{t,i,j} z_{t,i,j}$ subject to linear constraints: \begin{align} \sum_{t\in T_{i,j}} x_t + y_{i,j} &= 1 \tag1 \\ \sum_{i,j} y_{i,j} &=7 \tag2 \\ z_{t,i,j} &\le x_t \tag3 \\ z_{t,i,j} &\le y_{i,j} \tag4 \end{align} Constraint $(1)$ forces each cell to be covered by exactly one tetromino or to be empty. Constraint $(2)$ forces exactly $7$ cells to be empty. Constraints $(3)$ and $(4)$ enforce the logical implication $z_{t,i,j} \implies (x_t \land y_{i,j})$.

$\endgroup$
3
$\begingroup$

To kickstart,

There is a way for an empty square to be pointed by 4 arrows at once, but needs 5x5 area. Thus if there are only 4 empty squares, we can get a perfect 16 points.

But as we are given 7 empty squares,

I tried to put the empty squares on the right-bottom quadrant as the following:
enter image description here

Which gives a total of

20 points.

$\endgroup$
2
$\begingroup$

Trial answer with

20 pointing arrows; four 5x5 regions maximizing their central squares and a corner modification that allows the remaining three gaps to get a decent number of points: enter image description here

$\endgroup$
2
  • 1
    $\begingroup$ Why 21x21 instead of 10x10? $\endgroup$
    – RobPratt
    Oct 16 at 19:48
  • $\begingroup$ Easier to use gaps to show borders than play around with colorings. The program I use for most of my PSE diagrams isn't actually meant to be used for such things. $\endgroup$ Oct 17 at 6:27

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.