8
$\begingroup$

There are $7$ gangs in (a greatly simplified version of) Los Angeles. Each of them claims half of Los Angeles as territory. Let's say a place is "hot" if a majority of gangs claim it. How small can the fraction of LA which is hot be?

As usual, you should justify your answer (give an example of a territory layout which achieves minimal hotness, and prove that every possible layout is at least as hot).

$\endgroup$
8
$\begingroup$

There are 35 possible combinations of 3 gangs, and each gang is in 15 of them. If all seven gangs claim $\frac18$ of the city and each combination of 3 claims $\frac1{40} (=\frac78 \times \frac1{35})$, then each gang has $\frac12 (=\frac18 + \frac{15}{40})$ of the city and $\boxed{\frac18}$ of the city is hot.

This is optimal. Any hot area of the city can be claimed by at most 7 gangs, and any non-hot area of the city can be claimed by at most 3 gangs. The total claimed area is $\frac72$ times the area of the city. If the hot area is $x$ and the area of the city is 1, the total claimed area is at most $7x+3(1-x)=4x+3$. If $x$ is less than $\frac18$, then this is less than $\frac72$, so it is impossible for less than $\frac18$ of the city to be hot.

$\endgroup$
  • 1
    $\begingroup$ bingo, nicely said, and quickly done! $\endgroup$ – Mike Earnest May 11 '15 at 0:04
  • 1
    $\begingroup$ Another example: divide the city into eights, numbered 0 thru 7. Every gang claims octant number 7. Gang number also $k$ claims the octants numbered $k,k+1$ and $k+2$ (mod 7). $\endgroup$ – Mike Earnest May 11 '15 at 4:32
0
$\begingroup$

Initially I thought the answer was 1/2 but then I came up with this:

1/4 of town can be hot (it turns out that isn't the minimum but is worth exploring)

There are seven gangs a,b,c,d,e,f and g.

If the town is divided into quarters each gang could take 2 of the quarters as follows:

NW :

abcdefg

NE:

abc

SW:

def

SE:

g

It gets better than that if the town is divided into eighths and each gang occupies 4/8.

NW:

abcdefg

N:

abc

W:

abc

NE:

abc

E:

def

SE:

deg

S:

dfg

SW:

gef

Other combinations are valid but the minimum hot area of town is:

1/8

$\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.