Monday, January 28, 2013

Announcements (PEM Olympiad)

PEM Olympiad

The PEM Olympiad is a written exam consisting of three questions. Students will be asked to provide complete solutions and answers to these problems within the allotted time. Students who answer one question perfectly get a bronze award, students who answer two questions perfectly get a silver award, and students who answer all questions perfectly get a gold award.

The PEM Olympiad will be held on February 2, 2012 (Saturday) from 1:00-4:00 PM at the following venues:

  • First Year – SEC A 202
  • Second Year – SEC A 203
  • Third Year – SEC A 209
  • Fourth Year – SEC A 214

Please note that these rooms are in the college area, NOT in the grade school. Awarding is on February 9, 2012 during the closing ceremony. In lieu of the PEM Olympiad, there will be no classes in the morning.

Handouts - Week 7

The handouts for the Week 7 PEM sessions can be downloaded via the links below.

Saturday, January 26, 2013

Some Chemistry Involved (Tuklas Vol. 14, No. 7 - Jan. 26, 2013)

SOME CHEMISTRY INVOLVED

The study of chemistry involves understanding the structures and symmetries of certain compounds at the molecular level. Being able to determine several properties of these structures can ultimately make the chemist's job easier in constructing different mixtures, or determining whether certain variations are possible. It turns out that a particular branch of mathematics called graph theory can provide many insights in these problems. Scientists like Vladimir Prelog, a Nobel Prize winner in Chemistry, are known for relating concepts in graph theory to applied chemistry.

We discuss a certain category of molecules called fullerenes. These are molecules composed of only carbon atoms in the shape of a hollow sphere, ellipsoid (a 3-d oblong shape) or tube. Their construction has been proven to be significant in research areas involving patents for material science, electronics, and nanotechnology. However, fullerenes are difficult to observe naturally. Thus, what we do instead is study their structure using theoretical tools (hint hint: graph theory) before performing experiments. To do so, we consider each bond between atoms as edges and the atoms themselves as vertices.

What we want to do at this point is determine a Hamiltonian path or cycle inside the graph we've just constructed. A Hamiltonian path is a set of edges that, taken in order, visits each vertex exactly once. A Hamiltonian cycle also visits each vertex exactly once with the added condition that the last edge should link back to the first vertex visited. The existence of Hamilton paths and cycles in fullerene graphs can be related to energy levels and chirality, which has something to do with the non-symmetry in molecules.

Leapfrog-fullerenes
Consider a graph \(F\). Let's call each region enclosed by a set of vertices with no vertex inside it a face. We now add a vertex inside each face and connect it to the vertices associated to the face we place it in. This process is called omnicapping, and results in a new graph which we call \(\text{Omni}(F)\).
Figure 1: The graphs \(F\) and \(\text{Omni}(F)\). 
We now switch the vertices and faces of \(\text{Omni}(F)\). That is, each vertex is now a face and vice versa. The resulting graph, called the dual of \(\text{Omni}(F)\), is what we call the leapfrog of \(F\), denoted by \(\text{Le}(F)\).
Figure 2: The graphs \(\text{Omni}(F)\) and \(\text{Le}(F)\). 
Constructing the Hamiltonian path or cycle
The goal is to create a Hamiltonian path in \(\text{Le}(F)\). Specifically, we want to choose \(\frac{\left(3n-4\right)}{4}\) vertices that will correspond to faces in \(\text{Le}(F)\). Let \(S\) be the set consisting of our chosen vertices, with \(S^{c}\) referring to the complement of \(S\) or the vertices we didn't choose. A series of construction procedures can be done to arrive at \(S\). For example, consider the planar projection of the molecule \(C_{20}\), which is a fancy way of calling the flattened representation of \(C_{20}\) on paper (the plane).

What should always be kept in mind during construction are the following properties:

  1. No vertices in \(S^{c}\) are adjacent, except for the starting edge;
  2. the distance from a vertex in \(S^{c}\) to another vertex in the same set should be at most 3;
  3. For every face of the graph there should be at least one vertex in \(S^{c}\); and
  4. For every face of the graph there should be at least two vertices in \(S\). These vertices need not be adjacent.

The figure below is the result of the correspondence between the vertices of \(C_{20}\) which are members of \(S\) and the faces of \(C_{60}\) which are shaded, the boundary of which is a cycle on 58 vertices. We connect the shaded region to 2 adjacent vertices to complete the Hamiltonian path in \(C_{60}\).
Figure 3: \(C_{20}\) and its leapfrog-fullerene \(C_{60}\) containing a Hamiltonian path.  
Below is the planar representation of \(C_{26}\) and its leapfrog-fullerene \(C_{78}\). This time around, the result is not just a Hamiltonian path, but a cycle.
Figure 4: \(C_{26}\) and its leapfrog-fullerene \(C_{78}\) containing a Hamiltonian cycle.

ABOUT THE AUTHOR:
Victor Andrew Antonio is a Lecturer at the Ateneo de Manila University. He obtained his B.S. in Mathematics at the Ateneo de Manila University in 2012 and is currently taking his M.S. in Mathematics at the same university.

REFERENCES:
[1] Grünbaum, B. and T. S. Motzkin. The number of hexagons and the simplicity of geodesics on certain polyhedra. Canad: J: Math: 1963, 15. 744-751.
[2] Johnson, C. Molecular Graph Theory. Master's Thesis. 2010. 1-23.
[3] Marušič, D. Hamilton Cycles and Paths in Fullerenes. J: Chem: Inf: Model: 2007, 47. 732-736.
[4] Rouvray, D.H. and D. Bonchev. Chemical Topology Introduction and Fundamentals. Gordon and Breach Science. Amsterdam. 1999.

OLYMPIAD CORNER
from the Czech and Slovak Republic National Contest, 2000

Problem: Show that \[ \sqrt[3]\frac{a}{b}+\sqrt[3]\frac{b}{a} \leq 2\sqrt[3](a+b)\left(\frac{1}{a}+\frac{1}{b}\right) \] for all positive real numbers \(a\) and \(b\), and determine when equality occurs.

Solution: 
Multiplying both sides of the desired inequality by \(\sqrt[3]{ab}\) gives the equivalent inequality \[ \sqrt[3]{a^2}+\sqrt[3]{b^2} \leq \sqrt[3]{2(a+b)^2}. \] Setting \(\sqrt[3]{a}=x\) and \(\sqrt[3]{b}=y\), we see that it suffices to prove that \[ x^2+y^2 \leq \sqrt[3]{2(x^3+y^3)^2} \qquad \ast \] for \(x,y>0\). By the AM-GM inequality, \[ 3x^4y^2 \leq x^6+x^3y^3+x^3y^3 \text{ and } 3x^2y^4 \leq y^6+x^3y^3+x^3y^3, \] with equality if and only if \(x^6=x^3y^3=y^6\), or equivalently if and only if \(x=y\). Adding these two inequalities and adding \(x^6+y^6\) to both sides yields \[ x^6+y^6+3x^2y^2(x^2+y^2) \leq 2(x^6+y^6+2x^3y^3). \] Taking the cube root of both sides yields \(\ast\), as desired. Equality occurs when \(x=y\), or equivalently when \(a=b\).

PROBLEMS
  1. Find all pairs \((x,y)\) of two positive integers such that \(N = 11x + 99y\) is a perfect square number less than or equal to \(1199\) and \(x+y\) is also a perfect square.
  2. Show that for all positive integers \(x, y, z\) \[ \left(\frac{x+y}{x+y+z}\right)^{\frac{1}{2}} + \left(\frac{x+z}{x+y+z}\right)^{\frac{1}{2}} +\left(\frac{y+z}{x+y+z}\right)^{\frac{1}{2}} \leq 6^{\frac{1}{2}}. \]
  3. For a fixed positive integer \(n\), find the minimum value of the sum \[ x_1 + \frac{{x_2}^2}{2} + \frac{{x_2}^3}{3} + \ldots + \frac{{x_2}^n}{n}, \]given that \(x_1, x_2, \ldots, x_n\) are positive numbers satisfying the property that the sum of their reciprocals is \(n\).
We welcome readers to submit solutions to the problems posed below for publication consideration. Solutions may be submitted to the PEM facilitators on the deadline date or online via mactolentino@math.admu.edu.ph. Solutions must be preceded by the solver's name, school affiliation and year level. The deadline for submission is 4:00 PM February 2, 2013

SOLUTIONS
(for January 19, 2013)
  1. Let \(n \geq 2\) be an integer and \(a_1, a_2, \ldots, a_n\) be real numbers. Prove that for any nonempty subset \(S \subset \{1, 2, \ldots, n\}\), the following inequality holds: \[ \left(\sum_{i \in S}a_i\right)^2 \leq \sum_{1 \leq i \leq j \leq n}(a_i + \ldots + a_j)^2. \] (Romanian Mathematical Olympiad, 2004)
    (Solved by Farrell Eldrian Wu [MGC New Life Christian Academy])

    SOLUTION: 
    Let \(S = \{i_1, i_1+1, \ldots, j_1, i_2, i_2+1, \ldots, j_2, \ldots, i_p, \ldots, j_p \}\) be the ordering of \(S\), where \(j_k < i_{k+1}\) for \(k = 1, 2, \ldots, p-1\). Take \(S_p = a_1 + a_2 + \ldots + a_p, S_0 = 0.\) Then \[ \sum_{i \in S}{a_i} = S_{j_p} - S_{i_p-1}+S_{j_{p-1}}-S_{i_{p-1}-1}+\ldots+S_{j_1}-S_{i_1-1} \]and \[ \sum_{1 \leq i \leq j \leq n}(a_i+\ldots+a_j)^2 = \sum_{0 \leq i \leq j \leq n}(S_i - S_j)^2. \]By this construction, it is enough to prove an inequality of the following form: \[(x_1 - x_2 + \ldots + (-1)^{p+1}x_p)^2 \leq \sum_{1 \leq i \leq j \leq p}(x_j - x_i)^2 + \sum_{i=1}^p{x_i^2}, \]in effect ignoring the same non-negative terms on the right-hand side. This now reduces to \[4\sum_{\substack{1 \leq i \leq j \leq n \\ j-i \text{ even}}}x_ix_j \leq (p-1)\sum_{i=1}^p{x_i^2}, \]obtained by adding together inequalities of the form \[ 4x_ix_j \leq 2(x_i^2 + x_j^2), i < j, j - i = \text{even}. \]For odd \(i\), \(x_i\) appears in an inequality of this form \(\left[\frac{p-1}{2}\right]\) times and for even \(i\) it appears \(\left[\frac{p}{2}-1\right]\) times, where \([x]\) refers to the integer part of \(x\).
  2. Show that among all boxes with a given surface area, the cube has the largest volume(Taken from The Cauchy-Schwartz Master Class by J. Michael Steele)
    (Solved by Clyde Wesley Ang [Chiang Kai Shek College], Jecel Manabat [Valenzuela City Sci HS], Hans Jarett Ong [Chiang Kai Shek College], Jan Kedrick Ong [Chiang Kai Shek College], Terence Tsai [Chiang Kai Shek College] and Farrell Eldrian Wu [MGC New Life Christian Academy])

    SOLUTION: 
    Let \(a\), \(b\) and \(c\) be the dimensions of the box, with surface area \(A = 2ab + 2ac + 2bc\). Note that if the box is a cube, then the edge length can be expressed in terms of \(A\) as \(\sqrt{\frac{A}{6}}\). Thus, what we wish to prove is that \[ abc \leq \left(\frac{A}{6}\right)^{\frac{3}{2}}. \]By the AM-GM inequality, we have \[ 2(a^2b^2c^2)^{\frac{1}{3}} = [(2ab)(2ac)(2bc)]^{\frac{1}{3}} \leq \frac{2ab+2ac+2bc}{3} = \frac{A}{3}, \]where equality holds if and only if \(ab = ac = bc\). But this equality holds if and only if \(a = b = c\) and we are done.
  3. Three circles with the same radius pass through a common point. Let \(S\) be the set of points which are interior to at least two of the circles. How should the three circles be placed so that the area of \(S\) is minimized? (French Mathematical Olympiad, 1995)
    (Solved by Clyde Wesley Ang [Chiang Kai Shek College], Hans Jarett Ong [Chiang Kai Shek College], Jan Kedrick Ong [Chiang Kai Shek College] and Farrell Eldrian Wu [MGC New Life Christian Academy])

    SOLUTION: 
    Suppose the circles have unit radius. Let \(P\) be the common point of the circles and let \(A\), \(B\), \(C\) be the second intersection points of each pair of circles. We wish to minimize the common area between any two pairs of circles, which will happen when \(P\) is an interior point of \(\Delta ABC\).
    Should this be the case, the area of \(S\) is equal to \(\pi - (\sin \alpha + \sin \beta + \sin \gamma)\), where \(\alpha\), \(\beta\) and \(\gamma\) are the central angles of the common arcs of the circles. Note that \(\alpha + \beta + \gamma - 180^\circ\). Since \(\sin x\) is a concave function the area is minimized when \(\alpha = \beta = \gamma = 60^\circ\), which implies that the centers of the circles form an equilateral triangle.
  4. A line that contains the centroid \(G\) of the triangle \(ABC\) intersects the side \(AB\) at \(P\) and the side \(CA\) at \(Q\). Prove that \[ \frac{PB}{PA}\cdot\frac{QC}{QA} \leq \frac{1}{4}. \](Spanish Mathematical Olympiad, 1998)
    (Solved by Farrell Eldrian Wu [MGC New Life Christian Academy]; partial credit for Clyde Wesley Ang [Chiang Kai Shek College], Hans Jarett Ong [Chiang Kai Shek College] and Jan Kedrick Ong [Chiang Kai Shek College])

    SOLUTION: 
    Note that by the inequality \[ \frac{PB}{PA}\cdot\frac{QC}{QA} \leq \frac{1}{4}\left(\frac{PB}{PA}+\frac{QC}{QA}\right)^2 \]all we have to do is show that \(\frac{PB}{PA}+\frac{QC}{QA} = 1\).
    We draw \(BB'\) and \(CC'\) such that they are both parallel to the median \(AA'\) and \(B'\) and \(C'\) are on the line containing \(PQ\). Then \(\Delta APG\) is similar to \(\Delta BPB'\) and \(\Delta AQG\) is similar to \(\Delta CQC'\), implying that \(\frac{PB}{PA} = \frac{BB'}{AG}\) and \(\frac{QC}{QA} = \frac{CC'}{AG}\). Furthermore, \(AG = 2GA' = BB' + CC'\), and the conclusion follows.

ERRATA
Clyde Wesley Ang was not properly credited for answering Problem #14 and having a partial solution to Problem #15.

Monday, January 21, 2013

Announcements (for Week 6 Handouts and Tuklás)


Solvers for Problems #14 and #15 from Tuklás Matemátika Vol. 14, No. 5 have been properly credited.

Handouts for the Week 5 sessions have been uploaded. They may be accessed by the list of links found on the right side of the Tuklás Matemátika website.

Handouts - Week 6


The handouts for the Week 6 PEM sessions can be downloaded via the links below.



Saturday, January 19, 2013

Counting Infinity (Tuklas Vol. 14, No. 6 - Jan. 19, 2013)

COUNTING INFINITY

Counting is a very basic skill. It's usually a person's first encounter with mathematics. In fact, some people believe that this is the extent to which math is relevant to their lives. However, it turns out that something as simple as counting can behave very strangely under certain circumstances.

Let's start with the set of natural numbers \(\mathbb{N} = \{1, 2, 3, \ldots\}\). These are the very first numbers taught to us, and we usually learn them within the context of counting. If we want to bring the math into it, the idea of counting can be linked to the cardinality of a set. Remember, cardinality is the number of elements that are in the set. We can use cardinality as a way of determining whether one set is larger than the other. Of course, this would only make sense as long as the sets were finite. What happens with infinite sets? Which is larger, \(\mathbb{N}\) or the set of integers \(\mathbb{Z}\)? What about the set of rational numbers \(\mathbb{Q}\) and the set of all real numbers \(\mathbb{R}\)?

We'll try to answer these questions. \(\mathbb{N}\) has no negative numbers, so it seems that \(\mathbb{Z}\) is "larger". Of course, if we expand to fractions, \(\mathbb{Q}\) will be "bigger". If we include irrational numbers, \(\mathbb{R}\) is the "largest". But then again, all of these sets have an infinite number of elements, so by our current idea of cardinality no one is larger or smaller than the other. Our previous construction thus breaks down. Sadly, it seems our intuition fails us here. 

Let's try to stretch the idea of counting to accomodate this notion of infinity. We now introduce the idea of a countable set. Formally, a set is said to be countable if it shares a one-to-one correspondence with some subset of the set of natural numbers. For example, the set \(\{a,b,c\}\) can be matched to the set \(\{1,2,3\}\) which is a subset of \(\mathbb{N}\). In fact, the easiest matching here corresponds to the idea of counting (in a finite sense). However, the idea of countability also allows us to get an idea of how to determine the cardinalities of infinite sets. Simply put, if a set is countable, then it has the same cardinality as the set of natural numbers.

What we need to do then is establish a mapping from the set we are "counting" to \(\mathbb{N}\) . Here's where strange things start to happen. It turns out that \(\mathbb{Z}\)  and \(\mathbb{Q}\)  are countable. However, the unit interval (0,1) is not. Neither is \(\mathbb{R}\). This amazing result was discovered by Georg Cantor in 1891 using a proof by contradiction and a technique now called Cantor's diagonalization argument.

We'll deviate from Cantor's full proof and prove a smaller case that we can generalize later. Let's show that the unit interval is uncountable by first supposing that it is countable then arriving at a contradiction. Note that we can represent all the elements of the unit interval by the sequence of numbers \[ \begin{align*} x_1 &= 0.d_{11}d_{12}d_{13}\ldots \\ x_2 &= 0.d_{21}d_{22}d_{23}\ldots \\ x_3 &= 0.d_{31}d_{32}d_{33}\ldots \\ \vdots \end{align*} \] where \(d_{ij}\) is a number from 0 to 9. Our mapping from \(\mathbb{N}\) to this set would simply be the matching where \(1 \rightarrow x_1, 2 \rightarrow x_2\) and so on.

We now construct a new number \(y = 0.y_1y_2y_3\ldots\) with the condition that \(y_i \neq d_{ii}, 0, 9\). In effect, each decimal place has a different value from its corresponding pair in the "diagonal" formed by the sequence. The restriction for 0 and 9 means that we want to prevent getting numbers such as \(0.000\ldots = 0\), \(0.999\ldots = 1\) or \(0.4999\ldots = 5\).

Note that \(y\) is inside the interval (0,1), but by the way it was made it's not equal to any of the numbers in our created sequence. Even if we include this number, we can always find a new number that is not inside the sequence because the included number introduces a new diagonal element. Hence, we have a contradiction.

Next, let's show that the unit interval and the set of real numbers have the same cardinality. Consider the unit interval as a line segment placed 1/2 units above the real number line such that 1/2 on the unit interval is directly above 0 on the real number line. If we place a point in the middle of the unit interval, we can trace a semicircle underneath the unit interval. 

Note that we can draw a line segment from any number on the real number line towards the center of the semicircle we made (see below). Each segment intersects the semicircle at exactly one point. Furthermore, each point of intersection is directly below a number in the unit interval. We now have a matching between the numbers in (0,1) and the set of all real numbers, hence they share the same cardinality.

Confused? Don't worry. When Cantor first published his results, many mathematicians were shocked (some outraged) and campaigned against him and his ideas. His results were so counter-intuitive that some of his colleagues flat out rejected them. However, it cannot be denied that his ideas had merit, and in the end they were accepted by the mathematics community. Thanks to Cantor, we can see for ourselves how something as boring as counting can have mind-bending properties.

ABOUT THE AUTHOR:
Jesus Lemuel Martin, Jr. obtained his B.S. in Applied Mathematics major in Computational Science at the Ateneo de Manila University in 2010 and is currently taking his MS in Mathematics at the same university.

OLYMPIAD CORNER
from the Asian Pacific Mathematics Olympiad, 2012

Problem: Let \(P\) be a point in the interior of a triangle \(ABC\), and let \(D, E, F\) be the point of intersection of the line \(AP\) and the side \(BC\) of the triangle, of the line \(BP\) and the side \(CA\), and of the line \(CP\) and the side \(AB\), respectively. Prove that the area of the triangle \(ABC\) must be 6 if the area of each of the triangles \(PFA, PDB\) and \(PEC\) is 1.

Solution: 
Let \([XYZ]\) denote the area of triangle \(XYZ\). Let \(x=[PAB], y = [PBC]\) and \(z=[PCA]\).

Note that \[ \frac{BF}{AF} = \frac{[BPF]}{[APF]}=\frac{[BCF]}{[ACF]}=\frac{[BPF]-[BCF]}{[APF]-[ACF]}=\frac{[PBC]}{[APC]}=\frac{y}{z} \] hence \(y:z=\left(x-1\right):1\), which implies \(\left(z+1\right) x=x+y+z\). Similarly, we get \(\left( x+1\right) y=x+y+z\) and \(\left( y+1\right) z=x+y+z\). Thus, we obtain \[ \left( x+1\right) y=\left( y+1\right) z=\left( z+1\right) x. \]Assume, without loss of generality that \(x\leq y\) and \(x\leq z\). If \(y>z\), then \(\left( y+1\right) z>\left( z+1\right) x\), which is a contradiction. Likewise, if \(y<z\), then we have another contradiction as \((x+1)y<(y+1)z\). Therefore, \(y=z\). And as a result, the equality \(\left(y+1\right)z=\left(z+1\right)x\) would yield \(x=z\).

We now obtain from \(\left( x-1\right) :1=y:z=1:1\) that \(x=y=z=2\). Therefore, we can conclude that the area of the triangle \(ABC\) equals \(x+y+z=6\).

PROBLEMS
  1. Show that among all boxes with a given surface area, the cube has the largest volume.
  2. Three circles with the same radius pass through a common point. Let \(S\) be the set of points which are interior to at least two of the circles. How should the three circles be placed so that the area of \(S\) is minimized?
  3. A line that contains the centroid \(G\) of the triangle \(ABC\) intersects the side \(AB\) at \(P\) and the side \(CA\) at \(Q\). Prove that \[ \frac{PB}{PA}\cdot\frac{QC}{QA} \leq \frac{1}{4}. \]
We welcome readers to submit solutions to the problems posed below for publication consideration. Solutions may be submitted to the PEM facilitators on the deadline date or online via mactolentino@math.admu.edu.ph. Solutions must be preceded by the solver's name, school affiliation and year level. The deadline for submission is 12:00 PM January 26, 2013

SOLUTIONS
(for January 12, 2012)
  1. There are \(n\) straight lines in a plane, such that every two intersect with each other. Prove that among the angles formed there is at least one angle which is not greater than \(\frac{180^\circ}{n}\). (Romanian Mathematical Olympiad, 2004)
    (Solved by Clyde Wesley Ang [Chang Kai Shek College], Terence Tsai [Chang Kai Shek College] and Farrell Wu [MGC New Life Christian Academy])

    SOLUTION: 
    From the \(n\) lines we can form \(4\binom{n}{2} = 2n(n-1)\) angles. By translation to a fixed point \(O\) on the plane, the \(2n(n-1)\) angles form \(2n\) angles. If all of the angles formed are greater than \(\frac{180^\circ}{n}\) then the sum is greater than \(2n\cdot\frac{180^\circ}{n} = 360^\circ\) which is impossible, and we are done.
  2. In the figure above (omitted), \(ABCDEF\) is a regular hexagon. The midpoint of \(\overline{AB}\) is \(W\) and \(X\) and \(Y\) are intercepts as shown. What is the value of \(\frac{[XYDE]}{[WXF]}\)? (Australian Mathematics Competition, 1995)
    (Solved by Farrell Wu [MGC New Life Christian Academy], partial credit for Clyde Wesley Ang [Chang Kai Shek College] and Terence Tsai [Chang Kai Shek College])

    SOLUTION: 
    Note that the interior angle of a regular hexagon is \(120^\circ\). Let \(a\) be the length of any side of \(ABCDEF\). We solve for the length \(\overline{AE}\) from \(\Delta AEF\) by applying the Cosine Law to get \[ \overline{AE} = \sqrt{a^2 + a^2 - 2a^2\cos \theta} = \sqrt{3}a. \] The heights of \(WXF\) and \(XYDE\) are thus \(\sqrt{3}a/2\). We now solve for the lengths \(\overline{XY}\) and \(\overline{FX}\). Via similar triangles, \(\overline{XY} = a/2\) hence \[ [XYDE] = \frac{3\sqrt{3}a^2}{8}. \] If we let \(M\) be the intersection of \(\overline{AE}\) and \(\overline{CF}\), \(\overline{FM} = a/2\). Furthermore, since \(\overline{AE}\) is perpendicular to \(\overline{CF}\), \(\overline{MX} = a/2 - \overline{XY}/2\). Hence,  \[ [WXF] = \frac{3\sqrt{3}}{16}a^2 \Leftrightarrow \frac{[XYDE]}{[WXF]} = 2. \]

Tuesday, January 15, 2013

Announcements (Handouts and Tuklás)


Solvers for Problem #11 from Tuklás Matemátika Vol. 14, No. 4 have been properly credited. Problem #13 in Tuklás Matemátika Vol. 14, No. 5 was ambiguous and has been replaced; the deadline for the new problem has been extended until January 26, 2013.

Handouts for the Week 5 sessions have been uploaded. In addition, the handout for Week 2 of the Advanced Class has also been uploaded in the Week 4 handout page. These pages may be accessed by the list of links found on the right side of the Tuklás Matemátika website.

Handouts - Week 5


The handouts for the Week 5 PEM sessions can be downloaded via the links below.




Saturday, January 12, 2013

A Divine Proportion (Tuklas Vol. 14, No. 5 - Jan. 12, 2013)

A DIVINE PROPORTION

Consider a string of finite length. Let us divide it into two parts. We do our division such that the ratio of the longer and shorter parts is equal to the ratio of the whole length and the longer part. It turns out that no matter how long the string is, the common value is a fixed positive number. Throughout history it has been called by many names such as the divine proportion, golden ratio, golden section, medial section and extreme and mean ratio. As a symbol, we denote it by $\varphi$(phi), the first letter in the name of the Greek sculptor Phidias.

We now use our string analogy to try and see what this number looks like. Two numbers \(a\) and \(b\), with \(a>b\), are said to be in the golden ratio if \(\frac{a+b}{a} = \frac{a}{b} = \varphi\). By rewriting the left-most quantity into \(1+\frac{b}{a}\), we get the equation \(\varphi = 1 + \frac{1}{\varphi}\). After some algebraic manipulations, we arrive at \[ \varphi ^2 - \varphi - 1 =0. \] Using the quadratic formula, we have \(\frac{1+\sqrt{5}}{2}\) and \(\frac{1-\sqrt{5}}{2}\) as solutions to the equation. Since \(\frac{1-\sqrt{5}}{2} < 0 < \frac{1+\sqrt{5}}{2}\), then \(\varphi = \frac{1+\sqrt{5}}{2}\). Using ten decimal places, the value of \(\varphi\) is approximately equal 1.6180339887. We can also write \(\varphi\) in terms of a continued fraction. We start with \(\varphi = 1 + \frac{1}{\varphi}\). By replacing \(\varphi\) with \(1 + \frac{1}{\varphi}\), we get \(\varphi = 1 + \frac{1}{1 + \frac{1}{\varphi}}\). Repeat the process infinitely many times and we get the equation shown below [1].
Let's move on to two dimensional objects. A golden rectangle is a rectangle whose side lengths are in the golden ratio. We can construct one such rectangle by starting with a right triangle with a base of half a unit and a height of one unit. From the Pythagorean theorem, the length of the hypotenuse is \(\frac{\sqrt{5}}{2}\) units. Rotate the hypotenuse in such a way that it extends the base of the triangle. Then we complete the rectangle. The golden rectangle that we have constructed has dimensions 1 unit by \(\varphi\) units. If we adjoin a square whose side is of length \(\varphi\) units, the resulting rectangle formed is also a golden rectangle. In fact, if we start with an arbitrary golden rectangle and adjoin a square whose side is of the same length as the longer side of the rectangle then we create another golden rectangle.
Remember Phidias, the guy from whom the symbol for the golden ratio originated? It is said that he incorporated golden rectangles into the design of Parthenon. The length and height of the building, the spacing between the columns and the pitch of the roof are all controlled by the golden section. Architects and artists believed that structures and paintings whose design is governed by the medial section are more pleasing to the eye.
Figure 1: The Greek Parthenon, and the superimposed golden rectangle. [2]
We can also observe the extreme and mean ratio in the natural sciences. For example, a biologist sees it in the structure of a human face and in the lengths of a finger's phalanges. A botanist sees it the pattern of seeds in a sunflower and in the positioning of leaves in a plant. A zoologist sees it in the population growth of rabbits. There are still a lot more examples that naturally follow the divine proportion. It is as if there is a divine power that guides all things to be created in such a beautiful manner. Truly, \(\varphi\) is such a divine number.

ABOUT THE AUTHOR:
Janree Ruark Gatpatan obtained his B.S. in Applied Mathematics at the University of the Philippines - Visayas in 2008 and is currently taking his Ph. D. in Mathematics at the Ateneo de Manila University.

OLYMPIAD CORNER
from the Putnam Competition, 2002

Problem: Let \(n\geq 2\) be an integer and \(T_n\) be the number of non-empty subsets \(S\) of \(\{1,2,3,...,n\}\) with the property that the average of the elements of \(S\) is an integer. Prove that \(T_n-n\) is always even.

Solution: 
We first note that each of the singletons \(\{1\},\{2\},...,\{n\}\) has the necessary property, for a total of \(n\) sets. 

Now suppose \(S\) is a set of more than one element with an integer average \(m\). Then \(S\) either contains \(m\) or does not contain \(m\). If \(S\) does not contain \(m\), then the set \(S\cup \{m\}\)  has an average \(m\). If \(S\) contains \(m\), then the set \(S\setminus \{m\}\) also has an average \(m\). This means that there is a one to one correspondence between sets that contain \(m\), and sets that don't contain \(m\). 

Therefore sets with the desired property other than \(\{1\},\{2\},...,\{n\}\) can be grouped into pairs, and hence \(T_n-n\) is always even.

PROBLEMS
  1. (The previous question was scrapped due to its ambiguity; submissions to this new question will be accepted until January 26, 2013.)
    Let \(n \geq 2\) be an integer and \(a_1, a_2, \ldots, a_n\) be real numbers. Prove that for any nonempty subset \(S \subset \{1, 2, \ldots, n\}\), the following inequality holds: \[ \left(\sum_{i \in S}a_i\right)^2 \leq \sum_{1 \leq i \leq j \leq n}(a_i + \ldots + a_j)^2. \]
  2. There are \(n\) straight lines in a plane, such that every two intersect with each other. Prove that among the angles formed there is at least one angle which is not greater than \(\frac{180^\circ}{n}\).
  3. In the figure above, \(ABCDEF\) is a regular hexagon. The midpoint of \(\overline{AB}\) is \(W\) and \(X\) and \(Y\) are intercepts as shown. What is the value of \(\frac{[XYDE]}{[WXF]}\)?
We welcome readers to submit solutions to the problems posed below for publication consideration. Solutions may be submitted to the PEM facilitators on the deadline date or online via mactolentino@math.admu.edu.ph. Solutions must be preceded by the solver's name, school affiliation and year level. The deadline for submission is 12:00 PM January 19, 2013

SOLUTIONS
(for December 8, 2012)
  1. Sherlock and Mycroft play a game which involves flipping a single fair coin. The coin is flipped repeatedly until one person wins. Sherlock wins if the sequence TTT (tails-tails-tails) shows up first while Mycroft wins if the sequence HTT (heads-tails-tails) shows up first. Who among the two has a higher probability of winning? (13th Philippine Mathematical Olympiad, Area Stage)
    (Solved by Clyde Wesley Ang [Chiang Kai Shek College], Kimberly Co [St. Stephen's], Jecel Manabat [Valenzuela City Sci HS], Terence Tsai [Chiang Kai Shek College], Hans Jarett Ong [Chiang Kai Shek College], Jan Kendrick Ong [Chiang Kai Shek College] and Farrell Eldrian Wu [MGC New Life Christian Academy])

    SOLUTION: 
    Sherlock wins if the sequence TTT comes up first. This sequence has probability \(P(\left\{TTT\right\})=\frac{1}{8}\). Mycroft wins as long as the sequence HTT comes up, which has probability \(P(\left\{HTT, THTT, TTHTT, \ldots \right\})>\frac{1}{8}\). Therefore Mycroft has a higher probability of winning.
  2. In \(\Delta ABC\), \(D\) is the midpoint of \(AB\), \(E\) and \(F\) are on \(AC\) and \(BC\) respectively. Prove that the area of \(\Delta DEF\) is not greater than the sum of the areas of \(\Delta ADE\) and \(\Delta BDF\). (All-Russia Olympics Mathematical Competitions, 1983)
    (Solved by Clyde Wesley Ang [Chiang Kai Shek College], Hans Jarett Ong [Chiang Kai Shek College], Jan Kendrick Ong [Chiang Kai Shek College]; partial credit for Farrell Eldrian Wu [MGC New Life Christian Academy])

    SOLUTION: 
    We denote the area enclosed by the convex polygon by \([\cdot]\). Extend \(\overline{ED}\) to \(E_1\) such that \(\overline{E_1D} = \overline{ED}\). Connecting \(E_1\) to \(B\) and \(F\), we note that \(\Delta ADE \cong \Delta DE_1B\) by SAS and \([DE_1F] = [EDF]\) since they have equal height. Thus \[[ADE]+[DBF]=[DE_1B]+[DBF]=[DE_1BF]>[DE_1F]=[DEF]. \]
  3. Let \(n \geq 3\) be an odd number. Show that there is a number in the set \[ \{ 2^1 - 1, 2^2 - 1, \ldots, 2^{n-1} - 1 \} \]which is divisible by \(n\). (USSR MO, 1980)
    (Solved by Farrell Eldrian Wu [MGC New Life Christian Academy])

    SOLUTION: 
    Let \(S = \left\{2^1-1, 2^2-1, \ldots, 2^{n-1}-1\right\}\) and \(R = \left\{1, 2^1, 2^2, \ldots, 2^{n-1}\right\}\). Then \(|R| = n\) where none of its elements are divisible by \(n\) since \(n \geq 3\) is an odd positive integer. This implies that none of the elements of \(S\) are divisible by \(n-1\), since \[ \begin{align*} 2^i-1 &\equiv (n-1) \pmod{n} \\ 2^i &\equiv 0 \pmod{n}, \end{align*} \] which we know is false. Hence by the Pigeonhole Principle there are \(\left\lceil\frac{|S|}{|R|}\right\rceil = 2\) numbers in \(S\) that have the same remainder when divided by \(n\), say \(2^i - 1\) and \(2^j - 1\) for some \(1 \leq i < j \leq n-2\). We now have \[ \begin{align*} 2^j - 1 &\equiv 2^i - 1 \pmod{n} \\ 2^j - 2^i &\equiv 0 \pmod{n} \\ 2^i(2^{j-i} - 1) &\equiv 0 \pmod{n}, \end{align*} \] and since \(n \nmid 2^i\), \(n \mid 2^{j-i} - 1\), and we are done.
ERRATA
There were several typographical errors in the article "Winning the Ultimatum Game"
  - par. 2, "\pi" was written as "pi"
  - par. 3, "...leave the money where you found..." was written as "...leave the money here you found...".)
There was a typographical error in Problem #8 that read \(2^n-1, 2^2-1, \ldots, 2^{n-1}-1\), which has been corrected to read  \(2^1-1, 2^2-1, \ldots, 2^{n-1}-1\) .
Jazzrine Tagle [Valenzuela City High School] was not credited for answering problem 8.

Wednesday, January 9, 2013

Handouts - Week 4


The handouts for the Week 4 PEM sessions can be downloaded via the links below. Handouts for the First and Second Year classes were composed of previously released problems.