One solution:
1 - 2 - 3 - 4 - 5 - 6 - 3
\
4 - 2
For a total of 30. I'm not convinced it's the only solution- perhaps I'm missing some constraints implied by the flavour text. The ones I'm working from:
- There's a 5 room
- There's a 2 room adjacent to a 1 room
- All rooms are reachable from all others
Okay, let's try to show that going with the above conditions + that there is a finite number of rooms, this solution is unique.
So, first, let's talk about the idea of a "chain", of form:
1 - 2 - 3 - ... - (N-1) - N - ?
How can we break out of a chain like this? Once we have a room with N people connected to a room with N-1, to break out of the chain we need to connect more rooms to it following these conditions:
- The sum of people in the remaining adjacent rooms is N+1
- None of the adjacent rooms has < N/2 people in it (otherwise that room would have more than double its population in its own adjacent rooms).
- As a result of the above, none of the adjacent rooms can have more than N+1 - N/2 = N/2 + 1 people.
From this, it's clear that the only solution (for N > 2) is to have two rooms splitting off, one with N/2 people, one with N/2 + 1. So let's update:
1 - 2 - 3 - ... - (N-1) - N - (N/2)
\
(N/2 + 1) - ?
What connects to the (N/2 + 1) room? Well it needs a total of N + 2 adjacent, but it already has the N next to it, so it needs 2 more. So it can only be two 1 rooms or one 2 room.
That means the maximum in the ? room is 2. But that constrains us that N/2 + 1 must be <= 4, otherwise the 2 room would have more than 4 adjacent to it. So from that we get N <= 6.
Great! What more constraints can we put on it? Well, the need for rooms to have N/2 and N/2 + 1 people means N must be even. So now we know a chain starting at 1 can only get to 2, 4 or 6 for it to ever end. Let's call that Lemma 1 for now.
Second observation is for a situation like this:
... - N - M - ?
Assume the N is fully joined up (has the correct number of people in its adjacent rooms). And take M < N. The observation here is simply that any further rooms connected to M must be of size less than M:
... - N - M - P - ?
\
...
So now P < M, which means that any further rooms connected to P must be of size less than P. This can be extended indefinitely. In other words, if you start from a room and walk through a connection to a smaller room, and keep walking until you hit a dead end, every connection you take will always be taking you to a smaller room than the one you were just in. Let's call that Lemma 2.
Putting it together, we're starting from a 1 - 2 chain and trying to create a network that gets to 5, but doesn't go on forever. By Lemma 1, our options are to get out of that chain at 2, 4 or 6. But we can't get out of the chain at 2 or 4 because that would involve connecting to a smaller room, and as Lemma 2 tells us, that would mean 4 would be the largest room. So getting out at 6 is the only option, giving us the solution at the top, and demonstrating that it's unique.
