COUNTING BEYOND YOUR FINGERS
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:
- If \(y=0\), then from (1), we have \(x^{x}=0\). This equation has no solution.
- 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)\).
- 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.
- 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*} \]
- 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)\).
- 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.
- 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\).
- 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.
- \(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)
- 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.
- 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. \] - 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*} \] - 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. - 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\). - 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.
No comments:
Post a Comment