A Combinatorics Problem
There is a kingdom called Qidan that recently conquered three cities A , B and C . King Temutai wants to construct roads to connect the Capital to these three cities. At present, no two of these four places have road(s) connecting them.
The king has decided to construct a total of 630 roads, each of which fall into exactly one of the following three categories:
- From the Capital to city A ;
- From city A to city B and
- From city B to city C .
The King wishes to maximize the number of different ways from the Capital to city C , that passes through A and B exactly once. What is the maximum number of ways?
The answer is 9261000.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
This is, in fact, a problem inspired from the AM-GM inequality.
Let the number of roads from the Capital of Qidan to the city A be x ; from the city A to the city B be y and from the city B to the city C be z .
From the condition in the problem statement, we have x+y+z=630 .
According to the Product Rule of Counting , we have to find the maximum value of xyz .
Using the AM-GM inequality, we can have the real number 9261000 as the maximum value of xyz , with x=y=z=210 , which is also a real value. Luckily, those real values happen to be positive integer values too, as expected as number of roads.