% 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}{\mathbbn} % 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{\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 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}

Consider the same game as in Exercise 9.1.2 on Worksheet 9,
but with a minor difference: Now, each player is allowed to
blow out $1$, $2$ or $4$ candles (rather than
$k \in \set{1,2,3,4,5}$ candles).

\begin{enumerate}

\item[\textbf{(a)}] Same question as before: Who wins
(depending on $n$), assuming optimal play?

\item[\textbf{(b)}] What if, instead, each player can blow
out $2$ or $3$ candles? Blowing out the second-to-last
candle also counts as winning here (since it leaves the
next player with no possible moves).

\item[\textbf{(c)}] Generalize part \textbf{(b)}: Fix an
integer $m > 2$. Assume that each player can blow out an
arbitrary number $k \in \set{2, 3, \ldots, m-1}$ of
candles. Who wins?

\end{enumerate}

\subsection{Solution}

...

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

\section{Exercise 2}

\subsection{Problem}

Let $A$ and $B$ be two $n \times n$-matrices with complex
entries such that $AB + A + B = 0$. Prove that $BA + B + A = 0$ as
well.

\subsection{Hint}

One of the many facets of the infamous
\href{https://en.wikipedia.org/wiki/Invertible_matrix#The_invertible_matrix_theorem}{Invertible
Matrix Theorem} says the following: If $X$ and $Y$ are two
$n \times n$-matrices that satisfy $XY = I_n$ (where $I_n$
is the $n \times n$ identity matrix), then $YX = I_n$ as well.

\subsection{Solution}

...

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

\section{Exercise 3}

\subsection{Problem}

Let $n$ be a positive integer. Consider the $2^n$ many
$n$-bitstrings (see Exercise 9.1.3 for their definition).
Assume that $2^{n-1}$ of these $2^n$ bitstrings have been
colored white (arbitrarily), while the remaining $2^{n-1}$
have been colored black.
Prove that there exist at least $2^{n-1}$ pairs $\tup{w, b}$,
where $w$ is a white $n$-bitstring, where $b$ is a black
$n$-bitstring, and where $w$ and $b$ differ in exactly
one position. \medskip

[\textbf{Example:} The two $4$-bitstrings $\tup{ 0,1,0,0 }$
and $\tup{ 0,1,1,0 }$ differ in exactly one position (the
third one).]

\subsection{Solution}

...

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

\section{Exercise 4}

\subsection{Problem}

Let $a, b, c$ be three positive reals satisfying
$a^2 + b^2 + c^2 = 1$. Show that
$\dfrac{bc}{a} + \dfrac{ca}{b} + \dfrac{ab}{c} \geq \sqrt{3}$.

% \qquad \qquad (BWM Germany 2019, 2nd round, problem 2)

\subsection{Solution}

...

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

\section{Exercise 5}

\subsection{Problem}

Let $n$ be a positive integer such that $n \equiv -1 \mod 12$.
Let $s$ be the sum of all positive divisors of $n$.
Prove that $12 \mid s$.

\subsection{Solution}

...

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

\section{Exercise 6}

\subsection{Problem}

\newcommand{\god}{\operatorname{god}} % This introduces the shorthand \god.

For each positive integer $n$, let $\god \tup{n}$ denote the
greatest odd divisor of $n$. For instance, $\god \tup{24} = 3$
and $\god \tup{25} = 25$ and $\god \tup{30} = 15$.

Given two positive integers $a$ and $b$. We define a sequence
$\tup{ x_1, x_2, x_3, \ldots }$ of positive integers
recursively by setting $x_1 = a$ and $x_2 = b$ and
\[
x_n = \god \tup{x_{n-1} + x_{n-2}}
\qquad \text{for all }n \geq 3.
\]

Prove that all entries of this sequence from a certain point
on are equal to $\god \tup{ \gcd\tup{a, b} }$. In other
words, prove that there exists a $k \geq 1$ such that
$x_k = x_{k+1} = x_{k+2} = \cdots = \god \tup{ \gcd\tup{a, b} }$.

% \qquad \qquad (Tournament of Towns 30.6.3, by G. Galperin)

\subsection{Solution}

...

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

\section{Exercise 7}

\subsection{Problem}

Let $p$ and $q$ be two coprime positive integers.
Let $s = p+q$.

\begin{enumerate}

\item[\textbf{(a)}] Prove that
$\set{ \tup{ip} \% s\ \mid \ i\in \set{1, 2, \ldots, s-1} }
= \set{1, 2, \ldots, s-1}$.
(That is, the $s-1$ remainders $\tup{1p} \% s,\ \tup{2p} \% s,
\ \ldots,\ \tup{\tup{s-1}p} \% s$
are just the $s-1$ numbers $1, 2, \ldots, s-1$ in some order.)

\item[\textbf{(b)}] Let
$\mathbf{a} = \tup{a_1, a_2, \ldots, a_{s-1}}$ be an
$\tup{s-1}$-tuple of arbitrary objects (e.g., numbers).
Given an integer $d \in \set{1, 2, \ldots, s-1}$, we say that
$\mathbf{a}$ is \emph{$d$-periodic} if each \newline
$i \in \set{1, 2, \ldots, s-1-d}$ satisfies $a_i = a_{i+d}$.

Assume that $\mathbf{a}$ is both $p$-periodic and $q$-periodic.
Prove that $\mathbf{a}$ is $1$-periodic (i.e., we have
$a_1 = a_2 = \cdots = a_{s-1}$).

\item[\textbf{(c)}] Generalize part \textbf{(b)}:
Let $\mathbf{a} = \tup{a_1, a_2, \ldots, a_k}$ be a $k$-tuple
of arbitrary objects, where $k \geq s-1$. Given an integer
$d \in \set{1, 2, \ldots, k}$, we say that $\mathbf{a}$ is
\emph{$d$-periodic} if each $i \in \set{1, 2, \ldots, k-d}$
satisfies $a_i = a_{i+d}$.

Assume that $\mathbf{a}$ is both $p$-periodic and $q$-periodic.
Prove that $\mathbf{a}$ is $1$-periodic (i.e., we have
$a_1 = a_2 = \cdots = a_k$).

\end{enumerate}

\subsection{Solution}

...

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

\section{Exercise 8}

\subsection{Problem}

Let $a_1, a_2, \ldots, a_n$ be $n$ integers. A pair
$\tup{i, j}$ of integers satisfying $1 \leq i < j \leq n$ will
be called

\begin{itemize}

\item an \emph{odd inversion} if $a_i$ is odd, $a_j$ is even,
and $j-i$ is odd;

\item an \emph{even inversion} if $a_i$ is odd, $a_j$ is even,
and $j-i$ is even.

\end{itemize}

Prove that the number of odd inversions is at least as large
as the number of even inversions.

% \qquad \qquad (Tournament of Towns 30.6.4, by V. Yassinski)

\subsection{Solution}

...

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

\section{Exercise 9}

\subsection{Problem}

We write the numbers $1, 2, \ldots, n^2$ into the $n^2$ cells
of an $n \times n$-chessboard (where $n > 1$).
(Each number goes into exactly one cell.)

Prove that we can find two adjacent cells of this chessboard in
which the two numbers differ by more than $n$. Here, ``adjacent''
means ``have an edge or a vertex in common'' (so a cell can have
up to $8$ other cells adjacent to it).

% \qquad \qquad (Tournament of Towns 12.5, by N. Sedrakyan)

\subsection{Solution}

...

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

\section{Exercise 10}

\subsection{Problem}

Continue with the notations of Exercise 9.1.3. Recall also
the Fibonacci sequence $\tup{f_0, f_1, f_2, \ldots}$, defined by
$f_0 = 0$ and $f_1 = 1$ and $f_n = f_{n-1} + f_{n-2}$ for each
$n \geq 2$.

Prove that the total number of $1$'s summed over all lacunar
$n$-bitstrings is
\[
\dfrac{n f_{n+1} + 2 \tup{n+1} f_n}{5}.
\]

\subsection{Solution}

...



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

\begin{thebibliography}{99999999}                                                                                         %

\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}

