% LaTeX solution template for Math 235
% -----------------------------------------------------------------

% Like most advanced LaTeX files, this one begins with a lot of
% boilerplate. You don't need to understand (or even read) most of it.
% All you need to do is fill in your name, email address,
% and the number of the pset. (Search for "METADATA" to find the place
% for this.) Then, you can go straight to the "EXERCISE 1"
% section and start writing your solutions.
% The "VARIOUS USEFUL COMMANDS" section is probably worth taking a
% look at at some point.

% If you are here to learn about LaTeX, search for
% "START READING HERE" and start reading there.

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------
\documentclass[paper=a4, fontsize=12pt]{scrartcl} % A4 paper and 12pt font size
\usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs
\usepackage[english]{babel} % English language/hyphenation
\usepackage{amsmath,amsfonts,amsthm,amssymb} % Math packages
\usepackage{mathrsfs}    % More math packages
\usepackage{sectsty}  % Allows customizing section commands
\allsectionsfont{\centering \normalfont\scshape} % Make all section titles centered, the default font and small caps %remove this to left align section tites
\usepackage{hyperref} % Turns cross-references into hyperlinks,
                      % and defines \url and \href commands.
\usepackage{graphicx} % For embedding graphics files.
\usepackage{framed}   % For the "leftbar" environment used below.
\usepackage{ifthen}   % Used for the \powset command below.
\usepackage{lastpage} % for counting the number of pages
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[height=10in,a4paper,hmargin={1in,0.8in}]{geometry}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}     % This is a powerful tool to draw vector
                      % graphics inside LaTeX. In particular, you can
                      % use it to draw graphs.
\usepackage{verbatim} % For the "verbatim" environment, in which
                      % special symbols can be used freely without
                      % confusing the compiler. (And it's typeset in
                      % a constant-width font.)
                      % Useful, e.g., for quoting code (or ASCII art).

%\numberwithin{table}{section} % Number tables within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)

\setlength\parindent{20pt} % Makes indentation for paragraphs longer.
                           % This makes paragraphs stand out more.

%----------------------------------------------------------------------------------------
%	VARIOUS USEFUL COMMANDS
%----------------------------------------------------------------------------------------
% The commands below might be convenient. For example, you probably
% prefer to write $\powset[2]{V}$ for the set of $2$-element subsets
% of $V$, rather than writing $\mathcal{P}_2(V)$.
% Notice that you can easily define your own commands like this.
% Caveat: Some of these commands need to be properly "guarded" when
% they occur in subscripts or superscripts. So you should not write
% $K_\CC$, but rather $K_{\CC}$.
\newcommand{\CC}{\mathbb{C}} % complex numbers
\newcommand{\RR}{\mathbb{R}} % real numbers
\newcommand{\QQ}{\mathbb{Q}} % rational numbers
\newcommand{\NN}{\mathbb{N}} % nonnegative integers
\newcommand{\Z}[1]{\mathbb{Z}/#1\mathbb{Z}} % integers modulo k
                                            % (syntax: "\Z{k}")
\newcommand{\ZZ}{\mathbb{Z}} % integers
\newcommand{\id}{\operatorname{id}} % identity map
\newcommand{\lcm}{\operatorname{lcm}}
% Lowest common multiple. For historical reasons, LaTeX has a \gcd
% command built in, but not an \lcm command. The preceding line
% rectifies that.
\newcommand{\rev}{\operatorname{rev}} % reversal of a walk
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
% $\powset[k]{S}$ stands for the set of all $k$-element subsets of
% $S$. The argument $k$ is optional, and if not provided, the result
% is the whole powerset of $S$.
\newcommand{\set}[1]{\left\{ #1 \right\}}
% $\set{...}$ compiles to {...} (set-brackets).
\newcommand{\abs}[1]{\left| #1 \right|}
% $\abs{...}$ compiles to |...| (absolute value, or size of a set).
\newcommand{\tup}[1]{\left( #1 \right)}
% $\tup{...}$ compiles to (...) (parentheses, or tuple-brackets).
\newcommand{\ive}[1]{\left[ #1 \right]}
% $\ive{...}$ compiles to [...] (Iverson bracket, aka truth value).
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
% $\floor{...}$ compiles to |_..._| (floor function).
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
% $\verts{...}$ compiles to V(...) (vertex set of a graph/digraph).
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
% $\edges{...}$ compiles to E(...) (edge set of a graph).
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
% $\arcs{...}$ compiles to A(...) (arc set of a digraph).
\newcommand{\lf}[2]{#1^{\underline{#2}}}
% $\lf{...1}{...2}$ compiles to $...1^{\underline{...2}}$.
% This is a notation for the falling factorial.
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
% $\underbrack{...1}{...2}$ yields
% $\underbrace{...1}_{\substack{...2}}$. This is useful for doing
% local rewriting transformations on mathematical expressions with
% justifications. For example, try this out:
% $ \underbrack{(a+b)^2}{= a^2 + 2ab + b^2 \\ \text{(by the binomial formula)}} $
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height
\newcommand{\nnn}{\nonumber\\} % Don't number this line in an "align" environment, and move on to the next line.
\newcommand{\explain}[1]{\tup{\hspace{-0.5pc}\text{\begin{tabular}{c}#1\end{tabular}\hspace{-0.5pc}}}}
% $\explain{...}$ interprets the "..." as text (you can
% nest some math inside by putting it in $...$'s as you
% would in any other text block) and puts it in parentheses.

%----------------------------------------------------------------------------------------
%	MAKING SUMMATION SIGNS ALWAYS PUT THEIR BOUNDS ABOVE AND BELOW
%	THE SIGN
%----------------------------------------------------------------------------------------
% The following are hacks to ensure that sums (such as
% $\sum_{k=1}^n k$) always put their bounds (i.e., the $k=1$ and the
% $n$) underneath and above the sign, as opposed to on its right.
% Same for products (\prod), set unions (\bigcup) and set
% intersections (\bigcap). Remove the 8 lines below if you do not want
% this behavior.
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}

%----------------------------------------------------------------------------------------
%	ENVIRONMENTS
%----------------------------------------------------------------------------------------
% The incantations below define how theorem environments
% (\begin{theorem} ... \end{theorem}) and their likes will look like.
\newtheoremstyle{plainsl}% <name>
  {8pt plus 2pt minus 4pt}% <Space above>
  {8pt plus 2pt minus 4pt}% <Space below>
  {\slshape}% <Body font>
  {0pt}% <Indent amount>
  {\bfseries}% <Theorem head font>
  {.}% <Punctuation after theorem head>
  {5pt plus 1pt minus 1pt}% <Space after theorem headi>
  {}% <Theorem head spec (can be left empty, meaning `normal')>

% Environments which make the text inside them slanted:
\theoremstyle{plainsl}
  \newtheorem{theorem}{Theorem}[section]
  \newtheorem{proposition}[theorem]{Proposition}
  \newtheorem{lemma}[theorem]{Lemma}
  \newtheorem{corollary}[theorem]{Corollary}
  \newtheorem{conjecture}[theorem]{Conjecture}
% Environments that don't:
\theoremstyle{definition}
  \newtheorem{definition}[theorem]{Definition}
  \newtheorem{example}[theorem]{Example}
  \newtheorem{exercise}[theorem]{Exercise}
  \newtheorem{examples}[theorem]{Examples}
  \newtheorem{algorithm}[theorem]{Algorithm}
  \newtheorem{question}[theorem]{Question}
 \theoremstyle{remark}
  \newtheorem{remark}[theorem]{Remark}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}

%----------------------------------------------------------------------------------------
%	METADATA
%----------------------------------------------------------------------------------------
\newcommand{\myname}{Darij Grinberg} % ENTER YOUR NAME HERE
\newcommand{\mymail}{darij.grinberg@drexel.edu} % ENTER YOUR EMAIL HERE
\newcommand{\psetnumber}{0} % ENTER THE NUMBER OF THIS PSET HERE

%----------------------------------------------------------------------------------------
%	HEADER AND FOOTER
%----------------------------------------------------------------------------------------
\ihead{Solutions to homework set \#\psetnumber} % Page header left
\ohead{page \thepage\ of \pageref{LastPage}} % Page header right
\ifoot{\myname} % left footer
\ofoot{\mymail} % right footer

%----------------------------------------------------------------------------------------
%	TITLE SECTION
%----------------------------------------------------------------------------------------
\title{	
\normalfont \normalsize 
\textsc{Drexel University, Department of Mathematics} \\ [25pt] % Your university, school and/or department name(s)
\horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule
\huge Math 235: Mathematical Problem Solving, \\
Fall 2024:
Homework \psetnumber\\% The assignment title
\horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule
}
\author{\myname}

\begin{document}

\maketitle % This command causes the title part to be printed.

\begin{center}
\Large
\textbf{Diagnostic homework set} graded on completion. Please attempt to write meaningful responses (not necessarily complete solutions) to all exercises! \\
% \textbf{Please solve 4 of the 8 exercises!} \\
\textbf{Deadline:} September 25, 2024
\end{center}

%----------------------------------------------------------------------------------------
%	EXERCISE 1
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 1}

\subsection{Problem}

Have you participated in mathematical contests,
coding challenges, puzzle competitions and the likes?
If so, which ones, and which were your favorites?

\subsection{Solution}

...

%----------------------------------------------------------------------------------------
%	EXERCISE 2
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 2}

\subsection{Problem}

A \emph{domino} shall mean a
$1 \times 2$-rectangle or a $2 \times 1$-rectangle.
A board shaped like a $8 \times 8$-square can easily be
tiled with dominoes, e.g., as follows:
\[
\begin{tikzpicture}[scale=0.7]
\draw(0,0) rectangle (1,2);
\draw(1,0) rectangle (3,1);
\draw(1,1) rectangle (2,3);
\draw(0,2) rectangle (1,4);
\draw(3,0) rectangle (5,1);
\draw(2,1) rectangle (3,3);
\draw(2,3) rectangle (4,4);
\draw(1,3) rectangle (2,5);
\draw(0,4) rectangle (1,6);
\draw(3,1) rectangle (5,2);
\draw(3,2) rectangle (5,3);
\draw(0,6) rectangle (2,7);
\draw(0,7) rectangle (2,8);
\draw(1,5) rectangle (3,6);
\draw(2,4) rectangle (4,5);
\draw(2,6) rectangle (3,8);
\draw(3,5) rectangle (4,7);
\draw(3,7) rectangle (5,8);
\draw(5,7) rectangle (7,8);
\draw(7,6) rectangle (8,8);
\draw(4,6) rectangle (6,7);
\draw(6,5) rectangle (7,7);
\draw(4,4) rectangle (5,6);
\draw(5,4) rectangle (6,6);
\draw(7,4) rectangle (8,6);
\draw(6,3) rectangle (7,5);
\draw(4,3) rectangle (6,4);
\draw(7,2) rectangle (8,4);
\draw(5,1) rectangle (6,3);
\draw(6,1) rectangle (7,3);
\draw(5,0) rectangle (7,1);
\draw(7,0) rectangle (8,2);
\end{tikzpicture}
\]
(``Tiling'' a board by dominos means covering
it by dominos in such a way that two dominos cannot have any overlap except
along their edges. The dominos should lie with their sides parallel to the
horizontal and vertical axes, and should be ``snapped to the
grid'' -- i.e., their edges should fall along the gridlines
that subdivide the board into $1 \times 1$-squares.)

\begin{enumerate}

\item[\textbf{(a)}] If we remove one of the four
corner cells from our board, then can the remaining
shape still be tiled with dominoes? (A \textquotedblleft
cell'' means a $1\times1$-square.)

\item[\textbf{(b)}] Consider two corner cells of the
board that lie on the same side (e.g., the southwestern
and the northwestern corners). If we remove these two
cells from the board, then can the remaining shape
still be tiled with dominoes?

\item[\textbf{(c)}] Now consider two opposite corner
cells of the board (e.g., the southwestern and the
northeastern corners). If we remove these two cells
from the board, then can the remaining shape still be
tiled with dominoes?

\end{enumerate}

\subsection{Solution}

...

%----------------------------------------------------------------------------------------
%	EXERCISE 3
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 3}

\subsection{Problem}

Define a sequence $\tup{a_0, a_1, a_2, \ldots}$ of
positive rational numbers recursively by setting
\begin{align*}
a_0 &= 1, \qquad
a_1 = 1, \qquad
a_2 = 1, \qquad \text{and} \\
a_n & = \dfrac{a_{n-1} a_{n-3}}{a_{n-2} + 1}
\qquad \text{for each } n \geq 3.
\end{align*}
Prove that $a_n$ is the reciprocal of a positive
integer for each $n \in \NN$.
(For instance, $a_8 = \dfrac{1}{448}$.)

\subsection{Solution}

...

%----------------------------------------------------------------------------------------
%	EXERCISE 4
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 4}

\subsection{Problem}

Let $n$ be a positive integer. Consider the $n-1$
fractions
$\dfrac{2}{1},\ \dfrac{3}{2},\ \dfrac{4}{3},\ \ldots,
\ \dfrac{n}{n-1}$
(that is, $\dfrac{k}{k-1}$ for all
$k \in \set{2, 3, \ldots, n}$).

\begin{enumerate}

\item[\textbf{(a)}] Prove that the product of
these $n-1$ fractions is $n$.

\item[\textbf{(b)}] For which $n$ is it possible
to invert some of these fractions so that the
product of the $n-1$ fractions (the inverted and
the non-inverted ones multiplied together)
becomes $1$ ?

(To ``invert'' a fraction means to swap its
numerator with its denominator. For instance, for
$n=4$, we have the $3$ fractions
$\dfrac{2}{1},\ \dfrac{3}{2},\ \dfrac{4}{3}$.
Inverting the first of them, we get the three
fractions
$\dfrac{1}{2},\ \dfrac{3}{2},\ \dfrac{4}{3}$,
whose product is
$\dfrac{1}{2}\cdot\dfrac{3}{2}\cdot\dfrac{4}{3} = 1$,
as desired.)

\end{enumerate}

\subsection{Solution}

...

%----------------------------------------------------------------------------------------
%	EXERCISE 5
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 5}

\subsection{Problem}

\begin{enumerate}

\item[\textbf{(a)}] Prove that
$\sin 1^\circ + \sin 2^\circ + \cdots + \sin 179^\circ
= \cot \tup{0.5^\circ}$.
(Recall that $\cot x := \dfrac{\cos x}{\sin x}$
for any angle $x$.)

\item[\textbf{(b)}] Prove that
$1 \sin 1^\circ + 2 \sin 2^\circ + \cdots + 179 \sin 179^\circ
= 90 \cot \tup{0.5^\circ}$.

\end{enumerate}

\subsection{Solution}

...

%----------------------------------------------------------------------------------------
%	EXERCISE 6
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 6}

\subsection{Problem}

Prove that for each $n \in \NN$, there exists a
permutation $\tup{p_1, p_2, \ldots, p_n}$ of the
$n$-tuple $\tup{1, 2, \ldots, n}$ with the property
that each partial sum $p_1 + p_2 + \cdots + p_k$
(with $k \in \set{1, 2, \ldots, n-1}$)
is divisible by $p_{k+1}$.
\medskip

[\textbf{Example:} For $n=7$, one such permutation is
$\tup{5,1,6,4,2,3,7}$.]

\subsection{Solution}

...


%----------------------------------------------------------------------------------------
%	EXERCISE 7
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 7}

\subsection{Problem}

Let $\delta$ be a positive real number. Let
$a_1, a_2, \ldots, a_n$ be $n$ real numbers such that
$n \geq 2$ and $a_1 + a_2 + \cdots + a_n = 0$ and
\[
\abs{a_i - a_{i+1}} \leq 2 \delta
\qquad \text{for all } i \in \set{1, 2, \ldots, n},
\]
where we let $a_{n+1}$ denote $a_1$.
Prove that there exist at least two numbers
$i \in \set{1, 2, \ldots, n}$ such that
$\abs{a_i} \leq \delta$.

\subsection{Solution}

...


%----------------------------------------------------------------------------------------
%	EXERCISE 8
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 8}

\subsection{Problem}

\begin{enumerate}

\item[\textbf{(a)}] Let $ABC$ be a triangle.
Prove the inequality
\[
\sin A + \sin B + \sin C \leq \dfrac{3\sqrt{3}}{2}.
\]
Here, the $A,B,C$ in the inequality denote the
angles of triangle $ABC$ (that is,
$A = \measuredangle CAB$ and so on).

\item[\textbf{(b)}] Is there an analogous inequality
for convex quadrilaterals? for convex $n$-gons?

\end{enumerate}

\subsection{Solution}

...


%----------------------------------------------------------------------------------------
%	EXERCISE 9
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 9}

\subsection{Problem}

Let $n$ be a positive integer. Consider an
$n \times n$-matrix $A$ with real entries. An entry
of $A$ will be called \emph{weird} if it is
simultaneously (strictly) greater than the average
of the entries in its column and (strictly) smaller
than the average of the entries in its row.
What is the largest possible number of weird
entries that $A$ can have?
\medskip

[\textbf{Remark:} Of course, the weirdness of an
entry depends not just on the entry itself but also
on its position in $A$. Thus, when we speak of weird
entries, we really mean weird cells.]

\subsection{Solution}

...


%----------------------------------------------------------------------------------------
%	EXERCISE 10
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 10}

\subsection{Problem}

Let $n > 1$ be a integer. Let $m$ be the smallest
positive integer such that $1 + 2 + \cdots + m$ is
divisible by $n$. (For example, if $n = 5$, then
$m = 4$, since $1 + 2 + 3 + 4 = 10$ is divisible by
$5$ whereas $1$ and $1 + 2$ and $1 + 2 + 3$ are not.)

Prove that $m > n$ if and only if $n$ is a power of $2$.

\subsection{Solution}

...



\horrule{0.3pt} \\[0.4cm]

\begin{thebibliography}{99999999}                                                                                         %

\end{thebibliography}

\end{document}

