8
$\begingroup$

There is a space station which has several chambers and each chamber is connected with a tube.

Five mathematicians A, B, C, D, and E were gathered in a lounge of the space station.

Suddenly, E said.

E: Oh, look at this! We can see the number of people in each room from this screen. Do you see "5" indicated in the screen for this lounge?

Other four mathematicians nodded with curiosity and E continued speaking.

E: This is amazing! Twice the number of people in each room is equal to the sum of people in adjacent rooms. For example, "2" is indicated for the room which is adjacent to the room with one people in it. All rooms have this property.

Mathematicians started to generalize this phenomenon.

A: Is this also possible if you rearrange people?

B: I don't think this works if we rearrange. How about increasing or decreasing the number of people?

C: What if the space station has different structure?

D: Is there any mathematical meaning with this phenomenon?

Here is the question. How any people are in the space station?

$\endgroup$
  • $\begingroup$ When you say that all the chambers are connected with tubes, what exactly do you mean? Does each room have a connection to all the other rooms? Does each room have a connection to two other rooms, the ones to its right and left, and all the rooms are arranged in a line? $\endgroup$ – Kevin - Reinstate Monica Feb 18 '15 at 0:38
5
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

There are 30 people in the space station.

We know, from the mathematician's statement, that there is a room with 1 person, adjacent to a room with 2 people in it. We also know, from the presence of the mathematicians in the lounge, that there is at least one room with 5 people in it.

The known 2-person room must have 4 people in the rooms adjacent, and it already has an adjacent room with one person, so another adjoining chamber can have at most 3 people. The same logic dictates that there is a 4-person chamber next to that, and then the 5-person chamber next.

From there, we want the station to have an end. It cannot terminate right next to the 5, because that would mean having 2.5 people in a room, which would imply bigger problems than the little puzzle that our mathematicians are having. So the only option is a room with 6 people. This room, in turn, must have 12 people in adjacent rooms, which leaves 7 outside of the lounge. A room with 3 people could go next to this room and have no other connections, which leaves another room with 4 people. A chamber with 2 people next to that leaves all rooms meeting the conditions, with the station laid out like this:

  1-2-3-4-5-6-4-2
            |
            3

Alternate Answer:
The space station contains a countably infinite amount of people (maybe it's where these dwarves are being imprisoned). The first room, as above, has 1 person and is adjacent to a room with 2 people. After that, each room has one more person in it than the preceding room. Then the $n$th room has $n$ people, and is between chambers with $n-1$ and $n+1$ people, for a total of $2n$ people in adjacent rooms.

$\endgroup$
  • $\begingroup$ spoiler tags plz $\endgroup$ – Josh Feb 17 '15 at 20:05
  • $\begingroup$ There can not be an infinite number of people because the mathematician asks if you can increase or decrease the number of people. One does not simply decrease an infinite population. $\endgroup$ – corsiKa Feb 18 '15 at 19:06
  • $\begingroup$ @corsiKa Well, that depends on what you mean by "decrease". You can certainly take people away from the space station, even if the cardinality will stay the same. On the other hand, the mathematicians could simply cut off the next room---then the population goes from infinite to 15! $\endgroup$ – KSmarts Feb 18 '15 at 22:46
  • $\begingroup$ Good one, but this isn't as rigorous as the accepted answer. For example, the 2-person room might be connected to 3 other 1-person rooms instead of having another adjoining chamber with 3 people. $\endgroup$ – justhalf Sep 19 '16 at 5:03

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.