2
$\begingroup$

So I found this cool problem on a math competition (from a couple years ago), and I was wondering how I should solve this. I don't remember where this problem is from, but I know it was some kind of math competition. Probably MAA or such.

Given 5 cities, and the 10 roads between them (so that every city has a road to every other city), how many ways are there to create directions for the roads such that it is always possible to get from one city to any other?

Could you guys help? I'm still struggling with this problem.

Improve this question
$\endgroup$
1
  • $\begingroup$ Ooo! Seen this problem before! Yes, this is an MAA problem...I think it's from the AIME competition. $\endgroup$
    – NL628
    Commented Mar 5, 2018 at 5:00

1 Answer 1

Reset to default
2
$\begingroup$

Here's my solution:

The first thing we notice is that

This problem will be a lot simpler if we use complementary counting to find the answer.

Using this idea, we see that there are

two possibilities that make it impossible to go from one city to another. The first one is if all roads connected to that city point away from that city. Then, there is literally no way to get to that city. Another possibility is that all roads connected to that city point towards that city. Then, there is no way to start from that city and get to any other city.

We now calculate the number of ways for this to happen:

There are $5$ cities and $10$ roads, and we are setting the direction of $4$ of these roads, so there are $2^{10-4}\cdot 5 = 320$ ways to do the first case. The second case is similar in idea and also has $320$ ways to do this.

But, we see that:

There is overcounting. For example, we could have city A having all roads pointing towards it and city B all roads pointing away from it. The number of overcounted cases is $5\cdot 4 = 20$ ways to choose the two cities, and $2^3$ ways to rearrange the roads that are not defined by the two cities.

Hence, the total is

$320 + 320 - 160 = 480$.

But, we have to

Subtract that from the total because we used complementary counting so the answer is now $2^{10} - 480 = \boxed{544}$ and we are done.

This problem comes from here:

This problem...don't click here if you don't want the answer.

Improve this answer
$\endgroup$
6
  • $\begingroup$ So the roads are all one way only? I would have expected a road between wo cities to be usable in both directions. $\endgroup$
    – Gimli
    Commented Mar 5, 2018 at 8:43
  • 3
    $\begingroup$ I feel the answer is not quite complete. With 6 cities (15 roads) you can have an arrangement of the directions where every city has incoming and outgoing roads, but such that three cities are unreachable from the other three cities. Why would something like this not be possible with 5 cities? This answer assumes this to be the case without proving it. $\endgroup$
    – Jaap Scherphuis
    Commented Mar 5, 2018 at 9:59
  • $\begingroup$ @JaapScherphuis It is not possible to have three cities being unreachable from the other three cities. The graph is complete. There must be roads conecting all possible pairs of cities. $\endgroup$
    – NL628
    Commented Mar 5, 2018 at 14:50
  • 1
    $\begingroup$ @NL628, what JaapScerphuis is referring to is a configuration with 6 cities, let's call them A1, A2, A3, B1, B2, B3. There are roads connecting all possible pairs, but every road which has A* on one end and B* on the other leads from the former to the latter. That way you cannot reach from B* to A*. $\endgroup$
    – elias
    Commented Mar 5, 2018 at 15:04
  • $\begingroup$ @elias Mmmm I see. But then, one must have an unequal number of cities in group A and group B because the number of cities is odd. Then, it would be possible for an extra city on either group to have a connection with the other group. $\endgroup$
    – NL628
    Commented Mar 5, 2018 at 15:14

Not the answer you're looking for? Browse other questions tagged or ask your own question.