% 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}{6} % 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 2023:
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}

Recall the Euclidean algorithm discussed in Subsubsection 6.1.3.
Let $u$ and $v$ be two positive integers.
Prove that if we start the Euclidean algorithm in the state
$\tup{u, v}$,
then it will terminate after at most $\max \set{u, v}$ moves.

\subsection{Remark}

This is a sharp estimate, because if we start the Euclidean
algorithm in the state $\tup{n, 1}$, then it will take $n$ moves
to terminate:
\[
\tup{n, 1} \mapsto \tup{n-1, 1} \mapsto \tup{n-2, 1}
\mapsto \cdots \mapsto \tup{1, 1} \mapsto \tup{1, 0}
\qquad \tup{\text{or } \mapsto \tup{0, 1}}.
\]
On the other hand, the ``grown-up'' version of the Euclidean
algorithm, which uses division with remainder instead of
subtraction, terminates much faster: see, e.g., \cite{Epasin83}.

\subsection{Solution}

...

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

\section{Exercise 2}

\subsection{Problem}

Consider the process whose states are the $4$-tuples
$\tup{a, b, s, t} \in \set{1,2,3,\ldots}^4$ of positive
integers, and whose moves are
\begin{align*}
\tup{a, b, s, t}  &  \mapsto  \tup{a, b-a, s, t+s}
\qquad \text{if } b > a; \\
\tup{a, b, s, t}  &  \mapsto  \tup{a-b, b, s+t, t}
\qquad \text{if } a > b.
\end{align*}
Its end states are clearly the $4$-tuples
$\tup{a, b, s, t}$ with $a = b$.

Now, let $u$ and $v$ be two positive integers. We run
this process starting with the state $\tup{u, v, u, v}$.
Prove the following:

\begin{enumerate}

\item[\textbf{(a)}]
This process will eventually terminate.

\item[\textbf{(b)}]
The end state at which it terminates is a $4$-tuple
$\tup{g, g, s, t}$ with $g = \gcd \tup{u, v}$ and
$\dfrac{s+t}{2} = \lcm \tup{u, v}$.

\end{enumerate}

[\textbf{Example:} If $u=6$ and $v=9$, then the process
runs as follows:
\[
\tup{6, 9, 6, 9} \mapsto \tup{6, 3, 6, 15} \mapsto
\tup{3, 3, 21, 15} ,
\]
and indeed we have $3 = \gcd \tup{6, 9}$ and
$\dfrac{21+15}{2} = 18 = \lcm \tup{6, 9}$.]

\subsection{Solution}

...

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

\section{Exercise 3}

\subsection{Problem}

Consider the following variant of Exercise 6.2.1:
Chameleons can come in four colors, and change colors only
when three chameleons of pairwise different colors meet (in which
case they all take on the fourth color). (No more than three
chameleons meet at a time.)

Encode each state as a $4$-tuple $\tup{a, b, c, d}$, where $a$ is
the number of chameleons of the first color, and so on. Say that
a state $\tup{a, b, c, d}$ is \emph{winnable} if an appropriate
sequence of meetings can transform it into a state where all
chameleons have the same color.

\begin{enumerate}

\item[\textbf{(a)}]
Prove that if a state $\tup{a, b, c, d}$ is winnable, then (at
least) three of the integers $a, b, c, d$ are congruent modulo
$4$.

\item[\textbf{(b)}] Is the converse true?

\end{enumerate}

\subsection{Solution}

...

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

\section{Exercise 4}

\subsection{Problem}

Consider the following variant of Exercise 6.2.1:
We start with $a$ red, $b$ green and $c$ blue chameleons.
The rules of color change are the same as in Exercise 6.2.1,
but the goal we want to achieve is not that all chameleons
have the same color, but rather that the colors are
equidistributed (i.e., there are equally many red, green
and blue chameleons on the island).

Prove a simple necessary and sufficient criterion (in terms
of $a, b, c$) for this goal to be achievable.

\subsection{Solution}

...

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

\section{Exercise 5}

\subsection{Problem}

You have a bank account with $2023$ dollars. You can split a
bank account into two, but this operation costs you $1$ dollar in
fees. (Thus, you can split a bank account with $n$ dollars into two
bank accounts with $p$ and $q$ dollars each, where $n = p + q + 1$.)
Can you use a sequence of such operations to end up with all of your
accounts containing exactly $2$ dollars each?

\subsection{Solution}

...

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

\section{Exercise 6}

\subsection{Problem}

Consider Exercise 6.3.2 (the ``pentagon game''), but
now assume that the sum of all five integers is zero rather
than positive. Assume furthermore that not all five integers
are zero at the onset. Will the process go on forever, or
will it terminate?

\subsection{Solution}

...

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

\section{Exercise 7}

\subsection{Problem}

Four real numbers $a, b, c, d$ are written on a whiteboard.
Every hour, a ghost flies by and replaces them by the numbers
$a-b,\ b-c,\ c-d,\ d-a$. Prove that eventually, at least one of
the numbers will be too large (in absolute value) to fit on the
whiteboard, unless the original four numbers $a, b, c, d$ were
all equal.

\subsection{Solution}

...

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

\section{Exercise 8}

\subsection{Problem}

Consider a sequence $\tup{a_0, a_1, a_2, \ldots} $ of non-zero
reals that satisfies
\[
a_n^2 = 1 + a_{n-1} a_{n+1} \qquad \text{for each } n \geq 1.
\]
Prove that there exists a real number $\alpha$ such that
$a_{n+1} = \alpha a_n - a_{n-1}$ for all $n \geq 1$.

{\flushright(54th Putnam contest 1993, Problem A2)}

\subsection{Solution}

...

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

\section{Exercise 9}

\subsection{Problem}

Let $m$ be a positive integer. Consider the ritual described in
Exercise 6.4.1, but with $2^m$ points on the circle instead of $5$
(and thus $2^m$ integers instead of $5$).

Prove that after $2^m$ days, all the integers on the circle will
be even.

\subsection{Solution}

...

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

\section{Exercise 10}

\subsection{Problem}

Consider an $n$-tuple $\tup{a_1, a_2, \ldots, a_n}$ of
real numbers. We are allowed to make the following
three kinds of moves:

\begin{itemize}
\item \textbf{S-moves:} We pick two adjacent entries
$a_i$ and $a_{i+1}$ that are ``out of order'' (i.e.,
satisfy $a_i > a_{i+1}$), and swap them (i.e., replace
them by $a_{i+1}$ and $a_i$, respectively). This is
called an \emph{S-move}.

\item \textbf{L-moves:} We pick two adjacent entries
$a_i$ and $a_{i+1}$ that are ``out of order'' (i.e.,
satisfy $a_i > a_{i+1}$), and replace them by $a_{i+1}$
and $a_{i+1}$ (that is, we replace the larger entry by
the smaller one). This is called an \emph{L-move}.

\item \textbf{U-moves:} We pick two adjacent entries
$a_i$ and $a_{i+1}$ that are ``out of order'' (i.e.,
satisfy $a_i > a_{i+1}$), and replace them by $a_i$
and $a_i$ (that is, we replace the smaller entry by
the larger one). This is called a \emph{U-move}.
\end{itemize}

For instance,
$\tup{4,3,1,2} \mapsto \tup{3,4,1,2}$ is an
S-move,
$\tup{4,3,1,2} \mapsto \tup{3,3,1,2}$ is an
L-move, and
$\tup{4,3,1,2} \mapsto \tup{4,4,1,2}$ is a U-move.

\begin{enumerate}

\item[\textbf{(a)}]
Prove that if we keep applying S-moves and L-moves to our
$n$-tuple (sequentially), then we eventually end up with
a weakly increasing $n$-tuple (i.e., the process terminates).

\item[\textbf{(b)}] Is the same true if we allow all three
kinds of moves?

\end{enumerate}

\subsection{Solution}

...



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

\begin{thebibliography}{99999999}                                                                                         %

\bibitem[Epasin83]{Epasin83}%
\href{https://www.fq.math.ca/Scanned/23-2/epasinghe.pdf}{P. W. Epasinghe,
\textit{Euclid's Algorithm and the Fibonacci Numbers}, Fibonacci Quarterly 23
(\textbf{1985}), issue 2, pp. 177--179.}

\bibitem[Grinbe20]{20f}Darij Grinberg, \textit{Math 235: Mathematical Problem
Solving}, 10 August 2021. \newline
\url{https://www.cip.ifi.lmu.de/~grinberg/t/20f/mps.pdf}

\end{thebibliography}

\end{document}

