\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{tikz}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{wasysym}
\usepackage{easytable}
\usepackage{ytableau}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Monday, October 18, 2021 01:08:53}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{Language=American English}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\usetikzlibrary{arrows.meta}
\usetikzlibrary{chains}
\newcounter{exer}
\newcounter{exera}
\numberwithin{exer}{subsection}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[subsection]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{convention}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{question}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{warning}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\medskip \begin{small}}{\end{small} \medskip}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{question}[1][Question]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{warning}[1][Warning]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{teachingnote}[1][Teaching note]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\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}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newcommand\arxiv[1]{\href{http://www.arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\newenvironment{teachingnote}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\excludecomment{teachingnote}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\KK}{\mathbb{K}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\lf}[2]{#1^{\underline{#2}}}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}}
\newcommand{\are}{\ar@{-}}
\newcommand{\nnn}{\nonumber\\}
\newcommand{\sslash}{\mathbin{/\mkern-6mu/}}
\newcommand{\numboxed}[2]{\underbrace{\boxed{#1}}_{\text{box } #2}}
\newcommand{\ig}[2]{\includegraphics[scale=#1]{#2.png}}
\iffalse
\NOEXPAND{\today}{\today}
\NOEXPAND{\sslash}{\sslash}
\NOEXPAND{\numboxed}[2]{\numboxed}
\fi
\ihead{Math 235 Fall 2021, Worksheet A, version \today}
\ohead{page \thepage}
\cfoot{Darij Grinberg}
\begin{document}
\setcounter{section}{9}

\section{Math 235 Fall 2021, Worksheet A: assorted problems}

This is a selection of contest-type problems for discussion.

\begin{exercise}
\label{exe.A.e1}
(Stronger version of Putnam 2002 Problem A5)

Consider the sequence $\left(u_0, u_1, u_2, \ldots\right)$
of numbers defined recursively by
\begin{align*}
u_0 &= 1; \\
u_{2n} &= u_n + u_{n-1} \qquad \text{for all positive } n \in \NN; \\
u_{2n+1} &= u_n \qquad \text{for all } n \in \NN.
\end{align*}
(As we recall, $\NN = \set{0,1,2,\ldots}$.)
Prove that for each positive rational number $k$, there
is a unique $n \in \NN$ such that $u_n / u_{n+1} = k$.
\end{exercise}

\begin{exercise}
\label{exe.A.e2}
\textbf{(a)}
For which nonnegative integers $n$ is the polynomial
$x^n + 1$ a multiple of the polynomial $x + 1$ ? \medskip

\textbf{(b)}
For which nonnegative integers $n$ is the polynomial
$x^{2n} + x^n + 1$ a multiple of the polynomial $x^2 + x + 1$ ?
\medskip

\textbf{(c)}
Fix a positive integer $m$.
For which nonnegative integers $n$ is the polynomial
$x^{\tup{m-1}n} + x^{\tup{m-2}n} + \cdots + x^n + 1$
a multiple of the polynomial
$x^{m-1} + x^{m-2} + \cdots + x + 1$ ?
\end{exercise}

\begin{exercise}
\label{exe.A.e3}
Let $n \in \NN$. Assume that the set $\set{1, 2, \ldots, 2n}$
is partitioned into two disjoint subsets $A$ and $B$, each of
which has size $n$.

Let $a_1, a_2, \ldots, a_n$ be the elements of $A$ in
increasing order (that is, $a_1 < a_2 < \cdots < a_n$).

Let $b_1, b_2, \ldots, b_n$ be the elements of $B$ in
decreasing order (that is, $b_1 > b_2 > \cdots > b_n$).

Prove that
\[
\abs{a_1 - b_1} + \abs{a_2 - b_2} + \cdots + \abs{a_n - b_n} = n^2 .
\]
\end{exercise}

\begin{exercise}
\label{exe.A.e4}
Let $a, b, c, d$ be four integers such that
$ab = cd$.
Prove that there exist four integers $x, y, z, w$
such that
\[
a=xy,\ \ \ \ \ \ \ \ \ \ b=zw,\ \ \ \ \ \ \ \ \ \ c=xz,\ \ \ \ \ \ \ \ \ \ d=yw.
\]
\end{exercise}

\begin{exercise}
\label{exe.A.e5}
Fix an $n \in \NN$.
Let $\ive{n}$ be the set $\set{1, 2, \ldots, n}$.
\medskip

The \emph{top-led shuffle} is the operation that
takes an $n$-tuple $\tup{a_1, a_2, \ldots, a_n}$
of elements of $\ive{n}$ and changes it by
moving its first entry $a_1$ to the $a_i$-th
position (i.e., it replaces the $n$-tuple by
$\tup{a_2, a_3, \ldots, a_k, a_1, a_{k+1}, a_{k+2}, \ldots, a_n}$,
where $k = a_1$).
In other words, if we view the $n$-tuple
$\tup{a_1, a_2, \ldots, a_n}$ as a deck of $n$ cards
(numbered $a_1, a_2, \ldots, a_n$ from top to bottom),
then the top-led shuffle moves the topmost card to
the position indicated by the number on the card
(so, e.g., if the number on the card is $3$, then it
moves this card to the $3$-rd position).

[\textbf{Example:} The top-led shuffle turns
$\tup{4,1,5,2,3}$ into $\tup{1,5,2,4,3}$.]
\medskip

Start with some $n$-tuple $\tup{a_1, a_2, \ldots, a_n}$
of elements of $\ive{n}$ that contains each $i \in \ive{n}$
exactly once (i.e., start with a permutation of the
list $\tup{1, 2, \ldots, n}$),
and apply the top-led shuffle to it over and over.

Prove that eventually, this $n$-tuple will stabilize
(i.e., will no longer change under top-led shuffles).
\medskip

[\textbf{Remark:} In contrast, if we start with an
arbitrary $n$-tuple $\tup{a_1, a_2, \ldots, a_n}$
of elements of $\ive{n}$, then the top-led shuffle might
run in circles rather than stabilizing. For an example,
try $n = 4$ and $\tup{a_1, a_2, \ldots, a_n} = \tup{2,3,3,1}$.]
\end{exercise}

\begin{exercise}
\label{exe.A.e6}
Let $n \in \NN$.
Prove that $\floor{2 + \sqrt{3}}^n$ is odd.
(Here, for any given real $x$, the notation $\floor{x}$
stands for the largest integer that is $\leq x$.)
\end{exercise}

\end{document}