11
$\begingroup$

This is follow-up question to All (red and blue) roads lead to Rome

Eight cities lie in a kingdom, with Rome at the center of power.

Every morning, the Emperor shouts a sequence of colors from his balcony. Every messenger in the kingdom obeys blindly, moving from city to city, taking a Red road whenever "Red" is called, and a Blue road whenever "Blue" is called. The Emperor's goal is to ensure that, no matter which city a messenger starts in, they all end up in Rome at the exact same time when the sequence ends.

The Rules of the Kingdom:

  1. There are exactly 8 cities (Rome + 7 others).
  2. Every city has exactly two one-way exits: one Red road and one Blue road.
  3. A road cannot leave a city and immediately return to that same city.
  4. No city may be touched by more than 4 roads in total. (Since every city has exactly 2 outgoing roads, this mathematically forces every city to have exactly 2 incoming roads as well).

Design a valid road network for 8 cities and find the shortest possible sequence of colors the Emperor can shout to guarantee every messenger ends up in Rome.

What is your road map, and what is the shortest command?

If this question was asked for 4 cities including Rome:

enter image description here

BRB

would be the answer.

Here is the applet where you can play the game!

EMPEROR'S COMMAND GAMEPLAY (this is not perfect app)

Improve this question
$\endgroup$
2
  • $\begingroup$ did the given example change? $\endgroup$ Commented yesterday
  • 1
    $\begingroup$ @Someone the given example is topologically the same as before but Oray updated the diagram to make adjacencies more obvious. $\endgroup$ Commented yesterday

3 Answers 3

Reset to default
15
$\begingroup$

It's possible in

3 moves, as follows:

picture of graph of cities

The shouts for this one are RED, RED, BLUE.

This is provably optimal: you cannot have more than two groups of messengers merge into a single group, so after each shout, the number of groups is at least half of what it was before.

I found this particular solution by starting with this layout, and adding the remaining unused arrows in a way that would make them fit:

layout with unnecessary arrows removed

Improve this answer
$\endgroup$
1
  • $\begingroup$ good job! right one! $\endgroup$ Commented 21 hours ago
7
$\begingroup$

Road map

All messengers will be in Roma with "RBRB"

Improve this answer
New contributor
Burcu is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
7
  • $\begingroup$ Welcome to Puzzling. This is worse than @Deusovi's answer from an hour ago -- I don't see a point to posting a strictly worse answer to an optimization question. Especially as the prior answer already goes into detail about its thought process, so there's not even that to improve upon. $\endgroup$ Commented yesterday
  • 5
    $\begingroup$ @bobble That feels unfair against a new member. Who knows how long they spent coming up with this? The votes will reward the better answer. $\endgroup$ Commented yesterday
  • 6
    $\begingroup$ @bobble Fair enough, but this puzzle took 4 hours for even the best answer to arrive. This answer only took 5, it's not a "late answer". Feels mean to attack a literal newcomer with 1 rep for that, like they know all the rules. If I were Bercu, I'd never come back here. $\endgroup$ Commented yesterday
  • 2
    $\begingroup$ @Burcu - this happens a lot on all of the Stack Exchange network. Other people can be posting things while you're busy editing your answer. Happens all the time. I think your answer is good - not optimal, and won't get a tick, but worth seeing. $\endgroup$ Commented yesterday
  • 4
    $\begingroup$ Guys sorry, my bad! I was so focused on solving the puzzle for fun that I didn't see the reply from @Deusovi (congrats!) since I hit post. Definitely a rookie mistake on my part! I can delete it, if it is necessary. $\endgroup$ Commented yesterday
4
$\begingroup$

@Deusovi's bound is achievable for all $n>2$, except in the case of $n=4$.

Proof of latter claim:

The two shouts cannot be the same (W.L.O.G. RR), because Rome's messenger must take a red road (to A, say) and then another red road back, but then A's messenger will also end up at A.
So the two shouts are different, and W.L.O.G they are RB. As each city can only have up to 2 messengers after R, Rome has two blue roads leading in, say from cities B and C. Every city must have a red road leading into B or C, but this exhausts the roads leading out from B and C, so the roads leading into A must come from Rome and A, a contradiction.

Proof of former claim:

The answers to the linked question can solve $n=3$ in 2 shouts.
For $n>4$, we have the following general construction:
- Number the cities from $1$ to $n$, with $1$ representing Rome.
- Lay blue roads from $n$ and $n-1$ to $1$, from $k$ to $k+1$, for $1 \leq k \leq \lfloor\frac{n-1}{2}\rfloor$, and from $k+\lfloor\frac{n-1}{2}\rfloor$ to $k+1$ for $1 \leq k \leq \lfloor\frac{n-2}{2}\rfloor$.
- Lay red roads from $n-3$ and $n-1$ to $n$, from $n-2$ and $n$ to $n-1$, and from $k$ to $\lceil\frac{n+k}{2}\rceil$ for all $k < n-3$.
Example adjacency matrices for 9 and 10 cities, respectively (with diagonal drawn for clarity):
Example graphs on 9 and 10 cities
If there are more than two cities with messengers, a shout of R divides this number in half, rounding up. By @Deusovi's argument, this is best possible. Once messengers are concentrated in $n-1$ and $n$, a shout of B brings them to Rome.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.