Even Tree [HackerRank]

Hi all, I’m sorry about not posting very frequently – thankfully, however, my exams will be coming to a close in the next two weeks, so I will be able to return to regular posting soon.

If you are unfamiliar with graph theory, I recommend that you read my previous post on the subject – it gives an introduction into the topic and the ways in which it appears in competitive programming.

Today, we will solve a relatively simple problem on graph theory which can be found on the ‘HackerRank’ website – given a tree (a graph with no cycles and where any node can be reached from any other node) of N nodes numbered from 1 (which is the root node) to N, our program must find the maximum number of edges it can remove from this tree to obtain a set of trees (commonly called a ‘forest’) where every tree has an even number of nodes.

The source code of my final solution to this problem can be found here.

The problem statement states that it is always possible to remove edges from the main tree to create a forest consisting of only trees with even numbers of nodes, so we do not need to concern ourselves with difficult edge cases. This brings us to a relatively simple solution: any ‘subtree’ (a smaller tree which is part of the main tree – it may have its own root separate from the main root) with an even number of nodes can be separated from the node connecting to its root – therefore, the maximum number of edges which can be removed from the tree to satisfy the problem statement is equal to the number of subtrees with even numbers of nodes. We have now reduced the problem to counting the number of nodes in each subtree.

Our first course of action is to devise a method for storing the tree – the technique I used is known as an ‘adjacency list’. In C++, this is essentially a vector where each element represents a node. For simple graphs like the ones used in this problem, each node can be represented by a vector of integers, with each integer representing a node which can be reached from the node represented by the vector itself. Initially our adjacency list will be empty, however, we will fill it by taking each edge from input as two integers (which represent the two nodes connected by the edge in question) connecting the deeper of the two nodes to the node closer to the root (not vice-versa! The edges in our list only need to be unidirectional).

EvenTree1.png

After creating the adjacency list, we can write a function which performs a depth-first traversal of the tree, counting the number of nodes in each subtree by travelling to each node in turn and counting the number of children it has and adding 1 to this value (this addition represents the current node, which acts as the root). We can do this elegantly using recursion – the numbers of nodes in the subtrees rooted at the deepest points of the tree are always 1 (as these nodes have no child nodes). By this logic, we can have our recurring function return 1 when it reaches a node with no child nodes, and in order to calculate the numbers of nodes in the other subtrees, we recur for every child node of each potential root node and save the sum of the results.

EvenTree2.png

Once we have calculated the number of nodes in every possible subtree of the main tree, we can just iterate through our results and increment our final answer by 1 every time we find a subtree with an even number of nodes. Once this process is complete, we can print out our final value.

EvenTree3.png

Interesting Geometry Questions from the Intermediate Maclaurin Mathematical Olympiad (Part 2 – 2010)

This post covers a second set of geometry problems from the Intermediate Maclaurin Mathematical Olympiad (a mathematics competition run by the UK Mathematics Trust, aimed at students of age 16). Like the problems in the previous post, these problems do not require knowledge beyond that of a GCSE-level student, they are more a test of one’s creativity and insight than a test of one’s knowledge of the subject.

Problem 1

geometrymaclaurinp1

The two key pieces of information in this problem’s description are that all three shapes are regular, and that they have an edge in common. Another way of phrasing this is that every visible line in the question’s diagram has the same length. Additionally, since all three shapes are regular, they all have their own sets of equal internal angles. We can calculate the size of a single internal angle from all three shapes using the formula below (where n is the number of sides the polygon has):

Sum of the interior angles of a polygon (degrees) = (n-2) * 180

Single internal angle (degrees) = Sum of the interior angles of a polygon (degrees) / n

Using this procedure, we acquire the following sizes for a single internal angle of each polygon:

  • 15-gon: 156 degrees
  • Heptagon: 900/7 degrees
  • Decagon: 144 degrees

In order to find the size of angle XYZ, we need to take into account two ideas: one being that the sum of the angles around a single point is 360 degrees, and another being that the sum of the angles inside a triangle is 180 degrees. To progress further towards a solution, we can first focus on the lower point of the side the three polygons have in common (this point will be named P). We can find the size of the angle XPY by subtracting 900/7 degrees and 144 degrees from 360 – doing this gives the value 612/7. Additionally, we can also find the size of the angle ZPY by subtracting 900/7 degrees from 156 degrees – doing this gives the value 192/7. Given that the lengths of the lines PZ and PY are equal (since every visible line in the question’s diagram has the same length), we can state that the triangle ZPY is an isosceles triangle, and we can find the angle PYZ by subtracting  192/7 degrees from 180 degrees and dividing the result by 2 – this gives the value 534/7. To find the size of the angle XYZ, we can subtract the size of the angle XYP from the size of the angle PYZ. Getting the size of the angle XYP can be done by subtracting the size of the angle XPY from 180, and dividing the result by 2. To find the size of the angle XPY, we can subtract the values 144 degrees and 900/7 degrees from 360 degrees to obtain the value 612/7. Subtracting this value from 180 degrees and dividing the result by 2 gives the value 324/7 for the size of the angle XYP. We can now find the size of the angle XYZ by subtracting 324/7 from 534/7; doing this gives the value 210/7, which simplifies to 30 degrees.

geometrymaclaurinp1working1

Problem 2

geometrymaclaurinp2

In order to tackle this question, we must be aware of the circle theorem which states that a triangle drawn inside a semicircle with the longest side being said semicircle’s diameter will always be a right-angled triangle. Therefore, the triangle formed by the three points C, A and D is a right-angled triangle. Given that we know that the length of this right-angled triangle’s hypotenuse is 4, we can use the Pythagoras Theorem to find the length of CD if we know the distance between the two points A and C.

A kite can be drawn inside the circle if a radius is drawn to the point C. A key characteristic of this kite is that the length from its lowest point to its highest point is 2 (because this length is the radius of the circle).

geometrymaclaurinp2working2

This kite can then be split into four right-angled triangles, with the side lengths shown in the image below:

geometrymaclaurinp2working1

In the drawing above, we acknowledge that the distance from the lowest point of the kite to the highest point is 2, and we split this distance at the line AC to form two lines of length x and 2-x. Additionally, we know that the shape above is symmetrical, so the line from its lowest point to its highest point bisects the line AC into two smaller lines of length y. Focusing on one of the two sides of the kite, we can use the Pythagoras Theorem to form the following equations:

geometrymaclaurinp2working3

geometrymaclaurinp2working4geometrymaclaurinp2working5

First we observe that x^2 and y^2 sum to 1, and then we can subtract this expression from the sum of y^2 and (2-x)^2 to obtain a linear equation which we can then solve to find the value of x. We can then substitute this value of x into our first equation in order to acquire the positive value of y (obviously, a negative value of y does exist, but here we disregard it because we are dealing with length).

Now we can go back to our original image of the circle – given that the line AC has a length of 2y, we can apply the Pythagorean Theorem as follows to find the length of CD (bearing in mind that the circle theorem mentioned at the start of the explanation for this problem states that the triangle ACD is right-angled).

geometrymaclaurinp2working7

Problem 3

geometrymaclaurinp3

This problem initially appears quite complex – it requires a crucial insight in order for it to be solved, however, with this insight, the solution to the problem is arguably the most concise and elegant out of the three solutions on this post. The various regions in the diagram are created by the intersections of two triangles with equal area, shown below:

We can see that these two triangles have equal area by looking at the formula below:

Area of a triangle = (base * perpendicular height) / 2

Given that the length of the base of one of the triangles is the perpendicular height of the other triangle, and that the multiplication operation is commutative, this formula returns the same value for the area of both triangles (we do not need to know any specific values for either the base or the height in order to see that this is the case). Additionally, this value for the areas of the triangles is equal to half the area of the entire diagram, because the triangles share their dimensions with the rectangle, and therefore the white area on the right diagram is equal to the shaded area on the left diagram – if we label the regions on the diagram in the manner shown below, we can form and solve a new equation based on this idea.

geometrymaclaurinp3working3

Looking at the two previous diagrams, the shaded area of the one on the left contains the regions ab and c, while the white area of the one on the right contains the regions of a and c, along with three regions of sizes 1, 2 and 3. Given that both sections have equal area, we can form and solve the following equation to find the area of region b, which is the shaded area in the original question’s diagram.

geometrymaclaurinp3working4

Conclusion

As the Maclaurin Olympiad draws closer, I will continue to make more posts on the problems it has given in the past. Additionally, I will also begin writing about an interesting computing-related side project of mine in the coming weeks – more about this project will be revealed soon.

Interesting Geometry Questions from the Intermediate Maclaurin Mathematical Olympiad (Part 1 – 2008)

Due to certain circumstances related to other extra-curricular activities which I am participating in over the next several months, I will be unable to compete in the Intermediate Maclaurin Mathematical Olympiad (a British mathematics competition aimed at students of age 16 and under – pupils qualify to compete in it through achieving high scores in the UKMT Intermediate Challenge; more information on it can be found here). This would have been the last year I would have been young enough to participate in the competition, so I will be unable to attempt it ever again. However, several requests from fellow students of mine have led me to write about some of the questions which have been presented in this olympiad, in hopes of assisting any potential competitors both this year and in the future. The problems I will be exploring in this series of posts will have all come from past Maclaurin Olympiads, and have all been written by its organisers. This post will be focused on the problems related to geometry – no knowledge of any advanced theorems is required (the problems can be solved with a knowledge of GCSE-level mathematics).

Problem 1

Screen Shot 2017-01-24 at 9.27.27 AM.PNG

This question can be answered quite cleanly using several GCSE-level ideas about circles and polygons. The idea of this answer is to prove that the triangle DEF is an isosceles triangle with DE and DF as the two equal sides. Our first step is to observe that each angle within the pentagon has a size of 108 degrees. We can come to this conclusion using the following formula:

Sum of the interior angles of a polygon (degrees) = (n-2) * 180

In this formula, n denotes the number of sides the polygon has, so in our case, n has a value of 5, and thus the sum of the sizes of the interior angles of the pentagon is 540 degrees. Furthermore, from this figure, we can calculate the size of a single interior angle by dividing 540 by 5 – this calculation gives 108 degrees as the size of single angle.

Our next step is to calculate the angle DEF (so that we can then proceed to prove that it is equal to the angle DFE later on). The angles DEF and DEA lie on a straight line and thus have sizes that sum up to 180 degrees, and given that DEA is one of the interior angles of the pentagon, we can state that the size of the angle DEF is 72 degrees.

We must now proceed to prove somehow that the angle DFE also has a size of 72 degrees. A very simple way of doing this would be to apply the alternate segment theorem, shown below:

BlogAlternateSegmentTheorem.png

The theory states that in a circle boasting a tangent and an inscribed triangle (formed by three chords),  the angle between this tangent and a given chord is equal to the angle which is made by that same chord in the segment of the circle alternate to the segment containing the angle at the tangent. Therefore, in the diagram above, the blue angles are equal and the gold angles are equal.

Note that an inscribed triangle can be drawn on the circle in the problem, using points D, A and F. Drawing an inscribed triangle in this manner also forms a second isosceles triangle connecting points D, E and A. Remembering that the each interior angle of the pentagon has a size of 108 degrees, we can calculate the sizes two smaller angles of this newly formed isosceles triangle – both of them have a size of 36 degrees. Moreover, we can now calculate the angle CDA on the inscribed triangle by subtracting 36 from 108. We now know that the angle CDA has a size of 72 degrees, and the alternate segment theorem shows that the angle DFA also has a size of 72 degrees (as they lie on the same chord, but in alternate segments of the circle). Given that we now know that angle DEF and angle DFA both have the same size, we can state that the triangle DEF is an isosceles triangle, with DE and DF as its two equal sides. The image below illustrates this idea:

BlogPostMaclaurinGeometry1.png

Problem 2

Screen Shot 2017-01-24 at 9.27.37 AM.PNG

We can start tackling this problem by clearly defining the area of the triangle with a formula. First, we should declare that the base of the triangle is represented by b, and the height of the triangle is represented by h. Furthermore, we can use the following equation to denote the area of the triangle:

bgequations4

The path ahead is clear; we want to use the variables and y to represent both b and h, and if the above equation is true (and the question firmly states it is), the expression on the left will simplify to xy, giving an equation with two identical sides.

A key insight is that the height of the triangle is equal to x plus a certain value (let’s call this value z), and that the base of the triangle is equal to y plus this value. This is the case because when two tangents of a circle meet at a certain point, the lengths between the contact point of each tangent and the meeting point are equal. Using this theorem, three lines can be drawn on the circle: one to the base tangent, one to the height tangent and one to the longest tangent, like so:

blogmaclauringeometry2

The image shows that two kites and a square are formed when three radii are drawn, with one connecting to the base tangent and another to the height tangent. From this, we can write the following equations:

 

bgequations5

We can then proceed to apply the Pythagoras theorem to represent xy in a different manner, like so:bloggeometryequations1

We can now write a single equation using the variables xy and z to link our two separate values of xy.

bloggeometryequations2

 

Note that xy makes yet another appearance here, so we can substitute one of our known values for this term in to complete the equation.

 

bloggeometryequations3

To summarise our ideas, we can state that we have proven the area of the triangle is equal to xy by initially using both the Pythagoras theorem and a set of circle theorems to create a second expression for xy, before completing our proof by simplifying our expression for the area of the triangle such that it becomes equal to our second expression for xy.

Conclusion

I will continue to make more posts exploring various questions from the Maclaurin Olympiad as its date draws closer. The next post on the topic will come soon, and will most likely explore a second pair of geometry questions, from more recent years.