\documentclass[12pt]{article}
\usepackage{fullpage,amsmath,amssymb,graphicx}
\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}
\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''.}
\vfil\noindent{\bf Problem 2} (Larson's problem 1.2.9). Let $00$,
\[ 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.}
\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.
\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.
\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 size and orientation) is zero. Prove that the function is the zero function.
\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''.}
%\vfil\noindent{\bf Problem 10} (Larson's 2.6.10, expanded).
%\begin{enumerate}
%\item Let $\alpha$ be any real number. Prove that among the numbers
%\[ \alpha,\ 2\alpha,\ \ldots,\ (n-1)\alpha \]
%there is one that differs from an integer by at most $1/n$.
%\item Let $\alpha$ be an irrational number. Prove that the set $\{\{n\alpha\}\colon n\in\bbZ\}$ is dense in the unit interval $[0,1]$, where for a real number $x$, $\{x\}$ denotes its "fractional part" - the difference between $x$ and the largest integer $\lfloor x\rfloor$ smaller or equal to $x$.
%\end{enumerate}
\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}$.
\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$.
\vfil \centerline{\bf Good Luck!} \vfil
\end{document}