2

You are in charge of giving land to different numbers of individuals and below is how you have divided the land into 10 areas.

enter image description here

You can assign any number of people from 1 to $n$ to live in each area under these conditions, that no neighbouring areas have the same difference in number of people living in them and no area is allowed the same number of people living there as another area.

Neighbouring areas are defined as sharing at least one horizontal or vertical border, diagonally touching doesn't count.

What is the lowest value of $n$ so that the conditions are met? Proof it is lowest.

So from the drawing you can see there are 14 borders which means the minimum value for n=15 so you can have differenced 1,2,3...14. This is as far as I have got. I can allocate numbers to the rest so that it works but I don't know how to go about proving it is the lowest. I haven't managed to get to n=15 otherwise I could have proven it.

Asaf Karagila
  • 393,674
Ben Franks
  • 423

1 Answers1

1

The first condition (as interpreted by the OP) tells us that each border must have a distinct difference. Let's draw a graph with a vertex for each region and an edge between two vertices if they share a border.

Insert math 1

Since our graph has $m=14$ edges, there are $14$ borders and so we require $n\ge15$.

A graph with $m$ edges is graceful if there exists a labeling of its vertices with some subset of $\{0,\ldots,m\}$ such that no two vertices share a label, and such that each edge is uniquely identified by the absolute difference between its endpoints. In Rosa's original paper he showed that an Eulerian graph whose number of edges $m\equiv 1,2\pmod{4}\,\,$ is not graceful. Observe that our graph that models our map is not graceful as it is Eulerian with $14\equiv2\pmod{4}\,\,$ edges.

If we could find a way to label our vertices from $\{1,\ldots,15\}$ such that each edge takes on a unique value $\{1,\ldots,14\}$ as the absolute difference of their endpoints, then we could subtract $1$ from each of the vertices and arrive at a vertex labeling from $\{0,\ldots,14\}$ such that each edge takes on a unique value $\{1,\ldots,14\}$ as the absolute difference of their endpoints, a contradiction. Thus $n>15$.

If we let $n=16$ then we can do the following:

Insert math 2

However, the way the first condition is worded is a bit ambiguous. If you interpret it to mean that the edge coloring be proper, then $n=10$ suffices because the second condition implies that $n\ge 10$ and we can implement a vertex assignment that induces a proper edge coloring as follows:

enter image description here

Laars Helenius
  • 7,965
  • 1
  • 23
  • 35
  • No you are not allowed to have the same difference in number of people between two neighbouring areas across the whole puzzle. So if for instance the difference between area 1 and area 2 is $x$ you cannot have $x$ difference feature again. – Ben Franks Dec 21 '16 at 21:34
  • I understand what you are saying, but the condition is worded poorly, as it can be interpreted multiple ways. I would suggest clarifying the condition in the original question. – Laars Helenius Dec 21 '16 at 22:48
  • 1
    The way to solve this is by using @Laars' excellent graph representation, and running a backtrack algorithm across the edges, Start by assigning 14 as that has only two possibilities for the vertex values. – user383778 Dec 22 '16 at 00:03
  • OK. I think I've covered all the bases on this one now. – Laars Helenius Dec 22 '16 at 05:59