\documentclass[12pt]{article}
\usepackage{fullpage,amsmath,amssymb,graphicx,multicol}
\usepackage[usenames,dvipsnames]{xcolor}
% Following http://tex.stackexchange.com/a/847/22475:
\usepackage[setpagesize=false]{hyperref}\hypersetup{colorlinks,
  linkcolor={blue!50!black},
  citecolor={blue!50!black},
  urlcolor=blue
}
\usepackage{soul} \setstcolor{red}
\setlength\parindent{0in}

\def\bbR{{\mathbb R}}
\def\bbZ{{\mathbb Z}}
\def\myurl{http://www.math.toronto.edu/~drorbn/}
\def\red{\color{red}}

\begin{document}

{\small
  \href{\myurl}{Dror Bar-Natan}:
  \href{\myurl/classes/}{Classes}:
  \href{\myurl/classes/\#1516}{2015-16}:
  \hfill\url{http://drorbn.net/16-475/}
}

\vfil

\begin{center}
  {\Large UNIVERSITY OF TORONTO}\\
  \vskip 2mm
  {\large Faculty of Arts and Sciences}\\
  \vskip 2mm
  {\Large APRIL EXAMINATIONS 2016}\\
  \vskip 2mm
  {\Large \href{\myurl/classes/16-475-ProblemSolving/}{Math 475H1 Problem Solving Seminar} --- Final Exam}

  \vskip 2mm

  April 28, 2016\par
\end{center}

\vfil

Solve 8 of the following 11 problems. Indicate clearly which problems you wish graded; otherwise an arbitrary subset of the problems you have attempted will be chosen for marking. The problems carry equal weight.

\vfil

\noindent{\bf Duration. } You have 3 hours to write this exam.

\vskip 2mm

\noindent{\bf Allowed Material. } Stationary only.

\vskip 4mm

\noindent This booklet consists of 3 printed pages.

\vfil

\centerline{{\bf Good Luck!}}

\vfil

\newpage

\par\noindent{\small {\bf Tip. } Don't start working! Read the whole exam first. You may wish to start with the questions that are easiest for you.}

\vfil\noindent{\bf Problem 1} (Larson's 1.1.4). Find positive natural numbers $n$ and $a_1,a_2,\ldots,a_n$ such that the sum ${a_1+\cdots+a_n}$ is 1000 and the product $a_1a_2\cdots a_n$ is as large as possible.

\par\noindent{\small {\bf Tip. } In math exam, ``find'' means ``find and explain how you found''.}

{\red\footnotesize
Ans: $3^{332}2^2$
\hfill 8/10: Found pattern for $A$ through 10; no proof.
\newline 5/10: Optimized the $a_i$ using calculus, for a fixed $n$.
\hfill 2/10: Right answer, no justification.
\newline 7/10: Correct ``lemmas'', no proofs.
}

\vfil\noindent{\bf Problem 2} (Larson's problem 1.2.9). Let $0<a<b$ be real numbers. If two points are selected at random from a straight line segment of length $b$, what is the probability that the distance between them is at least $a$?

\par\noindent{\small {\bf Tip. } Neatness, cleanliness and organization count, here and everywhere else!}

{\red\footnotesize
Ans. $(b-a)^2/b^2$.
\hfill 4/10: Right answer, no justification.
\newline 8/10: Correct shading, wrong calculation.
\hfill 8.5/10: Complementary computation.
}

\vfil\noindent{\bf Problem 3} (Larson's 1.3.1). Find a general formula for the $n$th derivative of the function $\displaystyle f(x)=\frac{1}{1-x^2}$.

{\red\footnotesize
Ans: $\displaystyle \frac{n!}{2}\left(
  \frac{(-1)^n}{(1+x)^{n+1}} + \frac{1}{(1-x)^{n+1}}
\right)$
\hfill 2/10: Brute-computed $f'$, $f''$ and stopped.
}

\vfil\noindent{\bf Problem 4} (Larson's 1.4.3). Prove that there does not exist positive integers $x$, $y$, and $z$ such that $x^2+y^2+z^2=2xyz$.

{\red\footnotesize
3/10: Correct division into cases, then null.
\hfill (-5): unjustified elimination of the (eee) case.
\newline (-2): Eliminated (ooe) before (eee), thus not the general (ooe) case.
}

\vfil\noindent{\bf Problem 5} (Larson's 1.5.4). Let $-1 < a_0 < 1$ and define recursively for $n>0$,
\[ a_n=\left(\frac{1+a_{n-1}}{2}\right)^{1/2}. \]
What happens to $4^n(1-a_n)$ as $n\rightarrow\infty$?

\par\noindent{\small {\bf Tip. } Here and almost always, a concise yet precise solution is better than a lengthy roundabout one.}

{\red\footnotesize
Sol'n. With $a_0=\cos\theta$, get $a_n=\cos(\theta/2^n)\sim 1-\theta^2/2^{2n+1}$. So $\lim=\theta^2/2=(\arccos a_0)^2/2$.
\par 5/10: Got $a_n$ but not the quadratic $\cos$ approximation.
}

\vfil\noindent{\bf Problem 6.} Prove: You cannot colour the points of the plane with just three colours, so that no two points of distance 1 will be coloured with the same colour.

{\red\footnotesize
5/10: Constructed a diamond and stopped.
}

\vfil\newpage

\vfil\noindent{\bf Problem 7} (Larson's 2.6.1). Let $n$ be a natural number. Given $n+1$ positive integers, none of which exceeds $2n$, show that one of these integers divides another of these integers.

{\red\footnotesize
1/10: Said ``pigeonhole''.
}

\vfil\noindent{\bf Problem 8.} A function on the plane has the property that the sum of its values on the corners of any square (of any {\red positive} size and orientation) is zero. Prove that the function is the zero function.

{\red\footnotesize
4/10: Random playing with correct facts.
\hfill 5/10: Correct assuming integrability.
}

\vfil\noindent{\bf Problem 9} (part of Larson's 2.5.13). A {\em derangement} is a permutation $\sigma\in S_n$ such that for every $i$, $\sigma i\neq i$. Let $g_n$ be the number of derangements in $S_n$. Show that
\[ g_1=0,\quad g_2=1,\quad g_n=(n-1)(g_{n-1}+g_{n-2}). \]
Hint. A derangement interchanges $1$ with some other element, or not.

\par\noindent{\small {\bf Tip. } In math-talk, ``show'' means ``prove''.}

{\red\footnotesize
Point division is 1-1-8.
\hfill (-1.5) ``removing'' instead of ``rerouting'', in hard case.
\newline (-3) no explanation of hard case.
}

\vfil\noindent{\bf Problem 10} (Larson's 1.12.4c, modified) Compute the sum $\displaystyle \sum_{k=0}^n \frac{(-1)^k}{k+1}\binom{n}{k}$.

{\red\footnotesize
Ans. $\displaystyle
  = \left.\frac{1}{x}\int_0^x (1+t)^n\,dt\right|_{x=-1}
  = \left.\frac{1}{x}\left[\frac{(1+t)^{n+1}}{n+1}\right]_0^x\right|_{x=-1}
  = \left.\frac{1}{x}\left(\frac{(1+x)^{n+1}-1}{n+1}\right)\right|_{x=-1}
  = \frac{1}{n+1}
$.
\newline 5/10: All correct with derivative instead of integral.
\hfill 7/10: Indefinite instead of definite integration.
}

\vfil\noindent{\bf Problem 11} (Larson's 1.10.10, reworded). Show that for every positive integer $a$, the equation
$x^2-y^2=a^3$ has solutions with $x,y\in\bbZ$.

{\red\footnotesize
5/10: Only the odd case.
\hfill 6/10: Found $x\&y$, no discussion of parities.
}

\vfil \centerline{\bf Good Luck!} \vfil

\end{document}