AoPS - Problem

Source: Centroamerican 2012, Problem 4

Tags: floor function, combinatorics unsolved, combinatorics

hatchguy

20.06.2012 23:52

Trilandia is a very unusual city. The city has the shape of an equilateral triangle of side lenght 2012. The streets divide the city into several blocks that are shaped like equilateral triangles of side lenght 1. There are streets at the border of Trilandia too. There are 6036 streets in total. The mayor wants to put sentinel sites at some intersections of the city to monitor the streets. A sentinel site can monitor every street on which it is located. What is the smallest number of sentinel sites that are required to monitor every street of Trilandia?

Attachments:

I think it's easier than CNS. With a triangle of side length $2k$, if you consider the $3k$ streets of lengths $1, 2, \ldots, k$ in each of the three orientations, you get that a different sentinel is needed for each of them, with the exception of the three streets of length $k$ which need only two between them. That gets a bound of $3k-1$. This can be constructed just by putting $k$ consecutive sentinels on each side of the triangle so each covers a street of length $1, 2, \ldots, k$ of a particular orientation. Then remove one of the sentinels covering length $k$ streets. It's not hard to verify this works. So the answer for the problem should be $3017$ ($2k = n=2012$).