The King needs your help

Algebra Level 5

An ambitious king plans to build seven new cities in the wilderness, connected by a network of roads. He expects the annual tax revenues from each city to be numerically equal to the square of the population. Road maintenance will be expensive, though; the annual cost for each road is expected to be numerically equal to the product of the populations of the two cities that road connects. The project is considered viable as long as the tax revenues exceed the cost, regardless of the (positive) populations of the various cities. A developer submits a project as shown in the inserted graph, with the vertices representing the cities. Convince the king that this is not a viable plan! Find a population configuration where tax revenues will fail to exceed the cost for road maintenance. As your answer, return

$\frac{\text{total population of all seven cities}}{\text{population of the central city C}}$

We are told that there is only one possible configuration, up to a scaling.

This problem is continued here and here

The answer is 4.00.

1 solution

Raghav Vaidyanathan
May 7, 2015

Great problem! By intuition and symmetry, we claim that the cost>=income scenario occurs in a configuration where:

The central city has a population $a$ .
All three cities adjacent to the central city have population $b$
All the three terminal cities have a population of $c$

Using the information given in the problem, we have to find the condition for the following to happen:

$3ab+3bc \ge a^2 + 3b^2+3c^2$

Without loss of generality, assume: $b=ax,c=ay$ . Hence it is enough to solve:

$3x+3xy \ge 1+3x^2+3y^2$

We can re arrange the above equation into the following beautiful form:

$4{ (y-\frac { x }{ 2 } ) }^{ 2 }+3{ (x-\frac { 2 }{ 3 } ) }^{ 2 }\le 0$

It immediately follows that: $x=\frac{2}{3}, y= \frac{1}{3}$

Therefore, $b=\frac{2a}{3}, c=\frac{a}{3}$

Total population, $P_T=a+3b+3c=4a$

The required ratio is: $\frac{P_T}{a}=4$

Elegant solution! Thanks!

There are lots of interesting FOLLOW-UP QUESTIONS here, of course: Which graphs make for a viable plan? Which graphs make sure that the king is not losing money, at least (like the one we consider in this problem)? These are important and well-studied issues that come up in representation theory.

Can you give another example of a graph that is revenue-cost-neutral for some populations, but where the king is guaranteed not to lose money?

Otto Bretscher - 6 years, 1 month ago

Yes, I thought of that. The given problem is easy due to its symmetry, But how do we tackle more complicated graphs for seven and/or more cities? On top of that how can we even prove that a certain graph is the best/worst possible scenario? Brute force is an obvious option, but even that takes forever if there are many cities.

Raghav Vaidyanathan - 6 years, 1 month ago

Good questions! The function we consider here is called a "quadratic form", and we want to know whether it is "positive definite" or at least "positive semi-definite". In very simple cases (few vertices or symmetry), we can get away with completing the squares, but that method becomes tedious very quickly, as you expect. The standard approach is to look for the eigenvalues of a certain matrix which in our case is $2I_n-A$ , where $A$ is the adjacency matrix of the graph. It all boils down to the signs of the determinants of the principal submatrices of this matrix.

For example, you can show in this way that a "linear" graph with vertices 1, 2,...., n, where k is linked to k+1 for k=1...,n-1, is positive definite (it makes a "viable" city plan)... this is a simple exercise in an introductory linear algebra class.

Otto Bretscher - 6 years, 1 month ago

@Otto Bretscher – I see, that is interesting. Matrices seem to be popping out of a lot of places these days. @Otto Bretscher , Is it really necessary for us to use matrices to prove the exercise that you have mentioned?

What I want to know is this: can we say that, for a graph in which the n cities are distinct vertices of an n sided polygon, we have a "semi-viable" city plan? By "semi-viable" we mean that cost<=income.

If the above hypothesis is true, we can just destroy any one road(remove a side of the polygon) and we end up with a "viable" city plan. A "linear" graph.

Raghav Vaidyanathan - 6 years, 1 month ago

@Raghav Vaidyanathan – I like the way you approach this! You will have fun figuring it out for yourself (consider the case of three cities first)! For starters, ask yourself: Is the loop road approach (or polygon approach) viable?

Next question to ponder: Find an example of a non-linear graph that is "viable".

Otto Bretscher - 6 years, 1 month ago

Yup, did it with this assumption too! Unexpected completing the square; I haven't used it in a long time.

Jake Lai - 6 years, 1 month ago

Good thing that the problem specifies that this is the only scenario. Proving it rigorously doesn't seem to be easy.

Raghav Vaidyanathan - 6 years, 1 month ago

"Unexpected" is good ;)

Otto Bretscher - 6 years, 1 month ago

@Otto Bretscher

Raghav Vaidyanathan - 6 years, 1 month ago

Some comments:
In your first equation, it should be $3ab + 3bc$ on the LHS.
The initial assumption of symmetry needs to be justified. That, in essence, is the work of this problem. As Otto mentioned, we're essentially looking at a $7 \times 7$ matrix, which you simplified into a $3 \times 3$ matrix thereby cutting down the complexity.

Calvin Lin Staff - 6 years, 1 month ago

I tried to offer some help with my last sentence, "We are told that..." ;)

Otto Bretscher - 6 years, 1 month ago

Right, I was linking it back to your statement of "It all boils down to the signs of the determinants of the principal submatrices of this matrix." With that understanding, and a whole bunch of theorems (in linear algebra / representation theory), one gets to see how this problem could be dealt with.

I remember the first time that I came to interpret "inequalities of quadratic terms" through the "positive semi-definite form", which made it much simpler to attack. The difficulty of "completing the square" without motivation of terms is now simplified to just "finding the eigenvalues and eigenvectors". In fact, with that understanding, we can take any weird looking semi-definate matrix and convert that into an inequality problem.

Here's an interesting corollary (of the analogy). Let $f(0), f(1), \ldots f(n)$ be real values such that $\sum_{i\neq 0} |f(i)| < f(0)$ . Let $m_{ij} = f( | i - j | )$ . Show that for any set of real values $a_1, a_2, \ldots, a_n$ not all 0, we have

$\sum_{i,j} m_{ij} a_i a_j > 0$

Calvin Lin Staff - 6 years, 1 month ago

@Calvin Lin – Whoa! This feels like listening to people talk in your language and not being able to understand it.

Raghav Vaidyanathan - 6 years, 1 month ago

@Raghav Vaidyanathan – Don't worry about this for the time being... maybe it serves as a motivation to learn more about matrices and linear algebra. I know a good book on "Linear Algebra with Applications"... there is even an Indian edition ;)

Trying to be fair and reasonable, I was posing the question in such a way that people could handle it by completing the squares alone... you did this very well indeed. You had some very good ideas about my follow-up questions: Think about the loop road first, then the linear case. Also, maybe you can find one non-linear case of a viable graph. Can you give us your answers, for the benefit of the other readers?

Otto Bretscher - 6 years, 1 month ago

@Otto Bretscher – How about converting this comment into a note, so that you can lay out possible explorations of the investigation, and also allow others to investigate these scenarios? There is a lot of beauty mathematical theory that's wrapped up above.

Calvin Lin Staff - 6 years, 1 month ago

@Raghav Vaidyanathan – Well, that's mostly because you are unfamiliar with linear algebra and positive semi-definite forms. Over time, as you learn about them and make the linkages above, you will understand quadratic inequalities <=> positive quadratic forms <=> positive matrices <=> diagonal matrices with positive entries.

When I get some time, I will explain how one can easily (with a few minutes of work) show that for all real $a, b, c$ ,

$5 a^2-6 a b-4 a c+4 b^2-2 b c+3 c^2 \geq 0$

and further prove that equality holds if and only if $a = b = c$ . Notice that since the coefficients are not symmetric (IE the weird semi-definite matrices that I alluded to above), we cannot immediately apply the usual Classical inequality tricks. And yet, any attempt at "completing the square" seems almost hopeless.

In the meantime, why don't you try proving the inequality?

Calvin Lin Staff - 6 years, 1 month ago

@Raghav Vaidyanathan – Elegant solution! Thanks!

There are lots of interesting FOLLOW-UP QUESTIONS here, of course: Which graphs make for a viable plan? Which graphs make sure that they are not losing money, at least (like the one we consider in this problem)? These are important and well-studied issues that come up in representation theory.

Can you give another example of a graph with seven vertices that is revenue-cost-neutral for some populations, but where the king is guaranteed not to lose money?

Otto Bretscher - 6 years, 1 month ago

@Otto Bretscher – Hi all. I'm a late-comer to this discussion (until this morning I had only seen the "The King (still) needs your help" version of this problem). I see the "viable plan" question has been answered already, but I don't think that

Which graphs make sure that they are not losing money, at least (like the one we consider in this problem)?

has been answered. So let me say, Yes there are a number of "break-even" graphs besides the one mentioned here and the 5-city "plus sign" mentioned on the other thread:

$B\\ C\\ D\\ EA\\ F\\ G\\ H$

and

$B\\ C\\ DA\\ E\\ F\\ G\\ H\\ I$

and also

$B\\ CA\\ D\\ ...\\ W\\ XZ\\ Y$

(where the number of cities between $C$ and $X$ can be any non-negative integer -- and that also provides one answer to your last question, "Can you give another example of a graph with seven vertices that is revenue-cost-neutral for some populations, but where the king is guaranteed not to lose money?" i.e.

$B\\ CA\\ D\\ XZ\\ Y$

Peter Byers - 6 years, 1 month ago

@Peter Byers – Thanks for this very careful and complete analysis! I like your clever way to use letters to describe a graph!

For the benefit of the other members, could you please post a solution here

Otto Bretscher - 6 years, 1 month ago

@Raghav Vaidyanathan – Maybe we should define a few basic terms.

An m x n matrix A is a family of numbers $a_{ij}$ where i=1...m and j=1..n .

A matrix is called square if m = n and it is called symmetric if it is square and $a_{ij}=a_{ji}$ for all i, j.

With a symmetric matrix A we can associate a function $f(x_1,x_2,...,x_n)=\sum_{i,j}{a_{ij}} {x_i} {x_j}$ , called a quadratic form. This quadratic form (and the symmetric matrix A that describes it) are called positive definite if $f(x_1,x_2,...,x_n)>0$ for all $x_1,x_2,...,x_n$ , not all zero, and it is called positive semidefinite if $f(x_1,x_2,...,x_n)\geq0$ for all $x_1,x_2,...,x_n$

To be continued...we need to talk about determinants.

Exercise: Find the symmetric matrix that describes the quadratic form you used, $a^2+3b^2+3c^2-3ab-3bc$ as well as the revenue/cost function associated with a linear or a circular graph.

Otto Bretscher - 6 years, 1 month ago

@Otto Bretscher – Thanks for all your help. I will really look into all this when I get free time from entrance exam preparation. As @Calvin Lin said, maybe we should think about converting all these comments into a note so that everyone can see it.

edit: I have basic knowledge of determinants matrices and the likes. I do not know how it is implemented in this case, that's all.

Raghav Vaidyanathan - 6 years, 1 month ago

@Raghav Vaidyanathan – It's great that you have some basic knowledge about determinants. Let me just give you the key result, due to Sylvester, that Mr Calvin has already mentioned.

If $M$ is an $n\times{n}$ matrix, then its kth (leading) principal submatrix $M_{(k)}$ is the $k\times{k}$ matrix obtained by omitting all the entries of $M$ past the kth row and past the kth column.

Now the result: A symmetric $n\times{n}$ matrix $M$ is positive definite iff the determinants of all its principal submatrices $M_{(k)}$ , for $k=1,...,n$ are positive. (You will find a proof in any decent introductory text in Linear Algebra.)

Also, if $\det{M_{(k)}}>0$ for $k=1,...,n-1$ and $\det{M}\geq0$ , then $M$ will be positive semi-definite.

As an example, let's look at the quadratic form you consider in your solution, $q(a,b,c)=a^2+3b^2+3c^2-3ab-3bc$ . Using the definition I gave earlier, the symmetric matrix of this form is $M=\frac{1}{2}\left[\begin{matrix}2&{-3}&0\\{-3}&6&{-3}\\0&{-3}&6\end{matrix}\right]$ You can see that $\det{M_{(1)}}=1,\quad\det{M_{(2)}}=\frac{1}{4}\det\left[\begin{matrix}2&{-3}\\{-3}&6\end{matrix}\right]=\frac{3}{4}$ $\det{M_{(3)}}=\det{M}=0,$ so that $M$ is positive semi-definite as you showed by completing the squares.

Otto Bretscher - 6 years, 1 month ago

@Raghav Vaidyanathan – I'm still a novice here, and I would not quite know how to convert these comments into a note... would you mind getting this project started?

Otto Bretscher - 6 years, 1 month ago

@Otto Bretscher – I've converted some of these comments about analyzing road networks into this note .

Calvin Lin Staff - 6 years, 1 month ago

@Calvin Lin – Thanks a lot! Very nice! Lots to think about...

Otto Bretscher - 6 years, 1 month ago

@Calvin Lin – Interesting... I have never seen this! I will think about it after work. Thanks, Calvin!

Otto Bretscher - 6 years, 1 month ago

@Calvin Lin – I think this is true, more generally, for any strictly diagonally dominant symmetric matrix M with positive diagonal entries (to use less jargon: "strictly diagonally dominant with positive diagonal entries" simply means that $m_{ii}>\sum_{j\neq{i}}|m_{ij}|$ for all i, and symmetric mean $m_{ij}=m_{ji}$ .)

Otto Bretscher - 6 years, 1 month ago

@Otto Bretscher – Precisely! I chose a very special form which allows for a very direct "completing the square" approach for those who are used to thinking about it that way. (They just need to be convinced that it can be done, even though it looks scary.)

The followup question then, would be like you suggested, showing it for the "symmetric diagonally dominant" version. In this instance, "completing the square" would be almost impossible, since we have little control over the variables and understanding how they relate. Instead, by phrasing it as "Symmetric diagonally dominant matrix with positive diagonal entries is positive definite", we get the result immediately. The proof of that statement (with some work) follows from the continuity of determinants of principal minors, and applying Sylvester's Criterion. I believe that almost any other approach is doomed to fail.

The idea is to highlight the power of "linkage thinking", and relating one field of mathematics into another, and using the results in the latter and translating them back into the former.

Calvin Lin Staff - 6 years, 1 month ago

@Calvin Lin – The proof is trivial once you know that symmetric strictly diagonally dominant matrices are invertible... what is the best way to prove that?

Otto Bretscher - 6 years, 1 month ago

The King needs your help

The answer is 4.00.

1 solution

0 pending reports