% 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{\Fix}{\operatorname{Fix}} % set of fixed points
\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}{9} % 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 2020:
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.

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

\section{Exercise 1}

\subsection{Problem}

Let $n$ and $d$ be two positive integers.

An $n$-tuple $\tup{x_1, x_2, \ldots, x_n} \in \ive{d}^n$
will be called \textit{first-even} if its first entry $x_1$
occurs in it an even number of times (i.e., the number of
$i \in \ive{n}$ satisfying $x_i = x_1$ is even).
(For example, the $3$-tuples $\tup{1, 5, 1}$ and
$\tup{2, 2, 3}$ are first-even, while the $3$-tuple
$\tup{4, 1, 1}$ is not.)

Compute the \# of first-even $n$-tuples in $\ive{d}^n$.

\subsection{Solution}

...

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

\section{Exercise 2}

\subsection{Problem}

Let $n \in \NN$ and $p \in \ZZ$.
Prove that
\[
\sum_{k=0}^n \tup{-1}^k \dbinom{n}{k} \dbinom{2n-2k}{n+p}
= 2^{n-p} \dbinom{n}{p}.
\]

\subsection{Solution}

...

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

\section{Exercise 3}

\subsection{Problem}

Let $n$ be a positive integer. Prove that
\[
\sum_{i=0}^{n-1}
\dfrac{\tup{-1}^{i}}{n-i} \dbinom{n-i}{i}
= \dfrac{1}{n} \tup{-1}^{\tup{n+1}//3}
   \tup{ 1 + \ive{3 \mid n} }.
\]

\subsection{Solution}

...

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

\section{Exercise 4}

\subsection{Problem}

A chocolate bar has the shape of an $m \times n$-rectangle
(subdivided into little $1 \times 1$-squares by horizontal and
vertical lines, in case your eating habits are too healthy).
For example, if $m = 2$ and $n = 3$, then it looks like this:
\[
\begin{tikzpicture}[scale=0.5]
\draw[step=1cm,thick] (0, 0) grid (2, 3);
\end{tikzpicture}
\]
In one move, you can break a chocolate bar into two by splitting it along one
of the (horizontal or vertical) lines that divide it (unless it is already a
$1\times1$-square). For example:
\begin{align*}
\begin{array}[c]{c}
\begin{tikzpicture}[scale=0.5]
\draw[step=1cm,thick] (0, 0) grid (2, 3);
\end{tikzpicture}
\end{array}
\ \  &  \overset{\text{move}}{\longrightarrow}\ \
\begin{array}[c]{c}
\begin{tikzpicture}[scale=0.5]
\draw[step=1cm,thick] (0, 0) grid (2, 1);
\end{tikzpicture}
\\
\begin{tikzpicture}[scale=0.5]
\draw[step=1cm,thick] (0, 0) grid (2, 2);
\end{tikzpicture}
\end{array}
\ \ \overset{\text{move}}{\longrightarrow}\ \
\begin{array}[c]{c}
\begin{tikzpicture}[scale=0.5]
\draw[step=1cm,thick] (0, 0) grid (1, 1);
\end{tikzpicture}
\ \
\begin{tikzpicture}[scale=0.5]
\draw[step=1cm,thick] (0, 0) grid (1, 1);
\end{tikzpicture}
\\
\begin{tikzpicture}[scale=0.5]
\draw[step=1cm,thick] (0, 0) grid (2, 2);
\end{tikzpicture}
\end{array}
\ \ \overset{\text{move}}{\longrightarrow}\ \
\begin{array}[c]{c}
\begin{tikzpicture}[scale=0.5]
\draw[step=1cm,thick] (0, 0) grid (1, 1);
\end{tikzpicture}
\ \
\begin{tikzpicture}[scale=0.5]
\draw[step=1cm,thick] (0, 0) grid (1, 1);
\end{tikzpicture}
\\
\begin{tikzpicture}[scale=0.5]
\draw[step=1cm,thick] (0, 0) grid (1, 2);
\end{tikzpicture}
\ \
\begin{tikzpicture}[scale=0.5]
\draw[step=1cm,thick] (0, 0) grid (1, 2);
\end{tikzpicture}
\end{array}
\\
& \\
& \\
&  \overset{\text{move}}{\longrightarrow}\ \
\begin{array}[c]{c}
\begin{tikzpicture}[scale=0.5]
\draw[step=1cm,thick] (0, 0) grid (1, 1);
\end{tikzpicture}
\ \
\begin{tikzpicture}[scale=0.5]
\draw[step=1cm,thick] (0, 0) grid (1, 1);
\end{tikzpicture}
\\
\begin{tikzpicture}[scale=0.5]
\draw[step=1cm,thick] (0, 0) rectangle (1, 1);
\draw[step=1cm,thick] (0, 1.5) rectangle (1, 2.5);
\end{tikzpicture}
\ \
\begin{tikzpicture}[scale=0.5]
\draw[step=1cm,thick] (0, 0) grid (1, 2);
\end{tikzpicture}
\end{array}
\ \ \overset{\text{move}}{\longrightarrow}\ \
\begin{array}[c]{c}
\begin{tikzpicture}[scale=0.5]
\draw[step=1cm,thick] (0, 0) grid (1, 1);
\end{tikzpicture}
\ \
\begin{tikzpicture}[scale=0.5]
\draw[step=1cm,thick] (0, 0) grid (1, 1);
\end{tikzpicture}
\\
\begin{tikzpicture}[scale=0.5]
\draw[step=1cm,thick] (0, 0) grid (1, 1);
\end{tikzpicture}
\ \
\begin{tikzpicture}[scale=0.5]
\draw[step=1cm,thick] (0, 0) grid (1, 1);
\end{tikzpicture}
\\
\begin{tikzpicture}[scale=0.5]
\draw[step=1cm,thick] (0, 0) grid (1, 1);
\end{tikzpicture}
\ \
\begin{tikzpicture}[scale=0.5]
\draw[step=1cm,thick] (0, 0) grid (1, 1);
\end{tikzpicture}
\end{array}
\ \ .
\end{align*}

\begin{enumerate}

\item[\textbf{(a)}]
What is the smallest number of moves necessary
to break up the entire bar into $1 \times 1$-squares?

\item[\textbf{(b)}]
What is the largest number of moves necessary
to break up the entire bar into $1 \times 1$-squares?

\end{enumerate}

\subsection{Solution}

...

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

\section{Exercise 5}

\subsection{Problem}

A circle is split into $6$ sectors, and a
number has been written in each sector. These numbers are
$1, 0, 1, 0, 0, 0$ in clockwise order, as shown in the
following picture:
\[
\begin{tikzpicture}[scale=2.5]
\coordinate(a) at ({cos(0)}, {sin(0)}) {};
\coordinate(b) at ({cos(360/6)}, {sin(360/6)}) {};
\coordinate(c) at ({cos(2*360/6)}, {sin(2*360/6)}) {};
\coordinate(d) at ({cos(3*360/6)}, {sin(3*360/6)}) {};
\coordinate(e) at ({cos(4*360/6)}, {sin(4*360/6)}) {};
\coordinate(f) at ({cos(5*360/6)}, {sin(5*360/6)}) {};
\draw(d) -- (a);
\draw(e) -- (b);
\draw(f) -- (c);
\node at (-0.5, 0.3) {$1$};
\node at (0, 0.6) {$0$};
\node at (0.5, 0.3) {$1$};
\node at (0.5, -0.3) {$0$};
\node at (0, -0.6) {$0$};
\node at (-0.5, -0.3) {$0$};
\draw(0,0) circle [radius=1];
\end{tikzpicture}
\]
In one move, you can add $1$ to any two numbers written
in adjacent sectors.

Can you ever ensure that all six sectors have the same
number written in them?

\subsection{Solution}

...

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

\section{Exercise 6}

\subsection{Problem}

Fix a positive integer $n$. Consider $n$ chips placed in
a heap. In a move, you are allowed to split a heap $H$ of
chips into two smaller heaps $H_1$ and $H_2$; when doing
so, you gain $\abs{H_1} \cdot \abs{H_2}$ cents. (We treat
heaps as sets of chips; thus, $\abs{H_1}$ is the \# of
chips in heap $H_1$.) After sufficiently many moves, you
are left with $n$ heaps, each containing exactly one chip.
What is the maximum number of cents you can have made by
that moment?

\subsection{Solution}

...

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

\section{Exercise 7}

\subsection{Problem}

Fix two positive integers $a$ and $b$. Consider $a+b$
bowls, numbered $1,2,\ldots,a+b$. Initially, each of
the bowls $1, 2, \ldots, a$ contains an apple, and
each of the bowls $a+1, a+2, \ldots, a+b$ contains a
pear.
A \textit{move} consists of picking two numbers
$i, j \in \ive{a + b}$ satisfying $i < a + b$ and
$j > 1$ and $i \equiv j \mod 2$, and moving an
apple from bowl $i$ to bowl $i+1$ and a pear from
bowl $j$ to bowl $j-1$. (We assume that these fruits
do exist in these bowls; otherwise, the move cannot
be made. It is allowed for several fruits to lie in
one bowl at the same time.)

The goal is to end up with each of the bowls
$1, 2, \ldots, b$ containing a pear and each of the
bowls $b+1, b+2, \ldots, b+a$ containing an apple.
Show that this goal can be reached if and only if
the product $ab$ is even.

\subsection{Solution}

...

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

\section{Exercise 8}

\subsection{Problem}

Consider a hotel with an infinite number of rooms,
arranged sequentially on the ground floor. The
rooms are labelled by integers $i \in \ZZ$, with
room $i$ being adjacent to rooms $i-1$ and $i+1$.
A finite number of violinists are staying in the
hotel (it is possible for two violinists to be
staying in the same room).
Each night, two violinists staying in the same
room decide they cannot stand each other's noise,
and move to the two adjacent rooms (i.e., if they
were in room $i$, they move to rooms $i-1$ and
$i+1$). This keeps happening for as long as
there are two violinists staying in the same
room.

Prove that this moving will stop after a finite
number of days (i.e., there will be a day when no
two violinists share a room any more).

\subsection{Solution}

...

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

\section{Exercise 9}

\subsection{Problem}

Define a sequence $\tup{t_0, t_1, t_2, \ldots}$ of
positive rational numbers recursively by setting
\[
t_n = 1 \qquad \text{for each } n < 4
\]
and
\[
t_n = \dfrac{1 + t_{n-1}t_{n-3}}{t_{n-4}} \qquad
\text{for each } n \geq 4.
\]

Prove that $t_n$ is a positive integer for each
integer $n \geq 0$.

\subsection{Solution}

...

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

\section{Exercise 10}

\subsection{Problem}

Let $q \in \NN$.
Define a sequence $\tup{t_0, t_1, t_2, \ldots}$
of positive rational numbers recursively by setting
\[
t_n = 1 \qquad \text{for each } n < 3
\]
and
\[
t_n = \dfrac{t_{n-1}^2 + q t_{n-1} t_{n-2} + t_{n-2}^2}{t_{n-3}}
 \qquad \text{for each } n \geq 3.
\]
Prove that $t_n$ is a positive integer for each integer
$n \geq 0$.

\subsection{Solution}

...


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

\begin{thebibliography}{99999999}                                                                                         %

\end{thebibliography}

\end{document}

