MTH1030/MTH1035: Project 1, 2025

2025-03-23 Admin 写评论


Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due


MTH1030/MTH1035: Project 1, 2025

Linear Logic

1 Mission 1: Conjuring the Cube (40 marks)

In a totally fictitious city there is a strange building in the shape of a cube, partially sunk into the ground.

The image on the right shows what you would see if you were looking straight down at the cube from a drone. Imagine that you have been recruited by an architectural visualization company that specializes in 3D modeling of urban environments. Your task? To reconstructan accurate 3D model of this cube for an upcoming virtual reality city simulation.

To do this, you need to find the coordinates of the cube’s key points:
  • The four visible corners of the cube in the top-down view: A, B, C, D.
  • The points where four of the cube’s edges meets the ground: A0 , B0 , C0 , D0 .
As indicated in the reference diagram, point A is connected to A0 , point B to B0 , and so on. Also, both B and D are at the same height above the ground.

However, there’s a catch. The engineer previously assigned to this project quit unexpectedly, leaving behind a set of unorganized, cryptic notes. From what can be deciphered, the cube’s base is aligned with the xy-plane, with the y-axis pointing West and the x-axis pointing North. Additionally, two crucial corner points, A and C, were already measured before the previous engineer left.

To retrieve the coordinates of points A and C, enter your 8-digit employee (Monash) ID number into the following online tool: https://www.qedcat.com/cubeAC.html.

Your Task

Apart from finding the coordinates of A, B, C, D, A0 , B0 , C0 , D0 , your job also involves calcu lating the following:
  • The lengths of the edges AA0 , BB0 , CC0 , DD0 .
  • The side length of the cube |AB|.
  • The area of the base A0 B0 C 0 D0 (not a square!).
  • The surface area of the part of the cube above ground.
  • The volume of the part of the cube above ground.
At the end of your report, summarize your results as follows:
A = (∗, ∗, ∗)
B = (∗, ∗, ∗)
C = (∗, ∗, ∗)
D = (∗, ∗, ∗)
A 0 = (∗, ∗, ∗)
B 0 = (∗, ∗, ∗)
C 0 = (∗, ∗, ∗)
D 0 = (∗, ∗, ∗)
|AA0 | = ∗m
|BB0 | = ∗m
|CC0 | = ∗m
|DD0 | = ∗m
sidelength = ∗m
area(A0 B0 C 0 D0 ) = ∗m2
surface area = ∗m2
volume = ∗m3
Additionally, generate a 3D representation of the structure above the ground, clearly showing all 12 edges.

Important

Accuracy: Some of your coordinates are rounded to four decimal places. However, your final answers should be accurate to at least two decimal places (e.g., 12.5674m ≈ 12.57m). To ensure accuracy, only round final results, not intermediate values.

Methodology: Your calculations must exclusively use the mathematical tools covered in Week 1:

  • The cross product to construct perpendicular vectors.
  • The cross and box products to compute areas and volumes.
  • Line equations to determine cube edges and intersections.

Strict Marking Policy: Each mistake in vectors, values, or diagrams results in a 2-mark deduction. If an error affects subsequent calculations, every resulting mistake will also be penalized. Ensure all results are verified before submission.

To avoid errors, double-check your work using techniques such as the dot product to confirm right angles.

You can adapt the piece of Mathematica code on the following page to produce the picture of the sunken cube.

Graphics3D[{{Red, PointSize[Large], Point[{0, 0, 0}],
Point[{0, 0, 1}], Point[{0, 1, 0}], Point[{1, 0, 0}]}, {Red, Thick,
Line[{{0, 0, 0}, {0, 0, 1}}], Line[{{0, 0, 0}, {0, 1, 0}}],
Line[{{0, 0, 0}, {1, 0, 0}}], Line[{{0, 0, 1}, {0, 1, 0}}],
Line[{{0, 0, 1}, {1, 0, 0}}],
Line[{{0, 1, 0}, {1, 0, 0}}]}, {Opacity[0.3], Blue,
Polygon[{{0, 0, 0}, {0, 0, 1}, {0, 1, 0}}],
Polygon[{{0, 0, 0}, {0, 0, 1}, {1, 0, 0}}],
Polygon[{{0, 0, 0}, {0, 1, 0}, {1, 0, 0}}],
Polygon[{{0, 0, 1}, {0, 1, 0}, {1, 0, 0}}]}}, Boxed -> False,
Axes -> True, AxesLabel -> {"x", "y", "z"}
]

2 Mission 2: Too many cars! (30 Marks)

Consider a network of one-way streets consisting of:
  • Four junctions, marked in red.
  • Five internal streets connecting these junctions, labeled as a, b, c, d, e.
  • Four external streets connecting the network to the main traffic grid. In the diagram we’ve recorded the traffic flow rates on three of the external streets in cars per hour.
Figure 1: A zany traffic network.

We make the following assumptions:

  • Vehicles are continuously moving—there are no stops, parking, or interruptions.
  • The system follows the principle of flow conservation, meaning no cars are spon taneously created or removed within the network.

Your Task

(a) (2 marks) What is the traffic flow rate on the fourth external street labelled with question marks?
(b) (4 marks) Using the conservation of traffic flow at each of the four junctions, derivea system of four equations involving the variables a, b, c, d, e. Arrange the variables corresponding to the incoming and outgoing streets on the right and left of the equal signs, respectively.
(c) (2 marks) Express the system of equations as a matrix equation. Make sure that columns 1, 2, 3, 4, 5 of your matrix correspond to a, b, c, d, e, respectively.
(d) (4 marks) Express the system of equations as an augmented matrix. Compute the reduced row echelon form of your augmented matrix using Mathematica. Make sure that columns 1, 2, 3, 4, 5 of your matrices correspond to a, b, c, d, e, respectively.
(e) (3 marks) Read the solution of the linear system off the reduced echelon form. The solution should include free parameters.
(f) (2 marks) What is the minimum number m of traffic counters that you have to install on some m internal streets to be able to figure out the flow rates on ALL the internal streets suggested by your solution? Give an example of m internal streets that work in this respect.
(g) (4 marks) Given any selection of m internal streets, how can you decide using linear algebra whether installing traffic counters on those streets allows you to determine the flow rates of all the internal streets?
(h) (4 marks) List a possible choice of m internal streets whose flow rates DO NOT pin down all the flow rates of all the remaining streets and use linear algebra to prove thatthis is really the case.
(i) (5 marks) Not all solutions of our system of equations are physically possible as flow rates must be non-negative (assuming the absence of wrong-way drivers :) What are the minimum and maximum possible flow rates on a. Label two diagrams with two distributions of flow rates that feature these two extreme flow rates on a.

Extension questions

All pretty straightforward and so if you are keen, here are some more tricky questions that you may want to ponder. No marks attached to these questions. Discuss your solutions with Burkard.

How can you be sure that the minimum number m suggested by your solution of the system of equations is really THE minimum number we are interested in here? Is there an easy linear algebra based argument?

Given a possible distribution of traffic flow rates on the internal streets, let M be themaximum of these traffic flow rates. For which possible distribution is M minimal? What is this minimal maximal traffic flow rate? Of course, ultimately what we are really interested here is a general algorithm that finds this minimal value and the associated special distribution(s) of traffic flow rates.

3 Part 3: Devilish determinants (30 Marks)

Let’s look at one example of the determinant working its magic that is relevant for computer science applications.

On the left we have an example of a network or graph consisting of four vertices and five edges. On the right we have the eight different spanning trees of this graph. Here a spanning tree is a connected subgraph of our original graph whose edges do not form any loops and whose edges contain all the vertices of the original graph. It turns out that you can always count the number of spanning trees of a graph using determinants. Here is what you do:

  • There are four vertices. This means we’ll start by making a 4 × 4 matrix L.
The numbers on the main diagonal are the numbers of edges ending in vertices 1, 2, 3, 4. For example, there are two edges ending in vertex 1 and so the upper left entry of our matrix is equal to 2: l1,1 = 2. Apart from that, entry li,j = −1 if the vertices i and j are connected by an edge and li,j = 0 otherwise. For example, the number in the lower left corner of our matrix is 0 because vertices 1 and 4 are not connected by an edge.
  • Delete one row and one column from this matrix. Doesn’t matter which row or which column. For example, deleting the first row and the first column gives this matrix:
  • Then the determinant of this last matrix is equal to the number of spanning trees of our graph.
Wonderful!
We are not going to prove this theorem. Instead let’s apply it.

a) (6 marks) Let Bi be the banana graph having vertices 1, 2, 3, 4 . . . i, i ≥ 3. Let si be the number of spanning trees of Bi and let Li be the corresponding L matrices. Here are pictures of B3, B4, B5, and B6.

Display L3, L4, L5, L6 and the matrices you get by deleting their last rows and columns. Use the new matrices you arrive at to calculate the numbers s3, s4, s5, s6 of spanning trees of B3, B4, B5, B6, respectively.

b) (14 marks) What comes next? The underlying pattern of the matrices L3, L4, L5, L6 should be obvious. Describe this pattern. But what about those determinants? Just based on the numbers s3, s4, s5, s6 that you have calculated, can you guess what the next number s7 will most likely be? Can you guess a “formula” for si? In the seminars we’ll try to figure out that formula. You’ll have to summarize the reasoning we come up with in your write-up of this assignment.

c) (4 marks) Draw all the spanning trees of B4.

d) (6 marks) Calculate det(Li) for i = 3, 4, 5, 6? What’s the general rule? Another nice surprise isn’t it? Prove the general rule!

发表评论

电子邮件地址不会被公开。 必填项已用*标注