8
$\begingroup$

The diagram below shows the street map of a city. If three police officers are to be positioned at street corners so that any point on any street can be seen by at least one officer, what are the letter codes of these street corners?

Diagram for above question

I took combinations of all letters (positions) as 11C3 = 165; such as (A,B,C),(A,B,D),(A,B,E),...and I am trying each combination individually.

But, this method is too long & tedious. Is there a smarter way of solving this puzzle problem?

Improve this question
$\endgroup$
2
  • $\begingroup$ The standard way of writing the choose operation is ${n}\choose{k}$ (MathJax code: $ {n}\choose{k} $). $\endgroup$
    – jpmc26
    Jun 25, 2018 at 23:11
  • 1
    $\begingroup$ @jpmc26 for single variables, braces {} is unecessary. So, $n\choose k$ is also formatted from $n\choose k$ (or even \binom {n}{k} or \binom nk). $\endgroup$
    – Mr Pie
    Jul 13, 2018 at 6:49

5 Answers 5

Reset to default
3
$\begingroup$

The answer is

{H G B}

How I got it, with no guessing or enumeration:

There are a total of 8 streets to be observed. No matter where an officer is placed, they can observe 3 or 2 streets. By pigeonhole principal, at least two officers must observe 3 streets, meaning at least two of the four positions C, H, F, and G. Each of these positions observes a street not observed by any of the others, so we know that while {C F G H} is a solution, no subset of any three of them is. So our solution must contain two and only two of these positions. Any two of these positions will observe 5 or 6 streets. If only 5 are observed, we need another position that can see 3. So we know our solution contains a subset of {C F G H} which observes 6 streets, meaning the two positions of that subset cannot see each other. This takes out both C and F since they each see the other three, leaving {H G} as part of our solution. Marking out the streets those two observe, we're left with the streets AD and BI, which intersect at B. Therefore the answer must be {H G B}.

Side note:

The stipulation that the officers be placed at intersections is not necessary, since the above logic works if we assume officers can observe 3, 2, or 1 street(s).

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ They could also observe 3 streets from C, so you should probably explain why that possibility can be ignored. $\endgroup$
    – Bass
    Jun 26, 2018 at 6:40
  • $\begingroup$ Good point. It was fixable though. Answer updated. $\endgroup$
    – sgriffin
    Jun 28, 2018 at 16:05
18
$\begingroup$

The answer is

G,H and B.

since

Each officer can only watch 1 horizontal line, 1 vertical line and 0, 1 or 2 diagonal. So they must be on separate horizontal and vertical lines and they cannot be on C or K because they do not cover any vertical lines. So one must be on G (and thus not on D, E, F or J). So one must be on H (and thus neither on A or I). So there is only B left and it covers it all.

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

They would be

H, B and G.

This follows from the shape of the blocks

There are three parallel streets in the north-south-direction, and similarly, three parallel ones in the east-west direction.
It's impossible to see a parallel street from another parallel street, so the policemen must be on the corners of the 3x3 grid, so that no two policemen see each other

The only such configuration that also covers the oblique streets is the one mentioned above.

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

The answer is

G, B, and H

I got my answer in a different way however, maybe it only works for this particular puzzle but maybe not

I thought of it a bit like a sudoku puzzle, you don't want an officer on the same line, horizontal, vertical or diagonal, as another officer. This should give the greatest coverage, but like a sudoku you can't just put them anywhere so just start with the greatest lines attached to each point and work backwards

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Welcome to Puzzling.SE, Do take the tour to familiarize yourself with the site. Moreover the answer which you've submitted is already given by someone. So its good to have a look on the previous answer before submitting yours just to make sure that there is no duplicacy. $\endgroup$
    – Maniraj
    Jun 25, 2018 at 11:43
0
$\begingroup$

C and H cover all corners...

The question didn't say that the officers had to be out of sight of each other.

If it must be three, then C and H, plus another one on any other

If they must be out of sight of each other,

C and E, plus either I or J

Improve this answer
$\endgroup$
3
  • 4
    $\begingroup$ This only covers the intersections, the premise is 'any point on any street' $\endgroup$
    – Sconibulus
    Jun 25, 2018 at 12:46
  • 2
    $\begingroup$ C and H cover all corners, but not all the streets ( [DG], [GJ], [BF], [FI], [EF] and [FG] aren't covered). $\endgroup$
    – Dorian Fusco
    Jun 25, 2018 at 12:47
  • $\begingroup$ Understood, my bad :) $\endgroup$
    – horsethorn
    Jun 25, 2018 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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