\documentclass [12pt]{article}
\usepackage{amsfonts}
\usepackage{geometry}
\usepackage{amsmath}
\setcounter{MaxMatrixCols}{30}
\usepackage{amssymb}
\usepackage{graphicx}
\setlength{\topmargin}{-0.5in} \setlength{\leftmargin}{0in}
\setlength{\oddsidemargin}{0in} \setlength{\evensidemargin}{0in}
\setlength{\textwidth}{6in} \setlength{\textheight}{8.84in}
\newcommand{\lbin}{\left(\!\begin{array}{c}}
\newcommand{\rbin}{\end{array}\!\right)}
\newcommand{\ldet}{\left|\begin{array}}
\newcommand{\rdet}{\end{array}\right|}
\newcommand{\lmat}{\left(\begin{array}}
\newcommand{\rmat}{\end{array}\right)}
\newcommand{\dspace}{\baselineskip 22pt}
\newcommand{\sspace}{\baselineskip 14pt}
\newcommand{\dps}{\displaystyle}
\newcommand{\qed}{\hfill\rule{2mm}{2mm} \\}
\newcommand{\ds}{\displaystyle}
\DeclareMathOperator{\tr}{tr}
\pagestyle{myheadings}
\begin{document}
\thispagestyle{empty}
\begin{center}
2017 Missouri Collegiate Mathematics Competition \\ Session I
\end{center}
\noindent 1. An \textit{autobiographical number} is a natural number with ten digits or less in which the first digit of the number (reading from left to right) tells you how many zeros are in the number, the second digit tells how many 1's, the third digit tells you how many 2's, and so on. For example,
\begin{equation*}
6,210,001,000
\end{equation*}
is an autobiographical number. Find the smallest autobiographical number and prove that it is the smallest.
\ \\ \ \\
\noindent Solution I.
\ \\ \ \\
When you add the digits of an autobiographical number, you count the total number of digits. (For example the digits of the above 10 digit autobiographical number must sum to 10.) Using this fact and the process of elimination we can find the smallest autobiographical number.
\smallskip
The only possible one-digit number whose digits sum to 1 is 1 and it is not autobiographical so there are no one digit autobiographical numbers.
\smallskip
The only possible two digit numbers whose digits sum to two are (in increasing order) 11 and 20 and they are not autobiographical so there are no two digit autobiographical numbers.
\smallskip
The only possible three digit numbers whose digits sum to three are (in increasing order) 102, 111, 120, 201, 210 and 300 and they are not autobiographical so there are no three digit autobiographical numbers.
\smallskip
The possible four digit numbers whose digits sum to four are (in increasing order) 1003, 1012, 1021, 1030, 1102, 1111, 1120, 1210, $\ldots$.
\smallskip
Checking these numbers we find that the first autobiographical number in this list, and hence the smallest autobiographical number is 1210.
\ \\ \ \\
\noindent Solution II.
\ \\ \ \\
\noindent First, using the greedy algorithm, we find the smallest autobiographical number with four digits. Then we show that there is no smaller autobiographical number.
\ \\ \ \\
\noindent Construction of the smallest 4-digit autobiographical number.
\ \\ \ \\
\noindent The smallest leftmost (first) digit we can have is 1.
\noindent The second digit (that counts the numbers of 1's) cannot be 1 (we already have one 1 in the first place). So the smallest available is 2.
\noindent Since we have one 2 now, the third digit has to be at least 1. So let it be 1.
\noindent The first digit was 1, so we must have one 0, put it in the fourth place. So 1210 is our smallest 4-digit autobiographical number.
\ \\ \ \\
\noindent No smaller autobiographical number exists.
\ \\ \ \\
\noindent Observe that the maximal digit a $k$-digit autobiographical number can have is $k-1$. Otherwise, if digit $k$ or higher is present, then there must be a 1 or a bigger digit in the $(k+1)$st or higher position, therefore the number has at least $(k+1)$ digits.
\ \\ \ \\
\noindent 1-digit autobiographical numbers do not exist.
\noindent By our observation they are allowed to have 0 as the only digit and 0 is not an autobiographical number.
\noindent 2-digit autobiographical numbers do not exist.
\noindent By our observation, the only allowed digits are 0 and 1. Neither 10 nor 11 are autobiographical numbers.
\noindent 3-digit autobiographical numbers do not exist.
\noindent Again, by our observation the only allowed digits are 0, 1, and 2.
\noindent If an autobiographical number starts with 1, then the second digit cannot be 1, (there would be two 1s) so the second digit must be 2. This creates a conflict for the third digit: leftmost digit, 1, requires it to be 0, the middle digit, 2, requires it to be 1.
\noindent If an autobiographical number starts with 2, then the remaining two digits must be 00, so the number is 200 which is not autobiographical.
\ \\ \ \\
\noindent Therefore, there are no autobiographical numbers with fewer than 4 digits and 1210 is the smallest one.
\bigskip
\noindent Problem 4 from 1995 P.E.I. Mathematics Competition.
\ \\ \ \\
\noindent 2. Recall that the trace $\tr(A)$ of an $n\times n$ matrix $A$ is the sum of the entries on the main diagonal of $A$. Let $A^T$ denote the transpose of the matrix $A$. Show that if $A$ and $B$ are $n\times n$ real-valued matrices with $\tr(AA^T+BB^T)=\tr(AB+A^TB^T)$, then it must be the case that $A=B^T$.
\ \\ \ \\
\noindent Solution.
\ \\ \ \\
\noindent We first recall a few basic facts about the trace function. First, recall that $\tr(C\pm D)=\tr(C)\pm \tr(D)$ and $\tr(CD)=\tr(DC)$ for any two $n\times n$ matrices $C$ and $D$. Secondly, $\tr(C^T)=\tr(C)$ for any $n\times n$ matrix $C$. Finally, note that $\tr(CC^T)$ is the sum of squares of the entries of the matrix $C$ and hence $\tr(CC^T)=0$ if and only if $C$ is the zero matrix. Consequently, $A=B^T$ if and only if $\tr((A-B^T)(A-B^T)^T)=0$. Now \begin{eqnarray*}\tr((A-B^T)(A-B^T)^T) &=&\tr((A-B^T)(A^T-B)) \\ &=&\tr(AA^T+B^TB-AB-B^TA^T) \\ &=&\tr(AA^T+B^TB)-\tr(AB+B^TA^T)\\ &=&\tr(AA^T)+\tr(BB^T)-\tr(AB)-\tr(A^TB^T)=0\end{eqnarray*} and we are done.
\ \\ \ \\
\noindent This problem is a modification of a problem found in \emph{Putnam and Beyond} by R\u{a}zvan Gelca and Titu Andreescu.
\ \\ \ \\
\noindent 3. Let $f$ be a real-valued continuous function on the closed interval $[0,1]$. Assuming that $\int_0^1\, f(x)\, dx=\frac{\pi}{4}$, show that there is some $y$ with $00$ for some $x_0, x_1\in (0,1)$. Since $g$ is continuous on $(0,1)$, by the Intermediate Value Theorem there is some $y$ between $x_0$ and $x_1$ with $g(y)=0$. Now $f(y)=\frac{1}{1+y^2}$. In either case, we have $y\in (0,1)$ with $f(y)=\frac{1}{1+y^2}$. Since $090^{\circ}$. Find the
minimum length of the perimeter of $ABC$.
\ \\ \ \\
\noindent Solution.
\ \\ \ \\
\noindent Let $a=BC$, $b=CA$, $c=AB$. By the Law of Sines,%
\[
\frac{b}{\sin B}=\frac{a}{\sin A}=\frac{c}{\sin C}.
\]
Since $\sin A=\sin\left( 2B\right) =2\sin B\cos B$, and $\sin C=\sin\left[
180^{\circ}-\left( A+B\right) \right] =\sin\left( A+B\right) =\sin\left(
3B\right) =3\sin B-4\sin^{3}B$, we have%
\[
a=2b\cos B\text{ and }c=b\left( 3-4\sin^{2}B\right) =b\left( 4\cos
^{2}B-1\right) .
\]
Thus, $c=b\left[ \left( \frac{a}{b}\right) ^{2}-1\right] $, so that
$a^{2}=b\left( b+c\right) $. Since we are looking for a triangle of smallest
perimeter, we may assume that $\gcd\left( a,b,c\right) =1$. In fact,
$\gcd\left( b,c\right) =1$ since any common factor of $b$ and $c$ would be a
factor of $a$ as well. Since a perfect square $a^{2}$ is expressed as a
product of two relatively prime positive integers $b$ and $b+c$, it must be
the case that both $b$ and $b+c$ are perfect squares. Thus, for some integers
$m$ and $n$ with $\gcd\left( m,n\right) =1$, we have $b=m^{2}$, $b+c=n^{2}$,
$a=mn$. Also, $2\cos B=\frac{a}{b}=\frac{n}{m}$. Since $C>90^{\circ}$, we have
$0**1$, $y+1>x$, and $x+1>y$. For the triangle to be acute, we require
also that $10$ for all $x$ in $[0,1]$. For each point $a$ in $[0,1]$, draw the tangent line to $y=f(x)$ at the point where $x=a$. Let $A(a)$ be the area bounded by the curve $y=f(x)$, the tangent line at $a$, and the lines $x=0$ and $x=1$. What value(s) of $a$ minimizes the area?
\ \\ \ \\
\noindent Solution.
\ \\ \ \\
\noindent An equation for the tangent line is $y=f'(a) (x-a) + f(a)$. So, $f'(x) = f(x)$,
\begin{align*}
A(a) &= \int_0^1 (f(x) - f'(a) (x-a) - f(a) ) \, dx \\
&= F(1) - F(0) - f'(a) \left( \frac{(1-a)^2}{2} - \frac{a^2}{2} \right) - f(a) \\
&= F(1) - F(0) - f'(a) \left( \frac{1-2a}{2} \right) - f(a) .
\end{align*}
Thus, the solution of
\begin{equation*}
0 = A'(a) = -f''(a) \left( \frac{1-2a}{2} \right) + f'(a) - f'(a)
\end{equation*}
is $a = \frac12$. Further, $A'(a)$ is negative for $a$ less than $\frac12$ and positive for $a$ greater than $\frac12$ since $f'' > 0$. Consequently, $A(\frac12)$ is the absolute minimum.
\ \\ \ \\
\noindent 2. Let $n$ be a positive integer. Evaluate
\[
\int_{0}^{\pi/2}\dfrac{\sin\left[ \left( 2n+1\right) x\right] }{\sin
x}\,dx.
\]
\ \\ \ \\
\noindent Solution.
\ \\ \ \\
\noindent We use induction to show the value of the integral is $\frac{\pi}{2}$. Set
\[
I_{n}=\int_{0}^{\pi/2}\dfrac{\sin\left[ \left( 2n+1\right) x\right] }{\sin
x}\,dx.
\]
Note that
\begin{align*}
I_{1} & =\int_{0}^{\pi/2}\dfrac{\sin\left( 3x\right) }{\sin x}\,dx\\
& =\int_{0}^{\pi/2}\dfrac{3\sin x-4\sin^{3}x}{\sin x}\,dx\\
& =\int_{0}^{\pi/2}\left( 3-4\sin^{2}x\right) \,dx\\
& =\int_{0}^{\pi/2}\left[ 1+2\cos\left( 2x\right) \right] \,dx\\
& =\left. \left[ x+\sin\left( 2x\right) \right] \right\vert _{0}^{\pi
/2}\\
& =\dfrac{\pi}{2}.
\end{align*}
We assume that the claimed equality holds for $n-1$. To show that the equality
holds for $n$, we apply the angle sum identity for sine, obtaining
\begin{align*}
&\int_{0}^{\pi/2}\dfrac{\sin\left( 2n+1\right) x}{\sin x}\,dx =\int
_{0}^{\pi/2}\dfrac{\sin2nx\cos x+\cos2nx\sin x}{\sin x}\,dx\\
& =\int_{0}^{\pi/2}\dfrac{\sin2nx\cos x}{\sin x}\,dx+\int_{0}^{\pi/2}
\cos2nx\,dx\\
& =\int_{0}^{\pi/2}\dfrac{\sin2nx\cos x}{\sin x}\,dx\\
& =\int_{0}^{\pi/2}\dfrac{\left[ \sin\left[ \left( 2n-1\right) x\right]
\cos x+\cos\left[ \left( 2n-1\right) x\right] \sin x\right] \cos x}{\sin
x}\,dx\\
& =\int_{0}^{\pi/2}\dfrac{\sin\left[ \left( 2n-1\right) x\right] \cos
^{2}x}{\sin x}\,dx+\int_{0}^{\pi/2}\cos x\cos\left[ \left( 2n-1\right)
x\right] \,dx\\
& =\int_{0}^{\pi/2}\dfrac{\sin\left[ \left( 2n-1\right) x\right] \left(
1-\sin^{2}x\right) }{\sin x}\,dx+\int_{0}^{\pi/2}\cos x\cos\left[ \left(
2n-1\right) x\right] \,dx\\
& =\int_{0}^{\pi/2}\dfrac{\sin\left[ \left( 2n-1\right) x\right] }{\sin
x}\,dx-\int_{0}^{\pi/2}\sin x\sin\left[ \left( 2n-1\right) x\right]
\,dx+\int_{0}^{\pi/2}\cos x\cos\left[ \left( 2n-1\right) x\right] \,dx\\
& =I_{n-1}-\dfrac{1}{2}\int_{0}^{\pi/2}\left( \cos\left[ \left(
2n-2\right) x\right] -\cos\left( 2nx\right) \right) \,dx+\dfrac{1}{2}
\int_{0}^{\pi/2}\left( \cos\left[ \left( 2n-2\right) x\right]
+\cos\left( 2nx\right) \right) \,dx\\
& =\dfrac{\pi}{2}+\int_{0}^{\pi/2}\cos\left( 2nx\right) \,dx\\
& =\dfrac{\pi}{2}.
\end{align*}
\ \\ \ \\
\noindent This problem is Monthly 2758, ODMPB, p.~2.
\ \\ \ \\
\noindent 3. Let $n$ be a fixed positive integer. Let $M_{n}\left( \mathbb{Z}_{2}\right) $
denote the set of $n\times n$ matrices with entries in $\mathbb{Z}_{2}$.
Given $A\in M_{n}\left( \mathbb{Z}_{2}\right) $, what is the probability
that $A$ is invertible? (Hint: Recall that $\mathbb{Z}_{2} = \{ 0,1 \}$ and all arithmetic is modulo 2.)
\ \\ \ \\
\noindent Solution.
\ \\ \ \\
\noindent The set $M_{n}\left( \mathbb{Z}_{2}\right) $ has $2^{n^{2}}$ elements. A
matrix $A\in M_{n}\left( \mathbb{Z}_{2}\right) $ is invertible if and only
if its rows are linearly independent. We count the number of elements of
$M_{n}\left( \mathbb{Z}_{2}\right) $ with independent rows. We note that a
linear combination of vectors with entries in $\mathbb{Z}_{2}$ is a sum of
some subset of the vectors.
\begin{itemize}
\item The first row can be any nonzero row. There are $2^{n}-1$ such rows.
\item The second row can be any nonzero row different from the first row.
There are $2^{n}-2$ such rows.
\item The third row can be any nonzero row different from the first two rows
and different from their sum. There are $2^{n}-4$ such rows.
\item The $k$th row can be any nonzero row not equal to any previous row or
sum of previous rows. Thus, of the $2^{n}$ possible rows, we exclude $2^{k-1}$ rows since this is the number of subsets of the set of $k-1$
previous rows. There are thus $2^{n}-2^{k-1}$ choices for row $k$.
\end{itemize}
The desired probability is therefore
\[
P=\dfrac{\prod\limits_{k=1}^{n}\left( 2^{n}-2^{k-1}\right) }{2^{n^{2}}}.
\]%
Alternatively, we can write this as
\begin{align*}
P &=\dfrac{\prod\limits_{k=1}^{n}\left( 2^{n}-2^{k-1}\right) }{
\prod\limits_{k=1}^{n}2^{n}} \\
&=\prod\limits_{k=1}^{n}\dfrac{2^{n}-2^{k-1}}{2^{n}} = \prod\limits_{m=1}^{n}\dfrac{2^{n}-2^{n-m}}{2^{n}} \\
&=\prod\limits_{m=1}^{n}\left( 1-2^{-m}\right) =\prod\limits_{m=1}^{n}\dfrac{2^{m}-1}{2^{m}}.
\end{align*}
\ \\ \ \\
\noindent 4. Find, with proof, all solutions in nonnegative integers $x$, $y$,
$z$ to
\begin{equation}\label{dioph}
2^{x}+4^{y}=6^{z}.
\end{equation}
\ \\ \ \\
\noindent Solution.
\ \\ \ \\
\noindent Suppose that $\left( x,y,z\right) $ solves (\ref{dioph}).
\begin{enumerate}
\item[(a)] First suppose that $z$ is even. Write $z=2l$. Then (\ref{dioph}) is equivalent to
\[
2^{x}=6^{2l}-2^{2y}=\left( 6^{l}+2^{y}\right) \left( 6^{l}-2^{y}\right) ,
\]
so that there are positive integers $x_{1}>x_{2}$, $x_{1}+x_{2}=x$, such that%
\begin{equation}\label{diophsys}
\left\{
\begin{array}
[c]{c}%
6^{l}+2^{y}=2^{x_{1}}\\
6^{l}-2^{y}=2^{x_{2}}
\end{array}
\right.
\end{equation}
Subtracting gives
\[
2\cdot2^{y}=2^{x_{1}}-2^{x_{2}}=2^{x_{2}}\left( 2^{x_{1}-x_{2}}-1\right) .
\]
The last factor is odd, and hence must be 1. Therefore $x_{1}-x_{2}=1$, and
\[
\left\{
\begin{array}
[c]{c}%
x_{1}=y+2\\
x_{2}=y+1
\end{array}
\right. .
\]
This implies that $x=2y+3$. Adding in (\ref{diophsys}) gives
\[
2\cdot6^{l}=2^{y+1}\cdot3.
\]
Thus, $l=1$, and $y=1$. This yields
\[
\left( x,y,z\right) =\left( 5,1,2\right) ,
\]
which is readily verified to be a solution.
\item[(b)] Now suppose $z$ is odd. Write $z=2l+1$. Then
\[
2^{x}+2^{2y}=6^{2l+1}=2^{2l+1}\cdot3^{2l+1}.
\]
\begin{itemize}
\item If $x>2y$, then
\[
2^{2y}\left( 2^{x-2y}+1\right) =2^{2l+1}\cdot3^{2l+1},
\]
which is impossible since $2y$ is even and $2l+1$ is odd.
\item If $x=2y$, then%
\[
2\cdot2^{2y}=2^{2l+1}\cdot3^{2l+1},
\]
which is impossible since 3 divides the right side but not the left.
\item If $x<2y$, then
\[
2^{x}\left( 2^{2y-x}+1\right) =2^{2l+1}\cdot3^{2l+1},
\]
implying that $x=2l+1$, and
\begin{equation}\label{dioph2}
2^{2y-x}=9^{l}\cdot3-1.
\end{equation}
If $2y-x\geq2$, then the left-hand side of (\ref{dioph2}) is congruent to 0
$\operatorname{mod}4$, while the right-hand side is congruent to $2$. Hence,
$2y-x=1$, so that $y=l+1$, and $l=0$. This yields
\[
\left( x,y,z\right) =\left( 1,1,1\right) ,
\]
which is again a solution.
\end{itemize}
\end{enumerate}
\ \\ \ \\
\noindent 5. Given $2017$ points in the plane, what is the largest number of line segments that can be drawn connecting these points such that distinct segments intersect only at their endpoints?
\ \\ \ \\
\noindent Solution.
\ \\ \ \\
\noindent The problem can just as easily be solved for $n$ points in the plane. Consider the configurations of $n$ points and $m$ segments as a planar graph with $n$ vertices and $m$ edges. Add as many edges as needed to triangulate the plane; that is, ensure that every region of the plane is bounded by exactly three edges/segments. If $V=n$ is the number of vertices in this new graph, $E$ is the number of edges/segments of the new graph, and $F$ is the number of regions in the plane created by the new graph, Euler's Formula tells us that $V-E+F=2$ and so $E-F=n-2$. Since every edge belongs to two faces and every face has exactly three edges, $2E=3F$ and hence $E=3n-6$. Removing the edges previously added, $m\leq 3n-6$, with equality if and only if the original configuration was a triangulation of the plane. With $n=2017$, the maximum number of edges is $3\cdot 2017-6=6045$.
\ \\ \ \\
\noindent This problem is a modification of a problem from the 1976 German Mathematical Olympiad.
\end{document}
**