Where is my umbrella? (Tuklas Vol. 16, No. 5 - December 6, 2014)

WHERE IS MY UMBRELLA?

Everyday life is full of random phenomena, be it rolling dice, winning or losing pusoy dos, or even just the chance of rain on a cloudy day. In this article, we will talk about an object that behaves randomly in a rather odd way: its future behavior only depends on the past through present. We call this object a Markov process. Simply put, we can think of a Markov process as a memoryless process: what will happen in the future does not depend on the past. That is, the future event is dependent only on the current event. For instance, if $A_1, A_2, A_3, \ldots, A_{10}$ are events of a Markov process, then the probability that the next event $A_{11}$ happens will depend only on $A_{10}$. The rest, they say (quite appropriately), is history.

Let us talk about the weather. We give an example that always bothers students on a weekday morning. Suppose that in a certain city, there is a 60% chance that when it is sunny today it will also be sunny tomorrow. When it is rainy today, there is an 85% chance that it will also be rainy tomorrow. Of course, we are making simplistic assumptions here to illustrate the case of Markov processes. However, we can also use this example as an excuse when we are too sleepy to get out of bed on a weekday morning!

We can make a nice diagram called a chain, which can look like something below. The terms sunny and rainy are called states. Arrows represent the transition from one state to another with the corresponding probability values. From the problem, when it is rainy today, there is 0.85 chance that it will also be rainy tomorrow. This also means that there is a 0.15 chance of the weather being sunny tomorrow. Also, when it is sunny today, there is 0.6 chance of sun and 0.4 chance of rain tomorrow.

Diagrams like chains are useful in summarizing given data. Of course, mathematicians would prefer a more compact and powerful tool where calculations can be made, so they make use of matrices to describe the problem. A standard matrix representation of the problem would look something like the one below: $$P = \begin{bmatrix} & \text{sunny} & \text{rainy} \\ \text{sunny} & 0.6 & 0.4 \\ \text{rainy} & 0.15 & 0.85 \end{bmatrix}$$ The matrix $P$ is called a transition probability matrix or simply a transition matrix. Notice that the rows add up to 1. We can also write rainy instead of sunny first and the mathematics will not change. I prefer the order above.

So let us say that it is sunny today. What is the probability that it will be sunny tomorrow? What is the probability it will be sunny two days from now?

For a simple Markov process like this, the transition matrix two time steps from now is given by the product of the matrix $P$ with itself, or $P^2$. We have  $$P^2 = \begin{bmatrix} & \text{sunny} & \text{rainy} \\ \text{sunny} & 0.42 & 0.58 \\ \text{rainy} & 0.2175 & 0.7825 \end{bmatrix}.$$ This means that two days from now, there is a 42% chance of being sunny if it is sunny today, and a 78.25% chance of the weather being rainy if rains today. To get the weather $n$ days from now, you can compute $P^n$. 

After some diligence and hard work, something interesting happens to $P^n$: $$P^3 = \begin{bmatrix} & \text{sunny} & \text{rainy} \\ \text{sunny} & 0.3390 & 0.6610 \\ \text{rainy} & 0.2479 & 0.7521 \end{bmatrix}$$ $$P^{10} = \begin{bmatrix} & \text{sunny} & \text{rainy} \\ \text{sunny} & 0.2730 &  0.7270 \\ \text{rainy} & 0.2726 & 0.7274 \end{bmatrix}$$ $$P^{20} = \begin{bmatrix} & \text{sunny} & \text{rainy} \\ \text{sunny} & 0.2727 & 0.7273 \\ \text{rainy} & 0.2727 & 0.7273 \end{bmatrix}$$ $$P^{50} = \begin{bmatrix} & \text{sunny} & \text{rainy} \\ \text{sunny} & 0.2727 & 0.7273 \\ \text{rainy} & 0.2727 & 0.7273 \end{bmatrix}$$ Any guesses on the probability of rain or shine 70 days from now? 

Notice that as the powers go larger and larger, the probabilities do not change anymore. The probability of sunshine 20, 40, 50, and even 100 days from now is about 27% whether or not it is rainy or sunny right now. This Markov process is said to have a limiting distribution or a steady state distribution.

It is important to note that Markov processes have intricate subtleties that are prone to misinterpretation. Our example above involves some simplifications. A more rigorous treatment of Markov processes can be found in college probability textbooks.

ABOUT THE AUTHOR:
Clark Kendrick Go is an Instructor at the Ateneo de Manila University. He is currently taking his graduate studies in the Nara Institute of Science and Technology in Ikoma, Japan.

OLYMPIAD CORNER

from the Colombian Mathematical Olympiad, 1997

Problem: We are given an $m\times n$ grid and three colors. We wish to color each segment of the grid with one of the three colors so that each unit square has two sides of one color and two sides of a second color. How many such colorings are possible?

Solution: 

Suppose the three colors are blue, red and green. Let $a_{n}$ be the number of such colorings of a horizontal $1\times n$ board given the colors of the top grid segments. For $n=1$, assume WLOG the top segment grid is given and is colored blue. That means there are three ways to choose the other segment that will be colored with colored blue, and then two ways to choose the colors of the remaining two segments. This gives us a total of 6 colorings, and hence $a_{1} = 6$.

We now find $a_{n+1}$ in terms of $a_{n}$. Given any coloring of the $1\times n$ board, assume WLOG that its rightmost segment is colored blue. We now add a unit square to the right side of the board to make a $1\times \left(n+1\right)$ board, where the top color of the new square is known.

1. If the new top segment is colored blue, then there are two ways to choose the colors of the remaining two segments.
2. If the new top segment is not blue, then there are also two ways to choose which of the remaining segments is colored.

In other words, given the color of the top segment for the $\left(n+1\right)$-th square, there will always be two ways to color the remaining. This means that $a_{n+1}=2a_{n}$, and so $a_{n}=3\cdot 2^{n}$.

Going back to the given problem, note that there are $3^{n}$ ways to color the top edges, and $3\cdot 2^{n}$ ways to color each successive row. Hence the total number of colorings is $$3^{n}\cdot \left( 3\cdot 2^{n}\right) ^{m}=3^{m+n}\cdot 2^{mn}.$$

SOLUTIONS

(for November 22, 2014)

10. Show that if $2^{n}-1$ is prime, then $n$ must be prime. (Converse of Mersenne Prime Conjecture)
    (partial credit for Farrell Eldrian Wu [MGC New Life Academy])
    
    
    SOLUTION: 
    Suppose $n$ is not prime. Then $n = ab$, where $a, b > 1$. So we have $$\begin{align*} 2^{n}-1 & = 2^{ab}-1 \\ & = \left(2^{a}\right)^{b}-1 \\ & = \left(2^{a}-1\right)\left(\left(2^{a}\right)^{b} + \left(2^{a}\right)^{b-1} + \cdots + 2^{a}+1\right). \end{align*}$$ By our definition of $n$, we can see that $2^{a}-1>1$, and also, $\left(\left(2^{a}\right)^{b} + \left(2^{a}\right)^{b-1} + \cdots + 2^{a}+1\right) > 1$. This means that $2^{n}-1$ has proper divisors, which means it is not prime, which is a contradiction.


11. Given a positive integer $n$, let $p\left(n\right)$ be the product of the nonzero digits of $n$. Determine the value of $p\left(1\right) + p\left(2\right) + \cdots + p\left(999\right) + p\left(1000\right)$. (AIME 1994)
    (partial credit for Farrell Eldrian Wu [MGC New Life Academy])
    
    
    SOLUTION: 
    Define a function $m$ such that $m\left(0\right)=1$ and $m\left(x\right)=x$, for $x\neq0$. Note that if $x=a_{n}10^{n}+a_{n-1}10^{n-1}+\cdots+a_{0}$, then $$p\left(x\right)=m\left(a_{n}\right)m\left(a_{n-1}\right)\cdots\left(m_{1}\right)\left(m_{0}\right).$$ Specifically, since we are looking at $3$-digit numbers, $$p\left(100h+10t+u\right)=m\left(h\right)m\left(t\right)m\left(u\right).$$ This means that $$\begin{align*} p\left(0\right)+p\left(1\right)+p\left(2\right)+\cdots+p\left(999\right) & = m\left(0\right)m\left(0\right)m\left(0\right)+m\left(0\right)m\left(0\right)m\left(1\right) + \\ &\quad \cdots+ m\left(9\right)m\left(9\right)m\left(8\right)+m\left(9\right)m\left(9\right)m\left(9\right)\\ & = \left(m\left(0\right)+m\left(1\right)+\cdots+m\left(8\right)+m\left(9\right)\right)^{3}\\ & = \left(1+1+2+\cdots+8+9\right)^{3}\\ & = 46^{3}. \end{align*}$$ So, $$\left[p\left(1\right)+p\left(2\right)+\cdots+p\left(999\right)\right]+p\left(1000\right) = \left[46^{3}-1\right]+1\\ = 97336.$$
12. In $\triangle ABC$, $D$, $E$ are on $BC$ and $CA$ respectively, and $BD:DC=3:2$, $AE:EC=3:4$. $AD$ and $BE$ intersect at $M$. Given that the area of $\triangle ABC$ is $1$, find the area of $\triangle BMD$.
    (solved by Farrell Eldrian Wu [MGC New Life Academy])
    
    
    SOLUTION: 
    Define $N$ on $BC$ such that $EN$ is parallel to $AD$. The complete figure is shown below.
    

    
    

    

    
    By Triangle Similarity, $$\frac{DN}{NC}=\frac{AE}{EC}=\frac{3}{4}.$$ Because of this, $$\begin{align*} \left[ABE\right] & = \frac{3}{7}\left[ABC\right]\\ & = \frac{3}{7}. \end{align*}$$ Consequently, $$\left[BEC\right]=\frac{4}{7}.$$
    Note that $$\frac{BD}{DN} = \frac{7}{2}, \quad \frac{DN}{NC} = \frac{3}{4}.$$ so $BD:DN:NC=21:6:8$. This means $$\frac{BN}{NC} = \frac{27}{8}, \quad \frac{BD}{BN} = \frac{7}{9}.$$ Moreover, $$\frac{BN}{BC} = \frac{27}{35}$$ and $$\begin{align*} \left[BEN\right] & = \frac{27}{35}\left[BEC\right]\\ & = \frac{27}{35}\cdot\frac{4}{7}. \end{align*}$$ Finally, by Triangle Similarity, $$\begin{align*} \frac{\left[BMD\right]}{\left[BEN\right]} & = \left(\frac{7}{9}\right)^{2} \\ \left[BMD\right] & = \frac{7^{2}}{9^{2}}\left(\frac{27}{35}\cdot\frac{4}{7}\right)\\ & = \frac{4}{15}. \end{align*}$$

Change of schedule for PEM 2014

Please take note of the following changes in the schedule for PEM:

November 29 (unchanged):

CLASS	VENUE
Teachers	SEC-A304
Provincial (1st-2nd)	CTC102
Provincial (3rd-4th)	F-AVR

December 6 (originally scheduled on November 29):

CLASS	VENUE
Grade 7	SEC-A203
Grade 8	SEC-A205
Grade 9	Escaler Hall
Grade 10 (A)	SEC-A303
Grade 10 (B)	SEC-A304

December 13 (originally scheduled on December 6):

EVENT	VENUE
PEM Olympiad	Escaler Hall
PEM Closing Session	Leong Hall Auditorium

Please be guided accordingly.

Origami Math (Tuklas Vol. 16, No. 4 - November 22, 2014)

ORIGAMI MATH

Origami and Paper Folding
Origami is the traditional Japanese art of paper folding. It involves transforming a piece of paper using only folds and creases. There are no cutting and gluing in strict origami. It is amazing how different geometric shapes and three-dimensional figures can be made just by folding papers. One can discover lines, polygons and lines inside an origami model.

But did you know that, aside from geometry, algebra is also present in paper folding? Without the goal of forming a three-dimensional model, simple paper folding can help one solve various equations.

Let us look at how paper folding can be used to form various geometric concepts. We will also construct two origami models and discover the beautiful pattern inside our models. Finally, we show how simple paper folding is used to solve a cubic equation (a polynomial of degree 3).

Basic Geometric Shapes Using Origami
Geometric concepts are clearly present in origami and simple paper folding. Everyone knows how to fold a piece of paper in half or even in quarters just by simply folding a folded paper in half. For that matter, one can fold in any powers of 2: $\dfrac{1}{8}$, $\dfrac{1}{16}$, etc. But do you know how to fold a paper in exactly 3 parts? Moreover, you may easily divide an angle into 2 equal parts by simple paper folding, but can you trisect an angle (divide the angle into 3 equal parts)?

(Folding a paper in thirds using a square)

1.

2.

3.

4.

5.

6.

7.

(Folding a paper in thirds using a rectangle)

1.

2.

3.

4.

5.

6.

7.

(Trisecting an angle)

1.

2.

3.

4.

More Origami
It is fun to construct different figures by paper folding. We will do simple origami. What's so special about them? When we unfold the figure, we will reveal beautiful patterns (unintentionally?) arising from our paper folding.

(Yacht)

1.

2.

3.

4.

5.

6.

(Reverse Fold)

7.

8.

9.

(Bird)

1.

2.

3.

4.

5.

6.

7.

8.

Solving Real Roots Using Paper Folding

Consider $$x^3 + b x^2 + c x + d = 0$$ where $b$, $c$, $d \in \mathbb{R}$. This is a polynomial of degree 3 (also called a cubic polynomial).

To get the real roots using paper folding:

1. Let $P$ denote $(0, 1)$, and $Q$ denote $(-b + d, c)$.
2. Make a single fold that simultaneously places $P$ on a point $P'$ on $y = -1$ and places $Q$ on a point $Q'$ on $x = -b - d$. This can be done in different ways, especially if the cubic polynomial has 3 real roots (in that case, 3 possible folds can be done).
3. The $x$-intercept of the fold line is a root of $x^3 + b x^2 + c x + d = 0$.

As an example, consider the equation $$x^3 - 2x^2 - x + 2 = 0.$$ Thus, $b = -2$, $c = -1$ and $d = 2$.

1. The points are $P(0,1)$ and $Q(-(-2) + 2, -1) = Q(4, -1)$.
2. Place $P$ on a point $P'$ on $y = -1$ and $Q$ on a point $Q'$ on $x = -(-2) - 2 = 0$.
3. The possible folds are as follows:
   
   
   
   
   
   
   
   
   

Conclusion

Origami and paper folding are fun to do. There are numerous complicated figures that one can make using this traditional Japanese paper art. But as we have seen, there is more to folding paper than meets the eye. Perfect geometric figures may be formed and discovered when paper are folded accordingly. Moreover, who knew that paper folding can be utilized to solve a cubic equation? These things surely put the fun in math!

ABOUT THE AUTHOR:
Patrick Vincent N. Lubenia is an Instructor at the Ateneo de Manila University. He obtained his B.S in Mathematics and M.S. in Applied Mathematics at the University of the Philippines Diliman in 2008 and 2012, respectively. He is currently finishing his M.S. in Finance in the same university.

OLYMPIAD CORNER

from the International Mathematical Olympiad Shortlist, 2010

Problem: Find the least positive integer $n$ for which there exists a set $\{s_{1},s_{2},\ldots,s_{n}\}$ consisting of $n$ distinct positive integers such that $$\left( 1-\frac{1}{s_{1}}\right) \left( 1-\frac{1}{s_{2}}\right) \cdots \left( 1-\frac{1}{s_{n}}\right) = \frac{42}{2010}.$$

Solution: 

Suppose that the desired numbers exist for some $n$. We may assume without loss of generality that $$s_{1}<s_{2}<\cdots <s_{n}.$$ Note that $s_{1}$ should be an integer greater than 1, otherwise $1-\frac{1}{s_{1}}=0$. This implies that $$2\leq s_{1}\leq s_{2}-1\leq \cdots \leq s_{n}-\left( n-1\right)$$ therefore $$\begin{eqnarray*} s_i &\geq &i+ 1 \\ \frac{1}{s_i} &\leq &\frac{1}{i+1} \\ 1 - \frac{1}{s_i} &\geq &1-\frac{1}{i+1} \end{eqnarray*}$$ for each $i = 1, 2, \ldots, n$.

Moreover, since the denominator of $\frac{42}{2010}=\frac{7}{5\cdot 67}$ is divisible by 67, some of the $s_{i}^{\prime }$'s should be divisible by 67, and hence $$\begin{eqnarray*} s_n &\geq &s_i \geq 67 \\ 1-\frac{1}{s_n} &\geq &1-\frac{1}{67} = \frac{66}{67}. \end{eqnarray*}$$ This means that $$\begin{eqnarray*}\frac{42}{2010} &=&\left(1-\frac{1}{s_1}\right) \left(1-\frac{1}{s_2}\right) \cdots \left(1-\frac{1}{s_{n-1}}\right)\left(1-\frac{1}{s_n}\right) \\ &\geq &\left(1-\frac{1}{2}\right) \left(1-\frac{1}{3}\right) \cdots \left(1-\frac{1}{n}\right) \left(\frac{66}{67}\right) \\ &=&\left(\frac{1}{2}\right) \left(\frac{2}{3}\right) \cdots \left(\frac{n-1}{n}\right) \left(\frac{66}{67}\right) \\ &=&\frac{66}{67n} \end{eqnarray*}$$ therefore $$n\geq \frac{\left( 2010\right) (66)}{\left( 42\right) \left( 67\right) }= \frac{330}{7}>47$$ and hence $n\geq 48$.

Now we are left to show that there exists a set $s_1, s_2, \ldots, s_{48}$ that satisfies the equality. Consider the set $$\{2,3,\ldots,32,33,36,37,\ldots,50,67\}$$ which contains exactly 48 numbers. Then  $$\begin{eqnarray*} &&\left(1-\frac{1}{2}\right) \cdots \left(1-\frac{1}{33}\right) \left(1 - \frac{1}{36}\right) \cdots \left(1-\frac{1}{50}\right) \left(1-\frac{1}{67}\right) \\ &=&\left[ \left(\frac{1}{2}\right) \cdots \left(\frac{32}{33}\right) \right] \left[ \left(\frac{35}{36}\right) \cdots \left(\frac{49}{50}\right)\right] \left(\frac{66}{67}\right) \\ &=&\left(\frac{1}{33}\right) \left(\frac{35}{50}\right) \left(\frac{66}{67}\right) \\ &=&\frac{7}{335} = \frac{42}{2010}. \end{eqnarray*}$$ The least positive integer $n$ is therefore equal to 48.

PROBLEMS

10. Show that if $2^{n}-1$ is prime, then $n$ must be prime.
    
11. Given a positive integer $n$, let $p\left(n\right)$ be the product of the nonzero digits of $n$. Determine the value of $p\left(1\right) + p\left(2\right) + \cdots + p\left(999\right) + p\left(1000\right).$
12. In $\triangle ABC$, $D$, $E$ are on $BC$ and $CA$ respectively, and $BD:DC=3:2$, $AE:EC=3:4$. $AD$ and $BE$ intersect at $M$. Given that the area of $\triangle ABC$ is $1$, find the area of $\triangle BMD$.

We welcome readers to submit solutions to the problems posed below for publication consideration. Solutions may ONLY be submitted online via vantonio@ateneo.edu. Solutions must be preceded by the solver's name, school affiliation and year level. The deadline for submission is 12:30 PM November 29, 2014. 

SOLUTIONS

(for November 8, 2014)

7. Let $a$, $b$, $c$ be positive integers with the properties: $a^{3}$ is divisible by $b$, $b^{3}$ is divisible by $c$, $c^{3}$ is divisible by $a$. Show that $\left(a+b+c\right)^{13}$ is divisible by $abc$. (Taken from Polish and Austrian Mathematical Olympiads 1981-1995 by M. Kuczma and E. Windischbacher)
   (solved by Farrell Eldrian Wu [MGC New Life Academy])
   
   
   SOLUTION: 
   Note that each of the terms in the expansion of $\left(a+b+c\right)^{13}$ has the form $a^{l}b^{m}c^{n}$, where $l$, $m$, and $n$ are nonnegative and $l+m+n=13$. Our goal is to show that each of the terms is divisible by $abc$.
   
   If $l,m,n\geq1$, then this is trivial. Let us consider the case when one of $l,m,n=0$.
   
   Suppose $l=0$. This means we have $b^{m}c^{n}$, where $m+n=13$.
   

   CASE 1:
   If $m=13$, $n=0$, then we have $b^{13}=b\cdot b^{3}\cdot b^{9}=b\left(cp\right)\left(c^{3}p^{3}\right)$ for some integer $p$, since $b^{3}$ is divisible by $c$. Moreover, $$b^{13} = b\left(cp\right)\left(c^3p^3\right) = b\left(cp\right)\left(aqp^3\right)$$ for some $q$, since $c^{3}$ is divisible by $a$. This means that the product $a^{0}b^{13}c^{0}$ is divisible by $abc$.
   
   CASE 2:
   If $10\leq m\leq12$, $1\leq n\leq3$, then we have $b^{m}c^{n}=b\cdot c\cdot b^{9} \left(b^{m-10}c^{n-1}\right)$, which is divisible by by $abc$ (since, based from the previous case, $b^{9}$ is divisible by $a$).
   
   CASE 3:
   If $1\leq m\leq9$, $4\leq n\leq12$, then we have $b^{m}c^{n}=b\cdot c\cdot c^{3}\left(b^{m-1}c^{n-4}\right)$, which is divisible by $abc$ (since $c^{3}$ is divisible by $a$).
   
   \textit{CASE 4:}
   If $m=0$, $n=13$, then we have $c^{13}=c\cdot c^{3}\cdot c^{9}=c\left(ar\right)\left(a^{3}r^{3}\right)$, for some integer $r$. Since $a^{3}$ is divisible by $b$, we can see that $c^{13}$ is divisible by $abc$.

In all cases, we see that $b^{m}c^{n}$ is divisible by $abc$. We can proceed with a similar proof for when $m=0$, and for $n=0$. This means that $\left(a+b+c\right)^{13}$ is divisible by $abc$.


8. An exam with $k$ questions is presented to $n$ students. A student fails the exam if he gets less than half the answers right. We say that a question is easy if more than half of the students get it right. Decide if it is possible that
   

   • All students fail even though all the questions were easy.
   • No student fails even though no question was easy.

   (Estonia 2007)
   (solved by Farrell Eldrian Wu [MGC New Life Academy])
   
   
   SOLUTION: 
   • For the first case, if all questions were easy, then more than $\dfrac{n}{2}$ students are able to to get each of the $k$ questions right. So $T>k\cdot\dfrac{n}{2}$ (note that this is a strict inequality).
     
     On the other hand, if each of the $n$ students failed, then all of them got less then $\dfrac{k}{2}$ questions right. This means that $T<n\dfrac{k}{2}$ (again, a strict inequality). Combining the two conditions makes the first case impossible.
   • For the second case, if no question was easy, then at most $\left\lceil \dfrac{n}{2}\right\rceil$ students got each of the $k$ questions right. So $T\leq k\left\lceil \dfrac{n}{2}\right\rceil$.
     
     Now, if no student fails, then each of the $n$ students got at least $\left\lceil \dfrac{k}{2} \right\rceil$ questions right. Then $T\geq n\left\lceil \dfrac{k}{2}\right\rceil$. Combining the two conditions, we have $n \left\lceil \dfrac{k}{2} \right\rceil \leq T \leq k \left\lceil \dfrac{n}{2} \right\rceil$, which means $T = \dfrac{nk}{2}$, where $n$ and $k$ are both even.
     
     Specifically, if a labeling will be implemented on the students $\left(1,2,\dots,n\right)$ and questions $\left(1,2,\ldots,k\right)$, then student $m$ should answer $l$ questions, where $m$ and $l$ have the same parity.
9. $2014$ points are given on a circle. They are split into $1007$ pairs and each pair is joined by a segment. Find the probability that no two of these segments intersect. (Taken from Problem-Solving Methods in Combinatorics by Pablo Soberon)
   (solved by Farrell Eldrian Wu [MGC New Life Academy])
   
   
   SOLUTION: 
   First, we count the number of ways to split the $2n$ points without considering the intersections. We choose $n$ points first, then choose which of the remaining $n$ points will be paired up with the initial group. Note that in choosing the pairs, the order matters. So this can be done in ${\displaystyle \binom{2n}{n}n!}$ ways. However, we still need to consider that in each segment, the order in which the vertices were chosen does not matter. So, upon incorporating the double count for each segment, we have $$\dfrac{{\displaystyle \binom{2n}{n}n!}}{2^{n}}$$ ways of pairing the $2n$ points.
   
   Now, we introduce a sequence of numbers $a_n$, where $a_n$ is defined to be the number of ways to connect $2n$ points on a circle where the connecting segments will not intersect. For the purpose of completeness, we define $a_0=1$. In addition, we label the points on the circle with $1,2,\ldots,2n$.
   
   We connect $1$ with any vertex $k$. The segment will divide the circle into two sections. Note that the remaining $2n-2$ vertices should still be paired up, and if $k$ is odd, then there will be one section (the one between $1$ and $k$) with an odd number of points, which means that one point in that section will have to be connected to one point on the other section, and the segment formed will intersect with the initial segment. This means that $k$ must be even.
   
   So $1$ must be connected to $2p$. Then the remaining $2p-2$ points between $1$ and $2p$ must be paired up between themselves (same is true for the other section, which contains the points $2p+1$ to $2n$, a total of $2n-2p$ points). By our definition, there are $a_{p-1}a_{n-p}$ ways that this can be done. So, upon doing this for all $p$, we get $$\begin{align*} a_{0} & = 1\\ a_{n} & = a_{n-1}a_{0}+a_{n-2}a_{1}+\cdots+a_{0}a_{n-1}, \end{align*}$$ which follows the definition of Catalan numbers. The closed form of numbers in this sequence is given by $$a_{n}=\frac{{\displaystyle \binom{2n}{n}}}{n+1}.$$ Thus, the probability of pairing the $2n$ points and forming non-intersecting segments is given by $$\dfrac{\frac{{\displaystyle \binom{2n}{n}}}{n+1}}{\dfrac{{\displaystyle \binom{2n}{n}n!}}{2^{n}}}=\frac{2^{n}}{\left(n+1\right)!}.$$ In our case, we just have $n=1007$, so the probability is $\dfrac{2^{1007}}{1008!}$.

Counting Beyond Your Fingers (Tuklas Vol. 16, No. 3 - November 8, 2014)

COUNTING BEYOND YOUR FINGERS

This article focuses on countable sets. For a discussion of uncountable sets (such as the set of real numbers $\mathbb{R}$) and a different perspective on countable sets, read Counting Infinity.

Cardinality
We know sets as collections of elements of a particular nature. These elements could be tangible - apples, cars, socks, or whatever else you have seen or touched or both - and need only be recalled, not imagined (though one can put forth a case for, say, unicorns). They could also be intangible or conceptual---numbers, colors, and other abstractions - and require more from thought than anything else.

Regardless of the nature of what it contains, a set can be measured by its cardinality, which is simply the number of elements in it. The set \(A = \{\text{red}, \text{orange}, \text{yellow}\}\), for example, has a cardinality of 3, while the set $B = \{2,4,7,12\}$ has a cardinality of 4. There are multiple notations for cardinality, but for this article, we will use the pound sign ($\#$) - that is, $\#A = 3$ and $\#B = 4$.

$A$ and $B$ above are finite sets because, as the name implies, they each have a finite number of elements. Owing to how the natural numbers are ordered ($1 < 2 < 3 < \cdots$), it is easy to compare the cardinalities of finite sets, but what happens when we focus on infinite sets (sets that have infinitely many elements)?

The Set of Perfect Squares
Consider the set $\mathbb{N} = \{1,2,3,...\}$ of natural numbers and the set $S = \{1,4,9,...\}$ of perfect squares. Working with the fact that $S$ is a subset of $\mathbb{N}$, it seems natural - pun sort of intended - to say that $\#\mathbb{N} > \#S$. $\mathbb{N}$ contains the elements of $S$ and more; is that not enough for us to say something about the relationship between their cardinalities?

Consider Table 1 below. As you can see, we can match the elements of $\mathbb{N}$ with those of $S$ (so we have $1^2 = 1, 2^2 = 4, 3^2 = 9$, and so on) and establish what we call a one-to-one correspondence between the two sets. Two sets are in one-to-one correspondence if each element of one can be matched with exactly one element of the other (in other words, partnerships are formed, and nothing gets left behind). By virtue of this matching, we are able to show that $\#\mathbb{N} = \#S$.

$\mathbb{N}$	$1$	$2$	$3$	$\cdots$
	$\downarrow$	$\downarrow$	$\downarrow$	$\cdots$
$S$	$1$	$4$	$9$	$\cdots$

This result is counter-intuitive and the method used above may leave you feeling cheated, but you have to concede that the argument has some sort of elegant brilliance going for it. Arguments made in relation to the infinite often do.

The Set of Integers $\mathbb{Z}$
We have shown that $\mathbb{N}$ and one of its subsets share the same cardinality. It only seems fair to consider a set $\mathbb{N}$ is a subset of. Let us look at the set of integers $\mathbb{Z}$.

The trouble with $\mathbb{Z}$ is that unlike $\mathbb{N}$, it does not have a smallest element. We can, however, reorder the elements of $\mathbb{Z}$ in a way that allows us to establish a one-to-one correspondence between $\mathbb{N}$ and $\mathbb{Z}$ (see Table 2 below) and ultimately show that $\#N = \#Z$.

$\mathbb{N}$	$1$	$2$	$3$	$4$	$5$	$\cdots$
	$\downarrow$	$\downarrow$	$\downarrow$	$\downarrow$	$\downarrow$	$\cdots$
$\mathbb{Z}$	$0$	$-1$	$1$	$-2$	$2$	$\cdots$

The Set of Rational Numbers $\mathbb{Q}$
Finally, we consider the set of rational numbers $\mathbb{Q}$. This set contains all fractions, the numerators and denominators of which are integers. Since every integer can be expressed as a fraction with a denominator of 1, $\mathbb{N}$ and $\mathbb{Z}$ are subsets of $\mathbb{Q}$. Could it be that the cardinality of this much larger - at least according to our intuition - set equals that of $\mathbb{N}$?

As a matter of fact, it does.

Note that we can order the rational numbers in the following manner: $$\boxed{\frac{1}{1}}, \boxed{\frac{1}{2}, \frac{2}{1}}, \boxed{\frac{1}{3}, \frac{2}{2}, \frac{3}{1}}, \boxed{\frac{1}{4}, \frac{2}{3}, \frac{3}{2}, \frac{4}{1}}, \ldots$$ The rational numbers in each box are ordered from least to greatest. The first box contains all rational numbers, the numerator and denominator of which (disregarding signs) add up to $2$. The second contains all rational numbers, the numerator and denominator of each of which add up to $3$. The process goes on indefinitely and enables us to list all rational numbers.

The only problem with this list is that some of the rational numbers in it are not in lowest terms and are mere repetitions of other rational numbers. This prompts us to create another list that does not include such numbers (note that $-\frac{2}{2}$ and $\frac{2}{2}$ have been removed): $$\boxed{-\frac{1}{1}, \frac{1}{1}}, \boxed{-\frac{2}{1}, -\frac{1}{2}, \frac{1}{2}, \frac{2}{1}}, \boxed{-\frac{3}{1}, -\frac{1}{3}, \frac{1}{3}, \frac{3}{1}}, \ldots$$ The list above enables us to establish a one-to-one correspondence between $\mathbb{N}$ and $\mathbb{Q}$ (see Table 3 below). Thus, $\#\mathbb{N} = \#\mathbb{Q}$.

$\mathbb{N}$	$1$	$2$	$3$	$4$	$5$	$6$	$\cdots$
	$\downarrow$	$\downarrow$	$\downarrow$	$\downarrow$	$\downarrow$	$\downarrow$	$\cdots$
$\mathbb{Z}$	$\frac{1}{1}$	$\frac{1}{2}$	$\frac{2}{1}$	$\frac{1}{3}$	$\frac{2}{2}$	$\frac{3}{1}$	$\cdots$

We have shown that $\#\mathbb{N} = \#\mathbb{Z} = \#\mathbb{Q}$ even if $\mathbb{Q}$ contains $\mathbb{Z}$, which contains $\mathbb{N}$. Working with the infinite is bracing, is it not?

Countable Sets
Countable sets are those that have the cardinality of $\mathbb{N}$ or some subset of it. (Recall that natural numbers are sometimes called counting numbers.) All finite sets are, therefore, countable. Because we have established that $S$, $\mathbb{Z}$, and $\mathbb{Q}$ have the cardinality of $\mathbb{N}$, they are also countable. Because they are infinite, they can be further classified as countably infinite sets. While the elements of $S$, $\mathbb{Z}$, and $\mathbb{Q}$ cannot be counted in the strictest sense---conventional counting requires that the process terminate at some point---they can be enumerated or listed one by one in an ordered manner, consistent with rules such as those we used above (recall how we reordered $\mathbb{Z}$ and $\mathbb{Q}$).

The phrase "countably infinite" may well be an oxymoron, and something of its kind may not fit well with most people's view that mathematics is the most rigorous field there is, but it is often forgotten that so much of the development of mathematics has arisen in response to contradictions that have left people no choice but to embrace them.

ABOUT THE AUTHOR:
Juan Carlo Mallari is an Instructor at the Ateneo de Manila University. He obtained his Master of Applied Mathematics major in Mathematical Finance degree at the Ateneo de Manila University in 2014.

REFERENCES:

- Byers, William. How Mathematicians Think. New Jersey: Princeton University Press, 2007. Print.

- Martin, Jesus Lemuel, Jr. "Counting Infinity." 19 January 2013. Tuklás Matemátika. Web. 28 October 2014.

OLYMPIAD CORNER

from the Vietnamese Mathematical Olympiad, 1979

Problem: Find all integer solutions of the system $$\begin{eqnarray*} x^{x+y} &=&y^{12} \qquad\qquad \text{(1)} \\ y^{y+x} &=&x^{3} \qquad\qquad\;\, \text{(2)} \end{eqnarray*}$$

Solution: 

1. If $y=0$, then from (1), we have $x^{x}=0$. This equation has no solution.
2. If $y=1$, then from (2), we have $x^{3}=1$, which gives $x=1$. The integer solution to the system is therefore $\left( 1,1\right)$.
3. If $y=-1$, then from (1), we have $x^{x-1}=1$, which gives $x=\pm 1$. We note that $\left( 1,-1\right)$ is a solution. On the other hand, $\left(-1,-1\right)$ does not satisfy (2), hence it is not a solution.
4. Suppose $y\neq 0,\pm 1$. Then from (2), we have $x=y^{\frac{x+y}{3}}$. Substituting this into (1) yields $$\begin{eqnarray*} y^{\frac{\left( x+y\right) ^{2}}{3}} &=&y^{12} \\ \frac{\left( x+y\right) ^{2}}{3} &=&12 \\ \left( x+y\right) ^{2} &=&36 \\ x+y &=&\pm 6 \end{eqnarray*}$$
   1. If $x+y=6$, then from (2), we have $y^{6}=x^{3}$, or $x=y^{2}$. This implies that $y^{2}+y-6=0$, and therefore $y=2, y=-3$. The corresponding solutions to the system are $\left( 4,2\right)$ and $\left( 9,-3\right)$.
   2. If $x+y=-6$, then from (2), we have $$\begin{eqnarray*} y^{-6} &=&\left( -6-y\right) ^{3} \\ y^{2} &=&\frac{1}{-6-y} \\ y^{3}+6y^{2}+1 &=&0 \end{eqnarray*}$$ By the Rational Root Theorem, the only possible integer solutions to the above equation are $1$ and $-1$. However, both numbers do not satisfy the above equation.

PROBLEMS

7. Let $a$, $b$, $c$ be positive integers with the properties: $a^{3}$ is divisible by $b$, $b^{3}$ is divisible by $c$, $c^{3}$ is divisible by $a$. Show that $\left(a+b+c\right)^{13}$ is divisible by $abc$.
   
8. An exam with $k$ questions is presented to $n$ students. A student fails the exam if he gets less than half the answers right. We say that a question is easy if more than half of the students get it right. Decide if it is possible that
   • All students fail even though all the questions were easy.
   • No student fails even though no question was easy.
9. $2014$ points are given on a circle. They are split into $1007$ pairs and each pair is joined by a segment. Find the probability that no two of these segments intersect.

We welcome readers to submit solutions to the problems posed below for publication consideration. Solutions may ONLY be submitted online via vantonio@ateneo.edu. Solutions must be preceded by the solver's name, school affiliation and year level. The deadline for submission is 12:30 PM November 22, 2014. 

SOLUTIONS

(for October 18 and 25, 2014)

1. There are given $2014$ sets, each containing $40$ elements. Every two sets have exactly one element in common. Prove that all $2014$ sets have exactly one element in common. (Taken from 144 Problems of the Austrian-Polish Mathematics Competition 1978-1993 by M. Kuczma)
   (Solved by Jayson Dwight S. Catindig [Ateneo de Manila HS] and Farrell Eldrian Wu [MGC New Life Academy])
   
   
   SOLUTION: 
   Let the sets be given by $A_{1},A_{2},\dots,A_{2014}$.
   
   For each $x\in A_{1}$, assign the indices $k\in\left\{ 1,\dots,2014\right\}$ all those such that $x\in A_{k}$. Since $A_{1}$ has $40$ elements and each two of the $A_{k}$'s have a common element, we can define a partitioning of $A_{1},\dots,A_{2014}$ into $k$ groups. They are grouped if they have an $x\in A_{1}$ in common. Note that here, some of the groups may be empty.
   
   By the pigeonhole principle, at least one group will have $\left\lceil \dfrac{2014}{40}\right\rceil =51$ of those indices. We relabel them such that $A_{2},A_{3},\dots,A_{52}$ belong to the same group. This means that there exists $x_{0}$ such that $x_{0}\in A_{1}\cap A_{2}\cap\cdots\cap A_{52}$.
   
   Now, suppose there exists $i$ such that $x_{0}\notin A_{i}$. Note that each of the $A_{k}$'s, $k=1,2,\dots,52$, has an element common with $A_{i}$. All those common elements must be different from one another since $x_{0}$ is the unique element of $A_{n}\cap A_{m}, \left(n,m=1,2,\cdots,52\right)$.
   
   This means that $A_{i}$ has at least $52$ elements, which is a contradiction.
   
   
2. Let $a, b, c$ be positive real numbers such that $abc=1$. Prove the inequality $$\frac{a}{a+b^{4}+c^{4}}+\frac{b}{b+c^{4}+a^{4}}+\frac{c}{c+a^{4}+b^{4}}\leq1.$$ (Taken from Inequalities by Z. Cvetkovski)
   (Partial credit for Jayson Dwight S. Catindig [Ateneo de Manila HS] and Farrell Eldrian Wu [MGC New Life Academy])
   
   
   SOLUTION: 
   By the Cauchy-Schwarz Inequality, we have $$\begin{align*} \left(a^{2}+b^{2}+c^{2}\right)^{2} & \leq \left[\left(\sqrt{a}\right)^{2}+\left(b^{2}\right)^{2}+\left(c^{2}\right)^{2}\right]\left[\left(\sqrt{a^{3}}\right)^{2}+1+1\right]\\ & = \left(a+b^{4}+c^{4}\right)\left(a^{3}+2\right). \end{align*}$$ Since $a$, $b$, and $c$ are positive, $$\begin{align*} \frac{1}{\left(a+b^{4}+c^{4}\right)\left(a^{3}+2\right)} & \leq \frac{1}{\left(a^{2}+b^{2}+c^{2}\right)^{2}}\\ \frac{a}{a+b^{4}+c^{4}} & \leq \frac{a\left(a^{3}+2\right)}{\left(a^{2}+b^{2}+c^{2}\right)^{2}} \end{align*}$$ Similarly, $$\frac{b}{b+c^{4}+a^{4}}\leq\frac{b\left(b^{3}+2\right)}{\left(a^{2}+b^{2}+c^{2}\right)^{2}}, \quad\frac{c}{c+a^{4}+b^{4}}\leq \frac{c\left(c^{3}+2\right)}{\left(a^{2}+b^{2}+c^{2}\right)^{2}}$$ This means that $$\frac{a}{a+b^{4}+c^{4}}+\frac{b}{b+c^{4}+a^{4}}+\frac{c}{c+a^{4}+b^{4}} \leq\frac{a^{4}+b^{4}+c^{4}+2\left(a+b+c\right)}{\left(a^{2}+b^{2}+c^{2}\right)^{2}}.$$ Now, since $abc=1$, $$\begin{align*} a+b+c & = abc\left(a+b+c\right)\\ a+b+c & \leq a^{2}b^{2}+b^{2}c^{2}+c^{2}a^{2}\\ a^{4}+b^{4}+c^{4}+2\left(a+b+c\right) & \leq a^{4}+b^{4}+c^{4}+2\left(a^{2}b^{2}+b^{2}c^{2}+c^{2}a^{2}\right)\\ & = \left(a^{2}+b^{2}+c^{2}\right)^{2}. \end{align*}$$ Finally, $$\frac{a}{a+b^{4}+c^{4}}+\frac{b}{b+c^{4}+a^{4}}+\frac{c}{c+a^{4}+b^{4}}\leq1.$$
3. Circles $C_{1}$ and $C_{2}$ with centers $O_{1}$ and $O_{2}$ respectively intersect each other at $A$ and $B$. Ray $O_{1}B$ intersects $C_{2}$ at $F$ and ray $O_{2}B$ intersects $C_{1}$ at $E$. The line parallel to $EF$ and passing through $B$ intersects $C_{1}$ and $C_{2}$ at $M$ and $N$, respectively. Prove that $MN=AE+AF$. (Taken from Mathematical Contests, 1995-1996 by Andreescu, Kedlaya and Zeitz)
   (Solved by Farrell Eldrian Wu [MGC New Life Academy])
   
   
   SOLUTION: 
   The figure for the problem is given below.
   
   

   

   Consider $\triangle AEF$. Note that $$\begin{align*} \angle EAB & = \frac{1}{2}\angle EO_{1}B\\ & = 90^{\circ}-\angle O_{1}BE\\ & = 90^{\circ}-\angle FBO_{2}\\ & = \angle BAF. \end{align*}$$ Since $\angle EAF=\angle EAB+\angle BAF$, then $AB$ is the angle bisector of $\angle EAF$.
   
   Note also that $$\begin{align*} \angle EBA+\angle FBA & = \angle EBA+\pi-\angle O_{1}BA\\ & = 180^{\circ}+\angle EBO_{1}\\ & = 270^{\circ}-\angle EAB\\ & = 270^{\circ}-\angle BAF. \end{align*}$$ This means that $$\begin{align*} \angle EBF & = 360^{\circ}-\angle EBA-\angle FBA\\ & = 360^{\circ}-\frac{1}{2}\left(270^{\circ}-\angle EAB+270^{\circ}-\angle BAF\right)\\ & = \frac{180^{\circ}+\angle EAF}{2}. \end{align*}$$ This means that $B$ is on the angle bisector of $\angle EAF$ and on some arc along $S_{1}$, which have a unique intersection. The incenter of $\triangle EAF$ also satisfies these conditions, and is unique. So the incenter must be $B$.
   
   So $\angle AEB=\angle BEF$, and by parallel lines, $\angle BEF=\angle EBM$. This means that $EBAM$ is an isosceles trapezoid, and $EA=MB$. In addition, $FA=NB$ and $$\begin{align*} MN & = MB+NB\\ & = AE+AF. \end{align*}$$
4. Is there a triangle where the three altitudes have lengths $1$, $\sqrt{5}$, and $1+\sqrt{5}$? (Kiev 1969)
   (Solved by Farrell Eldrian Wu [MGC New Life Academy])
   
   
   SOLUTION: 
   Suppose such a triangle exists. Call the sides perpendicular to the altitudes of length $1$, $\sqrt{5}$ and $1+\sqrt{5}$ be $a$, $b$, and $c$, respectively. If the area of the triangle is given by $A$, then we have $$\begin{align*} A & = \frac{1}{2}a\\ A & = \frac{1}{2}b\sqrt{5}\\ A & = \frac{1}{2}c\left(1+\sqrt{5}\right). \end{align*}$$ From this, the expressions for $a$, $b$, and $c$ are as follows: $$a=2A,\quad b=\frac{2A}{\sqrt{5}},c=\frac{2A}{1+\sqrt{5}}.$$ Note that $$\begin{align*} b+c & = 2A\left(\frac{1}{\sqrt{5}}+\frac{1}{1+\sqrt{5}}\right)\\ & < 2A\left(\frac{1}{2}+\frac{1}{1+2}\right)\\ & = \frac{5}{3}A\\ & < 2A=a, \end{align*}$$ which contradicts the Triangle Inequality. Hence, no triangle exists.
5. Let $0<a<b<c<d$ be odd integers such that $ad=bc$ and $a+d=2^{k}$, $b+c=2^{m}$, for some integers $k$ and $m$. Determine the value of $a$. (Taken from The Math Problems Notebook by Valentin Boju and Louis Funar)
   (Solved by Farrell Eldrian Wu [MGC New Life Academy]; partial credit for Jayson Dwight S. Catindig [Ateneo de Manila HS])
   
   
   SOLUTION: 
   Let $\dfrac{a}{b}=\dfrac{c}{d}=\dfrac{x}{y}$, where $\gcd\left(x,y\right)=1$. Since $a$, $b$, $c$, and $d$ are odd, then $x$ and $y$ are odd. Combining this with the given two conditions, $$a=\frac{x2^{m}\left(y-2^{k-m}x\right)}{y^{2}-x^{2}}.$$ Note that since $a$ is odd, $y^{2}-x^{2}=\left(y-x\right)\left(y+x\right)=2^{m}n$, for some integer $s$. Since $x$ and $y$ are odd, we come up with two expressions for $x$ and $y$: $$\begin{cases} y=2^{m-2}n_{1}+n_{2}\\ x=2^{m-2}n_{1}-n_{2} \end{cases}$$ $$\begin{cases} y=n_{1}+2^{m-2}n_{2}\\ x=n_{1}-2^{m-2}n_{2} \end{cases}$$ with $n_{1},n_{2}\in\mathbb{Z}$. Note that, upon applying these equations to the above expression of $a$, we see that $n_{1}$ must divide $2^{k-m}+1$ and $n_{2}$ must divide $2^{k-m}-1$.
   
   Moreover, we can see that if $\left(a-b\right)\left(a-c\right)>0$, then $$\begin{align*} a+\frac{bc}{a} & > b+c\\ a+d & > b+c, \end{align*}$$ which means that $k>m$.
   
   This means that if $a+\dfrac{bc}{a}\leq1+bc$, then $k<2m-2$.
   
   Going back to the first of our two expressions for $x$ and $y$, we have $n_{1}>2^{m-2}n_{2}$. Since $n_{1}$ divides $2^{k-m}+1$, this implies that $n_{2}=1$ and $n_{1}=2^{k-m}+1$.
   
   For the second case, we have $y\leq b < 2^{m-1}$, which means $n_{1}<2$, so $n_{1}=1$.
   
   Now, since $3y>2^{m-1}$, then $x=a$, and $y=b$, which means $n_{2}=2^{m-2}-1$, and $a=1$.
6. Show that the interval $\left[0,1\right]$ cannot be partitioned into two disjoint sets $A$ and $B$ such that $B=A+a$ for some real number $a$. (Austrian-Polish Mathematics Competition, 1982)
   (Solved by Danielle See [Jubilee Christian Academy] and Farrell Eldrian Wu [MGC New Life Academy]; partial credit for Jayson Dwight S. Catindig [Ateneo de Manila HS])
   
   
   SOLUTION: 
   Suppose such a partitioning exists. This means that $A\cap B=\emptyset$, and $A\cup B=\left[0,1\right]$. Without loss of generality, let $a>0$.
   
   This means that $\left(1-a,1\right]\subset B$. Moreover, $\left(1-2a,1-a\right]\subset A$.
   
   It can be shown, by induction, that $\left(1-\left(2n+1\right)a,1-2na\right]\subset B$ and $\left(1-\left(2n+2\right)a,1-\left(2n+1\right)a\right]\subset A$.
   
   However, there exists $m$ such that $\left(1-ma,1-\left(m-1\right)a\right]\nsubseteq\left[0,1\right]$. Such a set still is contained entirely in $A$ or $B$, which is a contradiction. Hence, no partitioning exists.