Completing the square word problem

[Terrell]

Homework Statement

i've attached an image of the given problem. please see below

Homework Equations

tax revenue - maintenance cost = net revenue. net revenue can never be negative

The Attempt at a Solution

i've tried setting (p1)^2 for the revenue of a random city,
(p2)^2 for the revenue of the city that the other connects to,
then (p1)(p2) for the maintenance cost of the road that connects the two.

revenue: (p1)^2 + (p2)^2 + (p3)^2 + ... + (pn)^2
maintenance cost: (p1)(p2) + (p1)(p3) + ... (i guess this depends on how the distribution of maintenance cost will be like)

we can also deduce from the queen's decree that tree graphs cannot connect with loops because it violates the "there can only be one way from one city to any other city" law.

i'm having difficulty generalizing because the problem asks for the maximum number of cities REGARDLESS of population and road design. (road design is really vague for me).

 

[SammyS]

Homework Statement

i've attached an image of the given problem. please see below

Homework Equations

tax revenue - maintenance cost = net revenue. net revenue can never be negative

The Attempt at a Solution

i've tried setting (p1)^2 for the revenue of a random city,
(p2)^2 for the revenue of the city that the other connects to,
then (p1)(p2) for the maintenance cost of the road that connects the two.

revenue: (p1)^2 + (p2)^2 + (p3)^2 + ... + (pn)^2
maintenance cost: (p1)(p2) + (p1)(p3) + ... (i guess this depends on how the distribution of maintenance cost will be like)

we can also deduce from the queen's decree that tree graphs cannot connect with loops because it violates the "there can only be one way from one city to any other city" law.

i'm having difficulty generalizing because the problem asks for the maximum number of cities REGARDLESS of population and road design. (road design is really vague for me).

Some people may wish to see the problem statement made easily readable.

 

[Terrell]

i would prefer getting hints first. thanks! :)

 

[Ray Vickson]

i would prefer getting hints first. thanks! :)

If you want help you need to make things convenient for the helpers, not for yourself. The problem refers to the "attached design" but you have not shown us the attachment, so we are left guessing that what is allowed is a "binary tree". Is that the case?

Is this a problem located within a particular course context? The problem is that for n cities, there are many different possible binary trees on n nodes, and the maintenance cost depends on the design of the tree. Somehow you want a result that is of "worst case" type: in the worst-case design, the maintenance is less than the revenue. Is there some type of course material that is relevant to this problem?

 

[Terrell]

If you want help you need to make things convenient for the helpers, not for yourself. The problem refers to the "attached design" but you have not shown us the attachment, so we are left guessing that what is allowed is a "binary tree". Is that the case?

Is this a problem located within a particular course context? The problem is that for n cities, there are many different possible binary trees on n nodes, and the maintenance cost depends on the design of the tree. Somehow you want a result that is of "worst case" type: in the worst-case design, the maintenance is less than the revenue. Is there some type of course material that is relevant to this problem?

i'm sorry. should i just repost? i can't seem to be able to edit this thread. i found this problem from brilliant.org and saw it under the "quadratic equations - completing the square" section which was a bit surprising to me because my first impression of this problem should be under graph theory. also the reason why i did not post this diagram at first is because the author of the problem noted the diagram only as an acceptable example. thanks!

 

[Ray Vickson]

i'm sorry. should i just repost? i can't seem to be able to edit this thread. i found this problem from brilliant.org and saw it under the "quadratic equations - completing the square" section which was a bit surprising to me because my first impression of this problem should be under graph theory. also the reason why i did not post this diagram at first is because the author of the problem noted the diagram only as an acceptable example. thanks!

So my guess was correct: I said the description sounded like it allows a binary tree, and your diagram is, indeed, an example of a binary tree.

However, my original remarks remain: there are numerous different binary trees on n nodes, and different trees can have different maintenance costs (even for the same populations at the cities), so how can we be sure of achieving a non-negative net revenue? What prevents us from having $p_i = 0$ for all $i$, so the revenue and costs both equal zero, giving us a non-negative net revenue, as desired? If there is some total population restriction, such as $\sum_i p_i = N$, then, of course, the all-0 solution is eliminated.

In the same spirit, what prevents us from taking $p_1 = N, p_2 = p_3 = \cdots = p_n = 0$? That has revenue $p_1^2 = N^2$ but zero maintenance cost (since no roads are built).

 

[haruspex]

So my guess was correct: I said the description sounded like it allows a binary tree, and your diagram is, indeed, an example of a binary tree.

However, my original remarks remain: there are numerous different binary trees on n nodes, and different trees can have different maintenance costs (even for the same populations at the cities), so how can we be sure of achieving a non-negative net revenue? What prevents us from having $p_i = 0$ for all $i$, so the revenue and costs both equal zero, giving us a non-negative net revenue, as desired? If there is some total population restriction, such as $\sum_i p_i = N$, then, of course, the all-0 solution is eliminated.

In the same spirit, what prevents us from taking $p_1 = N, p_2 = p_3 = \cdots = p_n = 0$? That has revenue $p_1^2 = N^2$ but zero maintenance cost (since no roads are built).

it says, regardless of the populations. The queen cannot require any populations to be zero.

 

[haruspex]

Start by playing around with small networks. Try two cities, then three, then four.
Write out algebraic expressions for the profit, and see how it can be organised into sums of terms that are guaranteed non-negative.
Of the ways of connecting four, is one looking less profitable than the other?

 

[Terrell]

So my guess was correct: I said the description sounded like it allows a binary tree, and your diagram is, indeed, an example of a binary tree.

However, my original remarks remain: there are numerous different binary trees on n nodes, and different trees can have different maintenance costs (even for the same populations at the cities), so how can we be sure of achieving a non-negative net revenue? What prevents us from having $p_i = 0$ for all $i$, so the revenue and costs both equal zero, giving us a non-negative net revenue, as desired? If there is some total population restriction, such as $\sum_i p_i = N$, then, of course, the all-0 solution is eliminated.

In the same spirit, what prevents us from taking $p_1 = N, p_2 = p_3 = \cdots = p_n = 0$? That has revenue $p_1^2 = N^2$ but zero maintenance cost (since no roads are built).

after trying out some population values. it seemingly appears that if for every new city/node has a bigger population than the city/node it branched out from then i can safely guess that cities will be economically viable because (p_n)^2 - (p_n)(p_n-1) seems to be always greater than zero. the queen would also need to order that city p_n should shoulder the maintenance cost because p_n-1 might not be able to if we think of the worst case scenario of 3 roads connecting to it.

 

[haruspex]

if for every new city/node has a bigger population than the city/node it branched out from

Sure, but the Queen cannot control the populations. She has to allow for the worst case.