2
$\begingroup$

The following graph represents the positions at Castle Dragonstone. Each edge indicates that the positions are within sight of each other. This is not transitive; i.e., you can't see all the way along a row or column; you can see only the adjacent positions.

Dragonstone castle grid

King Aerion is putting dragons in his castle. He has a condition that every position in the above graph has to be either occupied by a dragon or within the sight of a dragon. Find the smallest number of dragons that he would need in order to meet this condition.

$\endgroup$
  • $\begingroup$ Is it right to say that the goal is essential to partition the graph in subgraphs with a maximum diameter of 2 in such a way that you have the least amount of subgraphs? $\endgroup$ – Ivo Beckers Jan 26 '17 at 14:57
  • $\begingroup$ What do you mean it won't work? $\endgroup$ – Ivo Beckers Jan 26 '17 at 15:01
  • $\begingroup$ each such a subgraph has a single dragon on it then $\endgroup$ – Ivo Beckers Jan 26 '17 at 15:04
  • $\begingroup$ A 3x3 grid doesn't have diameter 2. it actually has diameter 4. to get from the topleft position to the bottomright requires 4 steps. A position with a dragon on it with all positions in its sight are allways graphs of diameter 2 $\endgroup$ – Ivo Beckers Jan 26 '17 at 15:09
  • 1
    $\begingroup$ Vertex Cover? :P $\endgroup$ – Laschet Jain Jan 27 '17 at 10:10
5
$\begingroup$

The smallest number of dragons needed is:

40

This problem boils down into finding:

The minimum vertex cover of the 13 x 13 grid-graph. Another term for minimum vertex cover is "Dominating Set". The domination number for a 13 x 13 grid graph is 40. Here is an example covering.

enter image description here
See OEIS article for the domination number

$\endgroup$
  • $\begingroup$ Damn... thought I'd got this one... +1 $\endgroup$ – Brent Hackers Jan 27 '17 at 14:08
  • $\begingroup$ @BrentHackers Your answer was great, except math. :) $\endgroup$ – LeppyR64 Jan 27 '17 at 14:28
  • $\begingroup$ Harsh... I'm Maths-phobic... $\endgroup$ – Brent Hackers Jan 27 '17 at 14:53
4
$\begingroup$

My answer:

enter image description here 43 dragons (the number 2's in diagram). The general pattern is optimal as its a tesselated cross shape (see right), resulting in 20% of squares with dragons in an infinite grid. It's optimal because every square is either a dragon or is only adjacent to one dragon. Then it's a matter of choosing a 13x13 sub-grid in this infinite tesselated grid such that the number of additional edge dragons needed (the red 2's in diagram) is minimised. Wherever you place the 13x13 subgrid, you can't get less than 9 of these, and there will always be 34 tesselated dragons.

$\endgroup$
4
$\begingroup$

I got

41

by starting at the centre and working out...

enter image description here

but I could have that wrong...

Here's a slightly better formatted picture:

![enter image description here

$\endgroup$

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.