The Games that Populations Play (Tuklas Vol. 13, No. 7 - Jan. 28, 2012)

THE GAMES THAT POPULATIONS PLAY

The outcome of making decisions can surprisingly (for some), actually be investigated within a mathematical framework. This branch of mathematics is called classical game theory; here, situations that call for decision-making are called games. In this framework, the game is being played by an individual; the prize for winning the game is quantified by the payoff. A special type of game known as the population game represents a situation wherein decision making is applied in the context of a collection of individual decision-makers who have the same set of strategies and choices.
Suppose that game theory is applied in explaining the phenomenon of gender ratio in the population. Why is the ratio of males to females in human (or animal) populations 50:50? Game theory phrases the answer to this question as follows: the ratio 50:50 is an evolutionarily stable strategy or ESS. An ESS is related to an outcome which best serves the decision maker in the midst of uncertainty. Consider a game described by the following:

• Male-to-female ratio is \(\rho:1-\rho\), where \(0\leq\rho \leq 1\)
• All females only mate once in their lifetime; consequently engender \(n\) offspring
• Males are polygamous and mate, on average, with \(\frac{1-\rho}{\rho}\) distinct females in their lifetime
• Females are the ``decision makers;" either \(D_1\): all offpsring are males; or \(D_2\): all offspring are females

The female does not actually make a conscious decision about what type of offspring it produces. So in general, of the \(n\) offsprings it produces, a proportion \(p\) would be male, while \(1-p\) would be female. This can be summarized as a vector \(\sigma=\langle p, 1-p\rangle\), where \(0\leq p\leq 1\). At a certain point in time, if one looks at the entire population and conducts a census the proportion of males is \(x\), and that of females is \(1-x\) so that the sex ratio is such that \(\rho=x\), and can be summarized as the vector \(\mathbf{x}=\langle x, 1-x\rangle\) wherein \(0\leq x\leq 1\). The payoff for the pure decisions \(D_1\) and \(D_2\) is equivalent to the number of grandchildren that each female is expected to have: \[ \begin{align*} \pi(D_1,\mathbf{x}) &= n^2\frac{1-\rho}{\rho}\\ \pi(D_2,\mathbf{x}) &= n^2 \end{align*} \] The payoff \(\pi(D_1)\) arises because all of the \(n\) male offspring will mate with \((1-\rho)/\rho\) distinct females (on average) and engendering \(n\) offpsrings in each mating. On the other hand, \(\pi(D_2)\) arises because all \(n\) female offpsring would each give birth to \(n\) offspring in their lifetime. Finally, game theory prescribes that the payoff of the general strategy \(\sigma\) can be written as follows: \[ \begin{align*} \pi(\sigma,\mathbf{x}) &= p\cdot\pi(D_1,\mathbf{x}) + (1-p)\cdot \pi(D_2,\mathbf{x}) \\ &= pn^2 \frac{1-\rho}{\rho} + (1-p)n^2 \\ &= n^2\left[\left(\frac{1-2\rho}{\rho}\right)p+1\right] \end{align*} \] The ESS, by its very definition, should correspond to the value of \(p\) that results to the highest possible \(\pi(\sigma,\mathbf{x})\) given \(\rho\). From the above result, three cases can be enumerated:

• If \(\rho < \frac{1}{2}\), then \((1-2\rho)/\rho > 0\) so that \(p=1\) yields the highest possible value for \(\pi(\sigma,\mathbf{x})\)
• If \(\rho > \frac{1}{2}\), then \((1-2\rho)/\rho < 0\) so that \(p=0\) yields the highest possible value for \(\pi(\sigma,\mathbf{x})\)
• If \(\rho = \frac{1}{2}\), then \((1-2\rho)/\rho = 0\) so that any value of \(p\) yields the highest possible value for \(\pi(\sigma,\mathbf{x})\)

Since the female cannot really control the value of \(p\) (i.e., it does not have the will to choose the gender of offspring that it produces) then the game should be played without any regard of the specific value of \(p\). In other words, in finding the ESS of the population game, one should choose the case wherein any value of \(p\) will do. This case corresponds only when \(\rho = \frac{1}{2}\). Therefore, the ultimate consequence is that the ratio between males and females in the population is 50:50.

ABOUT THE AUTHOR:
Dranreb Earl Juanico is an Assistant Professor at the Ateneo de Manila University. He obtained his B.S., M.S., and Ph.D. in Physics at the University of the Philippines in 2002, 2004 and 2007, respectively.

OLYMPIAD CORNER

from the 57th Belarusian Mathematical Olympiad

Problem: Let \(O\) be the intersection point of the diagonals of the convex quadrilateral \(ABCD\), \(AO = CO\). Points \(P\) and \(Q\) are marked on the segments \(AO\) and \(CO\), respectively, so that \(PO = OQ\). Let \(N\) and \(K\) be the intersection points of the sides \(AB\), \(CD\) and lines \(DP\), \(BQ\) respectively. Prove that the points \(N\), \(O\), \(K\) are collinear.

Solution: 

Draw \(NM || KL || AC\). Let \(a = BO\), \(b = DO\), \(c = PO = OQ\), \(l = AO = OC\), \(x = KL\), \(u = OL\), \(y = NM\), \(v = OM\).

Since \(\Delta BOQ \sim \Delta BLK\), it follows that \[ \frac{x}{c} = \frac{a+u}{a} = 1 + \frac{u}{a} \] Furthermore, since \( \Delta DOC \sim \Delta DLK\), then \[ \frac{x}{l} = \frac{b-u}{b} = 1 - \frac{u}{b} \] Therefore \[ x\left( \frac{1}{c} - \frac{1}{l} \right) = u\left( \frac{1}{a} + \frac{1}{b} \right) \Rightarrow \frac{x}{u} = \frac{a+b}{ab} \cdot \frac{cl}{l-c} \] By a similar argument, we also obtain \[ \frac{y}{v} = \frac{a+b}{ab} \cdot \frac{cl}{l-c} \] Since \(\frac{x}{u} = \frac{y}{v}\), and \(\angle NMO = \angle KLO\), then \(\Delta ONM \sim \Delta OKL\). This implies that \(\angle NOM=\angle KOL\), which makes them vertical angles. Therefore, the points \(N\), \(O\) and \(K\) must be collinear.

PROBLEMS

19. If \(a_1 = 1\) and \[ a_{n+1} = \frac{1}{1+\frac{1}{a_n}}, n = 1, 2, \ldots, 2011, \] find the value of \[ a_1 a_2 + a_2 a_3 + a_3 a_4 + \ldots + a_{2011} a_{2012}. \]
    
20. One commercially available ten-button lock may be opened by depressing - in any order - the correct five buttons. Suppose that these locks are redesigned so that sets of as many as nine buttons or as few as one button could serve as combinations. How many additional combinations should this allow?
21. Let \(a\), \(b\) and \(c\) be three distinct positive integers. Show that among the numbers \[ a^5 b - ab^5, b^5 c - bc^5, c^5 a - ca^5, \] there must be one that is divisible by 8.

We welcome readers to submit solutions to the problems posed below for publication consideration. Solutions must be preceded by the solver's name, school affiliation and year level. The deadline for submission is February 4, 2012. 

SOLUTIONS

(for January 14 and 21, 2012)

13. \(AB\) is a chord in a circle with center \(O\) and radius 52 cm. The point \(M\) divides the chord \(AB\) such that \(AM = 63\) cm and \(MB = 33\) cm. Find the length of \(OM\) in cm. (Singapore Secondary Schools Mathematical Olympiads for Junior Section, 2003)
    (solved by Emman Joshua B. Busto [PSHS - Main] and Dianne S. Garcia [AA])
    
    
    SOLUTION: 
    

    
    Let \(D\) be a point on \(AB\) such that \(OD \perp AB\). We now have \[AD = BD = \frac{1}{2}(63+33) = 48.\] Thus \[ \begin{align*} MD = 48 - 33 &= 15 \\ {OD}^2 = {OB}^2 - {BD}^2 &= {52}^2 - {48}^2 = 400 \end{align*}  \] and \(OM = \sqrt{{OD}^2 + {MD}^2} = 25\) cm.
14. If \(a\) and \(b\) are positive real numbers such that \(a+b=1\), prove that \[\left(a+\frac{1}{a}\right)^2 + \left(b+\frac{1}{b}\right)^2 \geq \frac{25}{2}.\] (Taken from A Primer for Mathematics Competitions by Hitchcock and Zawaira)
    
    
    SOLUTION: 
    Note that \[\begin{align*} \left( a + \frac{1}{a} \right)^2 + \left( b + \frac{1}{b} \right)^2 &= a^2 + \frac{1}{a^2} + b^2 + \frac{1}{b^2} + 4 \\ &=(a+b)^2 - 2ab + \left( \frac{1}{a} + \frac{1}{b} \right)^2 - \frac{2}{ab} + 4 \\ &= 1 - 2ab + \frac{1-2ab}{(ab)^2} + 4. \end{align*} \] Furthermore, by the AM-GM inequality we have \[ ab \leq \left( \frac{a+b}{2} \right)^2 = \frac{1}{4}. \] Since \(a\) and \(b\) are positive real numbers, the second inequality yields the following: \[ \begin{align*} ab \leq \frac{1}{4} \Rightarrow -2ab \geq -\frac{1}{2}, \\ ab \leq \frac{1}{4} \Rightarrow \frac{1}{(ab)^2} \geq 16. \end{align*} \] Thus, we have, \[ \left( a + \frac{1}{a} \right)^2 + \left( b + \frac{1}{b} \right)^2 \geq 1 - \frac{1}{2} + \left(1 - \frac{1}{2}\right)16 + 4 = \frac{25}{2}. \]
15. For any non-negative integers \(m, n, p,\) prove that the polynomial \(x^{3m} + x^{3n+1}+x^{3p+2}\) has the factor \(x^2 + x + 1\). (Taken from Lecture Notes on Mathematical Olympiad Courses by Xu Jiagu)
    
    
    SOLUTION: 
    Consider \(f(y) = y^m - 1\). Since \(f(1) = 0\), we have \(y^m - 1 = (y-1)q(y)\). Taking \(y = x^3\), we have \[x^{3m}-1 = (x^3)^m - 1 = (x^3 - 1)q(x^3) = (x-1)(x^2+x+1)q(x^3). \] Also, \[ \begin{align*} x^{3n+1} - x &= x(x^{3n}-1), \\ x^{3p+2} - x^2 &= x^2(x^{3p}-1), \end{align*} \] implying that all of these terms have a factor of \(x^2+x+1\). Taking them together, we now have \[ x^{3m} + x^{3n+1} + x^{3p+2} = (x^{3m}-1) + (x^{3n+1} - x) + (x^{3p+2} - x^2) + (x^2+x+1), \] showing that the polynomial does have a factor of \(x^2+x+1\).
16. Let \(T\) be a triangle of perimeter 2, and \(a\), \(b\), \(c\) be the lengths of its three sides. Prove that \[ abc + \frac{28}{27} \geq ab + bc + ca \text{ and } abc + 1 \leq ab +bc +ca. \] (Ireland Mathematical Olympiad, 2003)
    
    
    SOLUTION: 
    Since \(a + b + c = 2\) then \(0 < a, b, c < 1\) hence \[ \begin{align*} 0 < (1-a)(1-b)(1-c) \leq \left( \frac{1-a+1-b+1-c}{3} \right)^3 = \frac{1}{27} \\ 0 < 1 - (a + b + c) + (ab +bc +ca) - abc \leq \frac{1}{27} \\ 0 < (ab + bc + ca) - 1 - abc \leq \frac{1}{27}, \end{align*} \] and thus both inequalities are shown to be true.
17. If \(a\), \(b\) are two different positive integers, and the two quadratic equations \[ (a-1)x^2 - (a^2+2)x +(a^2+2a) = 0, (b-1)x^2 - (b^2+2)x +(b^2+2b) = 0 \] have one common root, find the value of \[ \frac{a^b + b^a}{a^{-b} + b^{-a}}. \] (China Mathematical Competition for Primary Schools, 2003)
    
    
    SOLUTION: 
    We can deduce that \(a, b > 1\) where \(a \neq b\). Let \(r\) be the common root. We have \[ \begin{align*} (a-1)r^2 - (a^2+2)r+(a^2+2a) &= 0, \\ (b-1)r^2 - (b^2+2)r +(b^2+2b) &= 0, \end{align*} \] where \(r \neq 1\), since otherwise \(a = b = 1\), a contradiction.
    Using the two equations, we eliminate \(x^2\) and simplify to obtain \[ (a-b)(ab-a-b-2)(r-1) = 0,\] where \(a - b \neq 0\) and \(r \neq 1\), thus implying \(ab - a - b - 2 = 0\). Since this equation (and the final equation we are considering) is symmetric, we can assume \(a > b > 1\) without loss of generality. Then \(b = 1 + \frac{b}{a} + \frac{2}{a} \leq 3\), so \(b = 2, a = 4\).
    From there, \[ \frac{a^b + b^a}{a^{-b}+b^{-a}} = (a^b + b^a)\frac{a^bb^a}{a^b+b^a} = a^bb^a = 256.\]
18. In the convex quadrilateral \(ABCD\), the midpoints of \(BC\) and \(AD\) are \(E\) and \(F\) respectively. Prove that \([EDA] + [FBC] = [ABCD]\), where [] denotes the area of the region enclosed by the specified points. (IMO Shortlist, 1989)
    
    
    SOLUTION: 
    

    
    Suppose that \(AE\) and \(BF\) intersect at \(Q\) and \(CF\) and \(DE\) intersect at \(P\). Then it is sufficient to show that \([FQEP] = [ABQ] + [DPC]\). Let \(h_1\), \(h_2\) and \(h_3\) denote the heights of triangles \(ABE\), \(FBC\) and \(DEC\) respectively, giving us \(h_2 = \frac{1}{2}(h_1+h_3)\). Thus \[ \begin{align*} [FQEP] + [BEQ] + [ECP] &= [FBC] = \frac{1}{2}h_2BC \\ &= \frac{1}{4}(h_1+h_3)BC \\ &= \frac{1}{4}h_1(2BE) + \frac{1}{4}h_3(2EC) \\ &=([ABQ] + [BEQ]) + ([DPC] + [ECP]), \end{align*} \] which gives us the desired equality.

For those taking Inequalities

The handout for the module so far can be found by clicking here.

The Pythagorean Theorem and Special Relativity (Tuklas Vol. 13, No. 6 - January 21, 2012)

THE PYTHAGOREAN THEOREM AND SPECIAL RELATIVITY

One of the greatest hallmarks of 20th century physics was the development of a branch of Modern Physics called "Special Relativity." Briefly, it is a theory of space, time and light-– all of them bridging the gap and asking the most fundamental questions in physics. The Theory of Special Relativity was proposed in 1905 by Albert Einstein, then an unknown clerk in a Swiss patent office. In that moment he made three important breakthroughs in Physics: a consolidation of various ideas individually contributed by scientific giants including Lorentz, Poincare, and Maxwell, among others. Of course with great unexpected success also comes some controversies and issues that didn't sit well with fellow scientists and philosophers. However, various experiments have been conducted to this day and have affirmed the three very important contributions of Albert Einstein. The year 1905 was then known as Annus Mirabilis, or "Year of Wonders."
The propositions of this theory are far-reaching and almost impossible to understand. Many of the theory's consequences are counter-intuitive, but the basic foundations and proofs of some propositions are surprisingly elementary. This article aims to connect the astoundingly simple mathematics that gave rise to a superstar. 
We consider two rectangular and parallel plates in space that emit light pulses. The light pulse emitted from one plate is caught and immediately reflected back to the original plate. The time it takes for the light to travel from plate 1 to 2 and back to 1 is \(\Delta t_0\). Since the light pulse makes a round trip, it travels a distance \(2d\). If the speed of light is \(c\), then \(\Delta t_0 = \frac{2d}{c}\). Figure 1 shows the current setup of our thought experiment. 

What then if this setup is placed in a rocket that flies horizontally with a sufficiently fast velocity \(v\)? In order to understand this better, we will welcome the help of two laboratory assistants Albert and Hendrik. Albert stays on the ground and watches the rocket fly past him, while Hendrik wants a joyride and rides the rocket. The experiment of the light pulses is activated while both gentlemen watch, and the rocket is flying horizontally. (And oh yes, Albert must see Hendrik for the entire duration of the trip for the purposes of our thought experiment!) While Hendrik is perhaps enjoying inflight service or eating junk food, he will observe that both he and the plates aren't moving any farther from each other. Therefore what he will see is exactly the same setup as Figure 1. 
Albert's observations, on the other hand, will be totally different from Hendrik's. Since Albert is sitting down on Earth and perhaps doing Facebook or combing his funky hair, he will see that the light pulses will travel in a way illustrated in Figure 2. 

\(v\Delta t\) here is the distance travelled by the rocket. \(\Delta t_0\) and \(\Delta t\) are two different things!
Hendrik Lorentz first suggested this proposition, and by using an incredibly simple Pythagorean Theorem, he was able to arrive at the following relationships: \[ L= \sqrt{d^2+\left (\frac{v\Delta t}{2} \right )^2}.\]
From the equation used in Figure 1, the following equation is derived: \[ \Delta t = \frac{\Delta t_0}{\sqrt{1-v^2/c^2}}. \]
The consequences of this equation are difficult to stomach. It tells us that if \(v = c\), then the equation becomes undefined! This brings us a natural speed limit equal to the speed of light, \(c\). For more human speeds, \(v \ll c\), the effects of this equation is not immediately felt. 
Let us say that I have a rocket travelling at 99% the speed of light, \(v= 0.99c\). Inside the rocket is an observer telling me it takes 1 second for light to travel roundtrip between plates. For an observer on the ground, how long will it take for the light to make a roundtrip? Using the same equation, it will take 2.29 seconds! This equation is called the Time Dilation Equation and has been proven to be accurate in many experiments around the world. 
Still from Pythagorean Theorem and the Time Dilation Equation, a natural consequence would be the following phenomenon: \[ L= L_0 \sqrt{1-\frac{v^2}{c^2}}. \]
For those who are craving for an optical illusion, this is known as the Length Contraction Equation! 
Maybe the only time we will be able to see these phenomena is when our cars or airplanes are flying at at least around 70% the speed of light -- that is around 210,000,000 m/s! Bon Voyage!

ABOUT THE AUTHOR:
Clark Kendrick Go is an Instructor at the Ateneo de Manila University. He is currently taking his M.S. in Physics at the same university.

OLYMPIAD CORNER

from the Asian Pacific Mathematics Olympiad, 2005

Problem: Prove that there exists a triangle which can be cut into 2005 congruent triangles.

Solution: 

Suppose that one side of a triangle has length \(n\). Then it can be cut into \(n^{2}\) congruent triangles which are similar to the original triangle, the ratio of the corresponding sides given by \(n:1\). 
Since \(2005\) is a product of two primes (\(5\) and \(401\)) both of which are of the form \(4k+1\), then it can be represented as a sum of two integer squares \[ \begin{align*} 2005 &= 5\times 401 \\ &= \left( 2^{2}+1\right) \left( 20^{2}+1\right)  \\ &= 40^{2}+20^{2}+2^{2}+1 \\ &= \left( 40-1\right) ^{2}+2\times 40+20^{2}+2^{2} \\ &= 39^{2}+22^{2}. \end{align*} \] Let \(ABC\) be a right-angled triangle with legs \(AB\) and \(BC\) having lengths \(39\) and \(22\), respectively. We draw the altitude \(BK\), which divides \(ABC\) into two similar triangles. Now we divide \(ABK\) into \(39^{2}\) congruent triangles as described above and \(BCK\) into \(22^{2}\) congruent triangles.
Since \(ABK\) is similar to \(BKC\), then all \(39^{2}+22^{2}= 2005\) triangles will be congruent.

PROBLEMS

16. Let \(T\) be a triangle of perimeter 2, and \(a\), \(b\), \(c\) be the lengths of its three sides. Prove that \[ abc + \frac{28}{27} \geq ab + bc + ca \text{ and } abc + 1 \leq ab +bc +ca. \]
    
17. If \(a\), \(b\) are two different positive integers, and the two quadratic equations \[ (a-1)x^2 - (a^2+2)x +(a^2+2a) = 0, (b-1)x^2 - (b^2+2)x +(b^2+2b) = 0 \] have one common root, find the value of \[ \frac{a^b + b^a}{a^{-b} + b^{-a}}. \]
18. In the convex quadrilateral \(ABCD\), the midpoints of \(BC\) and \(AD\) are \(E\) and \(F\) respectively. Prove that \([EDA] + [FBC] = [ABCD]\), where [] denotes the area of the region enclosed by the specified points.

We welcome readers to submit solutions to the problems posed below for publication consideration. Solutions must be preceded by the solver's name, school affiliation and year level. The deadline for submission is January 28, 2012. 

Some Announcements

The final module handout for those who took Methods of Proof can be found by clicking here (the previous link no longer works). It will be available until the last PEM (plenary) session on February 11, 2012.

Once again, we encourage the participants to submit solutions to the Tuklas problems (deadline for problems included in the 5th Tuklas issue is on January 28, 2012). Those who are able to answer at least 8 problems will receive a special award. :)

Ant Colony Optimization in Vertex Coloring (Tuklas Vol. 13, No. 5 - Jan. 14, 2012)

ANT COLONY OPTIMIZATION IN VERTEX COLORING

Advances in science and technology are not always driven by human genius alone. Sometimes, inspiration can be obtained from the other creatures around us which, in their own little worlds, are experts. This was what happened with Daniel Costa and Alain Hertz when they developed a graph coloring method based on the behavior of ants. They presented this method in the 1997 article "Ants can colour graphs" in The Journal of the Operational Research Society.

Preliminaries: The Vertex Coloring Problem
A graph is a set of vertices (or nodes) together with a set of edges (lines or arcs) that each connect two vertices. In particular, a simple graph is a graph where there is only at most one edge between two vertices and that has no loops (edges that begin and end on the same vertex). Some examples are given below.

Figure 1: (a) A simple graph. (b) A non-simple graph.

Furthermore, the vertex coloring problem (also popularly known as the graph coloring problem) aims to obtain the minimum number of colors required to color the vertices of a (simple) graph in such a way that no two vertices have the same color.

Figure 2: Optimal coloring of a graph.

For small graphs, the vertex coloring problem is easy; in general, this problem is considered to be difficult. Most developments revolve around what we call heuristics which generate sub-optimal solutions only, i.e., solutions that might not be the best but are considered to be good. Among these heuristics are constructive methods that color each vertex while trying to keep the number of colors used as small as possible.

The Behavior of Real Ants
In 1991, Alberto Colorni, Marco Dorigo and Vittorio Maniezzo introduced in their paper "Distributed optimization by ant colonies" an optimization algorithm that is based on the observations of real ants in the environment. This algorithm is now called Ant Colony Optimization.
Ant colony optimization is inspired by the observation that a colony of ants have the tendency to move along an organized path. This self-organizing behavior of ants is due to a chemical substance called a pheromone that they leave on their trails when they move from one place to another. The general term for this indirect communication done by altering the environment is stigmergy. For ants, stigmergy is done using trail pheromones.
Ants that encounter a path with a high pheromone deposit are more likely to choose that path over other available paths. This process of choosing paths biased by trail pheromones allow for a group of ants to converge on a single path as observed in natural situations.
What is interesting is that ants usually converge on the shortest path between their source and destination. A simple explanation for this is that over time, the trail pheromone starts to evaporate which reduces the trail's attractive strength. Because long paths allow for more pheromone evaporation, pheromone density becomes higher on shorter paths than longer ones. In turn, the shortest path becomes more attractive until all the ants converge on it.

Figure 3: Ants converge on the shortest path.

Ant Colony Optimization
The idea behind ant colony optimization is to use artificial ants (called agents) that are also capable of indirect communication or what we can call artificial stigmergy. However, the agents have additional capabilities that real ants do not have. These additional capabilities are 

1. the ability to determine the quality of solutions,
2. deposit amount of pheromones based on solution quality,
3. and access to colony-wide information, in particular, the best solution obtained so far.

The premise that a real ant colony might not converge on the shortest path makes ant
colony optimization a probabilistic algorithm, or a heuristic.

Ant Colony Optimization in Vertex Coloring
Costa and Hertz called the ant algorithm for the vertex coloring problem ANTCOL. The ANTCOL algorithm uses a \colony" of arti cial ants to color the vertices of the graph. ANTCOL can be outlined as follows:

1. Each virtual ant from the colony will color the graph using a known constructive heuristic. When they obtain a solution, each will record the quality of the solution (i.e. a better solution is one with fewer colors used).

2. Based on the quality of the solution obtained, each virtual ant will place virtual pheromones on each pair of vertices. If two non-adjacent vertices have the same color, then pheromones will be placed on that pair through a virtual matrix. Here, pheromones are used to reinforce the desirability of coloring two non-adjacent vertices with the same color.

3. Each virtual ant accesses the colony-wide information to determine which pairs of non-adjacent vertices are desirable to be colored using the same color. With this new information, each ant repeats step 1.

Performing several rounds of ANTCOL will most likely return an optimal coloring of the graph given.

This evolutionary technique and its successors are important because coloring the vertices of a graph has various applications in real life situations such as scheduling, allocation and even recreational activities like Sudoku.

ABOUT THE AUTHOR:
Mark Tolentino is an Assistant Instructor at the Ateneo de Manila University. He is currently on leave, taking his Ph.D. in Mathematics at the same university.

REFERENCES:

Colorni, Alberto, Marco Dorigo and Vittorio Maniezzo. "Distributed optimization by ant colonies." Proceedings of the First European Conference on Arti cial Life Paris. Ed. P Bourgine FJ Varela. Cambridge, Massachussetts: MIT/Press/Bradford Books, 1991. 134-142.
Costa, Daniel and Alain Hertz. "Ants can colour graphs." The Journal of the Operational Research Society 48.3 (1997): 295-305.
Dorigo, Marco and Thomas Stutzle. Ant colony optimization. Cambridge: MIT Press, 2004.

OLYMPIAD CORNER

from the XXXIX Republic Competition of Mathematics in Macedonia Class I, 1999

Problem: The sum of three integers \(a, b\) and \(c\) is 0. Prove that \(2a^4+2b^4+2c^4\) is the square of an integer.

Solution: 
Let \(p(x) = x^3 + sx^2 + qx + r\) be a third degree polynomial having \(a, b\) and \(c\) as roots. Since \(s = -(a+b+c) = 0\), we can rewrite \(p(x) = x^3+qx+r\). Note also that \(ab+bc+ca = q\), a fact we will use later.

Since \(a, b\) and \(c\) are roots, \(p(a) = p(b) = p(c) = 0\) or \[ a^3 + qa + r = 0, \quad \quad \quad b^3 + qb + r = 0, \quad \quad \quad c^3 + qc + r = 0. \] Multiply each equation by \(2a, 2b\) and \(2c\) respectively. Then add. We have \[ \begin{align*} 2a(a^3+qa+r) + 2b(b^3+qb+r) + 2c(c^3+qc+r) &= 2a(0)+2b(0) + 2c(0) \\ 2(a^4+b^4+c^4) + 2q(a^2+b^2+c^2) + 2r(a+b+c) &= 0 \\ 2a^4+2b^4+ 2c^4 &= -2q(a^2+b^2+c^2) \end{align*} \] Now, note that \(0 = (a+b+c)^{2} = (a^{2}+b^{2}+c^{2}) + 2(ab+bc+ca)\). It follows that \[ a^{2}+b^{2}+c^{2} = -2(ab+bc+ca) = -2q. \] Therefore, \(2a^{4} + 2b^{4} + 2c^{4} = -2q(-2q) = (2q)^{2}\), so \(2a^{4} + 2b^{4} + 2c^{4}\) really is the square of an integer.

PROBLEMS

13. \(AB\) is a chord in a circle with center \(O\) and radius 52 cm. The point \(M\) divides the chord \(AB\) such that \(AM = 63\) cm and \(MB = 33\) cm. Find the length of \(OM\) in cm.
    
14. If \(a\) and \(b\) are positive real numbers such that \(a+b=1\), prove that \[ \left( a+\frac{1}{a} \right)^2 + \left( b+\frac{1}{b} \right)^2 \geq \frac{25}{2}.\]
15. For any non-negative integers \(m, n, p,\) prove that the polynomial \(x^{3m} + x^{3n+1}+x^{3p+2}\) has the factor \(x^2 + x + 1\).

We welcome readers to submit solutions to the problems posed below for publication consideration. Solutions must be preceded by the solver's name, school affiliation and year level. The deadline for submission is January 28, 2012. 

SOLUTIONS

(for December 3 and 10, 2011)

7. Evaluate\[ \frac{1}{(1+1)!} + \frac{2}{(2+1)!} + \ldots + \frac{n}{(n+1)!}, \] where \(n\) is any natural number.
   (solved by Ferdinand John S. Briones [MSHS], Emman Joshua B. Busto [PSHS - Main], Dianne Garcia [AA], Albert Jason Z. Olaya [PSHS - Main], Gerald M. Pascua [PSHS - Main] and Marisse T. Sonido [AA])
   
   
   SOLUTION: 
   Simply note that for \(1 \leq k \leq n\), we have \[ \frac{k}{(k+1)!} = \frac{k+1-1}{(k+1)!} = \frac{1}{k!} - \frac{1}{(k+1)!},\] Thus the original sum reduces to \[ 1 - \frac{1}{2!} + \frac{1}{2!} - \frac{1}{3!} + \ldots + \frac{1}{(n-1)!} - \frac{1}{n!} + \frac{1}{n!} - \frac{1}{(n+1)!} = 1 - \frac{1}{(n+1)!}. \]
8. Suppose that the incircle of \(ABC\) is tangent to the sides \(BC, CA, AB\) at \(D, E, F\) respectively. Prove that \[ EF^2 + FD^2 + DE^2 \leq \frac{s^2}{3},\] where \(s\) is the semiperimeter of \(ABC\). (Taken from Inequalities by Manfrino, Ortega, and Delgado)
   (solved by Ferdinand John S. Briones [MSHS])
   
   
   SOLUTION: 
   Let \(R\), \(r\) and \(s\) denote the circumradius, inradius and semiperimeter of triangle \(ABC\), respectively. Note that \(\text{area}(ABC)=\frac{abc}{4R}=sr\). We use the AM-GM inequality to obtain \[2s = a+b+c \geq 3\sqrt[3]{abc} = 3\sqrt[3]{4Rrs}. \] By manipulation and the fact that \(R \geq 2r\), we have \( 8s^3 \geq 27(4Rrs) \geq 27(8r^2s)\), giving us \(s \geq 3\sqrt{3}r\).
   Since the incircle of \(ABC\) is the circumcircle of \(DEF\), we can apply Leibniz's inequality to \(DEF\) and obtain \[ {EF}^2 + {FD}^2 + {DE}^2 \leq 9r^2, \] and combining with the previous inequality gives us the desired solution.
9. On the blackboard some student has written 17 natural numbers, and their units digits are inside the set \(\{0, 1, 2, 3, 4\}\). Prove that one can always select out 5 numbers from them such that their sum is divisible by 5. (China Mathematical Competitions for Secondary Schools, 2005)
   (solved by Ferdinand John S. Briones [MSHS])
   
   
   SOLUTION: 
   Group the 17 numbers into 5 sets according to their units digit. If each set contains at least one number, then taking a number from each set yields a sum whose units digit ends in 0, hence divisible by 5. If a particular set is empty, that means each set contains at least 4 numbers each with one set having 5 numbers, and these 5 numbers will yield our desired result. Two or more empty sets will yield the same result.
10. Let \(a, b, c\) be positive real numbers with \(abc = 8\). Prove that \[\frac{a-2}{a+1} + \frac{b-2}{b+1} + \frac{c-2}{c+1} \leq 0.\](Romania, 2008)
    (solved by Ferdinand John S. Briones [MSHS])
    
    
    SOLUTION: 
    We wish to show that \[ \begin{align*}
    \frac{a-2}{a+1} + \frac{b-2}{b+1} + \frac{c-2}{c+1} \leq 0 &\Leftrightarrow 3-3\left(\frac{1}{a+1} + \frac{1}{b+1} + \frac{1}{c+1}\right) \leq 0 \\
    &\Leftrightarrow 1 \leq \frac{1}{a+1} + \frac{1}{b+1} + \frac{1}{c+1}. \end{align*} \] By substituting \(a = \frac{2x}{y}\), \(b = \frac{2y}{z}\), \(c = \frac{2z}{x}\) we have \[ \begin{align*} \frac{1}{a+1} + \frac{1}{b+1}+\frac{1}{c+1} &= \frac{1}{\frac{2x}{y} + 1}+\frac{1}{\frac{2y}{z} + 1}+ \frac{1}{\frac{2z}{x}+1} \\
    &= \frac{y}{2x+y} + \frac{z}{2y+z} + \frac{x}{2z+x} \\
    &= \frac{y^2}{2xy+y^2} + \frac{z^2}{2yz+z^2} + \frac{x^2}{2xz+x^2} \\
    &\geq \frac{(x + y + z)^2}{2xy+y^2 + 2yz+z^2 + 2xz+x^2} = 1, \end{align*} \] by the Cauchy-Schwarz inequality in Engel form.
    As an alternative, we can prove by contradiction. Suppose \[1 > \frac{1}{a+1} + \frac{1}{b+1} + \frac{1}{c+1}.\] Simplifying, we have \[ \begin{align*} 1 &> \frac{1}{a+1} + \frac{1}{b+1} + \frac{1}{c+1} \\ &= \frac{(b+1)(c+1) + (a+1)(c+1) + (a+1)(b+1)}{(a+1)(b+1)(c+1)} \\ (a+1)(b+1)(c+1) &> (b+1)(c+1) + (a+1)(c+1) + (a+1)(b+1) \end{align*} \] which, after simplifying and using the fact that \(abc = 8\), yields \[ \frac{a+b+c}{3} < 2 = \sqrt[3]{abc}, \] which is false by the AM-GM inequality, hence the contradiction.
11. Let \(\{x\} = x - \left\lfloor x \right\rfloor\) denote the fractional part of \(x\). Prove that for every natural number \(n\), \[ \sum_{j=1}^{n^2} \left\{ \sqrt{j} \right\} \leq \frac{n^2 - 1}{2}.\](Russia, 1999)
    (solved by Ferdinand John S. Briones [MSHS])
    
    
    SOLUTION: 
    We prove via induction on \(n\). When \(n = 1\), the inequality holds. Assuming it is true for \(n\), we prove it is true for \(n+1\). Note that \(n < \sqrt{n^2 + i} < n+1\) for \(i = 1, 2, \ldots , 2n\), giving us  \[ \left\{ \sqrt{n^2 + i} \right\} = \sqrt{n^2+1} - n < \sqrt{n^2 + i + \left( \frac{i}{2n} \right)^2} - n = \frac{i}{2n}. \] Thus \[ \begin{align*}
    \sum_{j=1}^{(n+1)^2}\left\{\sqrt{j}\right\} &= \sum_{j=1}^{n^2}\left\{\sqrt{j}\right\}   + \sum_{j = n^2 +1}^{(n+1)^2} \left\{ \sqrt{j} \right\} \leq \frac{n^2 - 1}{2} + \frac{1}{2n} \sum_{i=1}^{2n}{i} \\
    &= \frac{(n+1)^2 -1}{2}.  \end{align*} \]
12. Show that there are infinitely many ordered integral pairs \((a,b)\) such that \(\frac{a^3+b^3}{a-b}\) is a perfect square. (Taken from A Primer for Mathematics Competitions by Hitchcock and Zawaira)
    (solved by Ferdinand John S. Briones [MSHS] and Gerald M. Pascua [PSHS - Main])
    
    
    SOLUTION: 
    Setting \(b = 0\), we have \[ \frac{a^3+b^3}{a-b} = \frac{a^3}{a} = a^2,\] which is always a perfect square for any integer \(a\), giving us the integral pair \( (a,0) \).

Class List (Students)

PROGRAM FOR EXCELLENCE IN MATHEMATICS 2011-2012

Part II: January 14 – February 4, 2012

Module 4
Inequalities
Schedule: Sat, 9:30-11:30AM
Teacher: Jesus Lemuel Martin

Room: B 206

#	School	Last Name	First Name	M.I.	Year Level	1st Module	Attend. (%)
1	Assumption College, San Lorenzo, Makati	Araneta	Andrea		1	6	100%
2	Assumption College, San Lorenzo, Makati	Espinueva	Charmaine		2	6	100%
3	Assumption College, San Lorenzo, Makati	Ruiz	Lauren		1	6	100%
4	Ateneo High School	Buban	Julian Mikhael	A.	4	2	80%
5	Ateneo High School	Del Mundo	Jo Adrian	P.	1	6	20%
6	Ateneo High School	Eala	John Patrick	B.	1	3	80%
7	Ateneo High School	Manguiat	Hans Rhenzo	N.	2	6	80%
8	Caloocan High School	Ballesteros	Mary Joy	B.	2	3	100%
9	Caloocan High School	Callagon	Edgardo Jr.	R.	1	3	100%
10	Caloocan High School	Concepcion	Kenneth	N.	2	3	100%
11	Caloocan High School	Ramos	Lindsay Marie	C.	1	3	100%
12	Colegio San Agustin - Makati	Arevalo	Ma. Veronica Pia	N.	2	3	40%
13	Colegio San Agustin - Makati	Castillo	Antonio Ramon	L.	3	3	60%
14	Colegio San Agustin - Makati	Jasarino	Liam Eliel	D.B.	2	3	80%
15	Colegio San Agustin - Makati	Orense	Jessica Mae	C.	4	3	40%
16	Colegio San Agustin - Makati	Rodolfo	Raphael Cecilio	S.		3	60%
17	Colegio San Agustin - Makati	Tapel	Leon III	L.	1	3	100%
18	PAREF Southridge	Gonzales	Juan Paolo Domingo	I.	3	6	60%
19	PAREF Southridge	Mapa	Jose Ignacio	P.	3	6	80%
20	Philippine Pasay Chung Hua Academy	Uyyco	Adrian Jan	B.	3	1	80%
21	Philippine Pasay Chung Hua Academy	Valino	Ma. Ricka Lorenn	O.	1	1	100%
22	San Sebastian College Manila	Abuel	Kernel	T.	3	3	40%
23	San Sebastian College Manila	Trinidad	Jessu	R.	3	3	40%
24	St. Matthew College	Felix	Shean Emanuel	I.	4	1	100%
25	St. Paul College, Pasig	Hong	Jungwon		1	3	80%
26	St. Paul College, Pasig	Ochoa	Michelle Marie	T.	2	1	80%
27	St. Paul College, Pasig	Onglao	Andrea	S.	1	3	60%
28	St. Paul College, Pasig	Varela	Natalia	M.	2	1	80%
29	St. Paul University Quezon City	de Guzman	Adrinne	L.	2	3	80%
30	St. Paul University Quezon City	Gatdula	Bryan Anthony	E.	2	3	80%
31	St. Paul University Quezon City	Gonzales	Janine Mae	D.	2	3	60%
32	St. Paul University Quezon City	Janoras	Craig Jarred	L.	4	3	80%
33	St. Paul University Quezon City	Mendoza	Gregory Emmanuel	J.	2	1	80%
34	St. Paul University Quezon City	Niño	Cleo Caoile			3	60%
35	St. Theresa’s College Quezon City	Magsino	Clarisse Anne	C.	3	1	80%
36	St. Theresa's College Quezon City	Abog	Maryanne		3	1	100%

Module 5

Circles

Schedule: Sat, 9:30-11:30AM

Teacher: Dr. Eden Delight Provido

Room: CTC 307

#	School	Last Name	First Name	M.I.	Year Level	1st Module	Attend. (%)
1	Assumption Antipolo	Bartolome	Adrienne	S.	2	3	60%
2	Assumption Antipolo	Garcia	Dianne	S.	4	6	80%
3	Assumption Antipolo	Peñaranda	Julia	A.	2	3	60%
4	Assumption Antipolo	Sonido	Marisse		3	6	100%
5	Caloocan High School	Cambri	Joshua	E.	4	6	100%
6	Caloocan High School	Esguerra	Jeanne Mallary	M.	3	6	80%
7	Caloocan High School	Estorque	Kim Lawrence	L.	4	6	100%
8	Caloocan High School	Uy	Micah Ella	R.	3	6	100%
9	Immaculate Conception Academy	Chan	Katrina		2	6	60%
10	Immaculate Conception Academy	Chua	Geraldine Shay	K.	1	1	80%
11	Immaculate Conception Academy	Go Tiong	Mikaela	T.	1	6	60%
12	Immaculate Conception Academy	Kaw	Aitana		3	6	60%
13	Immaculate Conception Academy	Sia	Charlene May	M.	4	1	80%
14	Immaculate Conception Academy	Siyvan	Vanessa		2	6	80%
15	Lourdes School of Mandaluyong	Dela Cruz	Francisco Miguel	M.	1	2	100%
16	Lourdes School of Mandaluyong	Flores	Luis Miguel	C.	1	2	80%
17	Malanday National School	Maniba	John Bart		2	1	100%
18	Manila Science High School	Dimatatac	Mary Joy		3	6	100%
19	Manila Science High School	Flores	Elijah Miguel	P.	1	1	100%
20	Manila Science High School	Ocampos	Ares Abigail	S.	1	1	100%
21	Manila Science High School	Segui	Mary Elizabeth	R.	3	6	100%
22	Philippine Pasay Chung Hua Academy	Bactat	Jamie	C.	2	1	100%
23	Philippine Pasay Chung Hua Academy	Bactat	Jazmine	C.	3	1	100%
24	Philippine Pasay Chung Hua Academy	Chua	Elaiza Mae	D.	2	1	60%
25	Philippine Pasay Chung Hua Academy	Lafiguera	Joella Marie	J.	1	1	100%
26	Philippine Pasay Chung Hua Academy	Lee	Seung Jun		4	6	80%
27	Philippine Pasay Chung Hua Academy	Magpantay	Christian Joseph		4	6	80%
28	St. Paul College, Pasig	Victorino	Clara Eufracia	R.	4	1	40%
29	St. Paul College, Pasig	Vilaga	Patricia Joyce	T.	4	1	60%
30	Uno High School	Cu	Aileen Jennifer		3	2	40%
31	Uno High School	Cu	Bernice Joy	C.	1	2	80%
32	Uno High School	Ong	Paul Ryan	S.	2	1	80%
33	Uno High School	Ong	Ezekiel Christian	C.	1	2	60%
34	Uno High School	Solis	Sean	G.	2	1	100%
35	Uno High School	Yap	Michaelben		3	2	60%

Module 6

Triangles and Trigonometry
Schedule: Sat, 8:30AM-12:30PM
Teacher: Eumir Alexis Angeles

Room: B 309

#	School	Last Name	First Name	M.I.	Year Level
1	Olongapo City National High School	Almandrez	Orlando Jr.		2
2	Olongapo City National High School	Avila	Jake		3
3	Olongapo City National High School	Borcelas	Angelica		3
4	Olongapo City National High School	Bueno	Cristabelle Alessandra		3
5	Olongapo City National High School	Bugay	Sefina Glisa		4
6	Olongapo City National High School	Cerrada	Zadkiel		4
7	Olongapo City National High School	Custodio	Miko Isaiah		1
8	Olongapo City National High School	Espano	Ron Miguel	L.
9	Olongapo City National High School	Garcia	Vincent Paul		3
10	Olongapo City National High School	Laborce	Louis Henry
11	Olongapo City National High School	Luna	Micah jonina		4
12	Olongapo City National High School	Mormeto	Gabriel		3
13	Regional Science High School III	Almandrez	Orlando	S.
14	Regional Science High School III	Alvarez	Alyssa Noelle	A.
15	Regional Science High School III	Bayol	Gerard Arvin	G.
16	Regional Science High School III	Besilia	Aena Marli	C.
17	Regional Science High School III	Bilog	Miguel Luis	V.
18	Regional Science High School III	Bolagao	Rhodelle Mariah	F.
19	Regional Science High School III	Buron	Camille Joy	N.
20	Regional Science High School III	Canlas	Johanne Veatrice
21	Regional Science High School III	Capili	Johanna Lindsay	P.
22	Regional Science High School III	Chua	Carlos Marc
23	Regional Science High School III	Custodio	Paul Michael
24	Regional Science High School III	Deldio	Rhusnie
25	Regional Science High School III	Dizon	Miguel Martin	M.I.
26	Regional Science High School III	Doropan	Mirasol Lily	G.
27	Regional Science High School III	Elayda	Grace Chelsea
28	Regional Science High School III	Fantone	Maribelle
29	Regional Science High School III	Galapon	Fredrick Angelo	R.
30	Regional Science High School III	Gamboa	Denise
31	Regional Science High School III	Limpo	Mechaela Tania	Y.
32	Regional Science High School III	Malinay	Augustus Jr.
33	Regional Science High School III	Mendoza	Janica Rose	G.
34	Regional Science High School III	Menor	Regina Chloe	Q.
35	Regional Science High School III	Miguel	Karen	D.
36	Regional Science High School III	Mostacho	Hannah Lousanne	G.
37	Regional Science High School III	Patagan	Christian Jon	O.
38	Regional Science High School III	Publico	Leanne Caryl	E.
39	Regional Science High School III	Quilala	Jeanette
40	Regional Science High School III	Reyes	Charles
41	Regional Science High School III	Seo	Jacob
42	Regional Science High School III	Umbina	Jalan joy	B.

Module 7
Polynomials, Sequences, and Equations
Schedule: Sat, 9:30-11:30AM
Teacher: Mrs. Eurlyne Domingo

Room: SEC A 204

#	School	Last Name	First Name	M.I.	Year Level	1st Module	Attend. (%)
1	Assumption Antipolo	Casillan	Megan	E.	3	1	100%
2	Assumption Antipolo	Enriquez	Erika Antonette	T.	1	1	100%
3	Assumption Antipolo	Tayag	Gabrielle	V.	1	3	100%
4	Assumption Antipolo	Yap	Gabrielle	F.	3	3	100%
5	Colegio de Sta. Rosa, Makati	Aceron	Loubill		3	3	40%
6	Colegio de Sta. Rosa, Makati	Agoncillo	Nadine Therese		1	3	40%
7	Colegio de Sta. Rosa, Makati	Agraan	Kathrina	A.	3	3	60%
8	Colegio de Sta. Rosa, Makati	Boado	Krysten		2	3	40%
9	Colegio de Sta. Rosa, Makati	Perez	Gail Coleen		1	3	40%
10	Colegio de Sta. Rosa, Makati	Tamayo	Sabrina	V.	4	3	40%
11	Colegio de Sta. Rosa, Makati	Villamiel	Estella		4	3	20%
12	Colegio San Agustin - Makati	Del Prado	Katherine	D.	1	2	100%
13	Lourdes School of Mandaluyong	Alvarez	Michael Bryan	B.	2	2	80%
14	Lourdes School of Mandaluyong	Capistrano	Cesar Lorenzo	G.	4	2	80%
15	Lourdes School of Mandaluyong	Catolico	Ignacio Luigi	C.	4	2	60%
16	Lourdes School of Mandaluyong	Chavez	Miguel Franco	B.	3	2	80%
17	Lourdes School of Mandaluyong	Cruz	Jules Cyber	G.	2	2	80%
18	Lourdes School of Mandaluyong	Delfin	Mikhail Kevin Derrick	D.	3	2	80%
19	San Sebastian College Manila	Ceron	Richard Khym	F.	2	2	20%
20	San Sebastian College Manila	Noriega	Kyle Trixia	E.	2	2	80%
21	San Sebastian College Manila	Perez	Kay	G.	1	2	80%
22	San Sebastian College Manila	Taguinod	John Danyael	B.	1	2	80%
23	St. Paul College, Pasig	Tan	Bianca Nichole	A.	3	3	60%
24	St. Paul College, Pasig	Varela	Sofia	M.	3	3	60%
25	St. Scholastica's College, Manila	Avila	Anna Maria	M.	3	2	100%
26	St. Scholastica's College, Manila	Lucena	Nicole Angelica	N.	3	2	100%
27	St. Scholastica's College, Manila	Masigan	Christine Joy	B.	3	2	80%
28	St. Scholastica's College, Manila	Miranda	Ysabelle Rei	P.	3	2	80%
29	St. Theresa's College Quezon City	Arevalo	Eunice		2	2	100%
30	St. Theresa's College Quezon City	Bautista	Therese		1	1	80%
31	St. Theresa's College Quezon City	Estevez	Pauline Bernadette	O.	4	1	100%
32	St. Theresa's College Quezon City	Fernando	Isabelle Maria		4	1	60%
33	St. Theresa's College Quezon City	Guanlao	Alyssa		2	2	80%
34	St. Theresa's College Quezon City	Teotico	Janine		1	1	80%
35	Xavier School	Dy	Aaron		3	6	20%
36	Xavier School	See	Kyle Stephen		4	6	20%
37	Xavier School	Siy	Lorenzo Ramon	C.	1	1	80%
38	Xavier School	Uy	Trevor jan	T.	1	1	100%

Module 8

Advanced Problem Solving and Training for Olympiads
Schedule: Sat, 9:30-11:30AM
Teacher: Dr. Flordeliza Francisco

Room: SEC A 205

#	School	Last Name	First Name	M.I.	Year Level	1st Module	Attend. (%)
1	Ateneo High School	Berba	Jose Daniel	P.	4	2	80%
2	Ateneo High School	Quiogue	Lorenzo Gabriel	D.	3	6	60%
3	Ateneo High School	Sin	Immanuel Gabriel	M.	2	3	100%
4	Colegio San Agustin - Makati	Grau	Maria Isabel	D.	4	2	40%
5	Manila Science High School	Arias	Christlyn Faith	H.	2	2	80%
6	Manila Science High School	Briones	Ferdinand	S.	4	3	80%
7	Manila Science High School	Jamir	Jasper	S.	2	2	100%
8	Manila Science High School	San Pedro	Simon Stephen	S.	4	3	60%
9	Philippine Science High School - Main	Busto	Emman Joshua	B.	1	6	100%
10	Philippine Science High School - Main	Olaya	Albert Jason	Z.	1	6	80%
11	Philippine Science High School - Main	Pascua	Gerald	M.	1	6	100%
12	St. Paul University Quezon City	Caragay	Michael Christopher	D.	3	6	100%
13	St. Paul University Quezon City	Santiago	Ma. Regina	T.	3	2	100%
14	Uno High School	Go	Diane Nicole		4	2	40%
15	Uno High School	Ong	Samuel Christian	C.	4	2	60%
16	Xavier School	Co	John		2	2	60%