% 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{\ceil}[1]{\left\lceil #1 \right\rceil}
% $\ceil{...}$ compiles to |°...°| (ceiling 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}{2} % 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 2021:
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 $S$ be a $10$-element subset of the set
$\set{1, 2, \ldots, 100}$.
Prove that there exist two disjoint nonempty subsets
$A$ and $B$ of $S$ such that
$\sum_{a\in A} a = \sum_{b\in B} b$.
(Note that $A$ and $B$ are allowed to have any
positive sizes, including $1$.)

[\textbf{Example:} If $S = \set{3,9,13,19,26,60,74,80,84,94}$, then
$\sum_{a\in A} a = \sum_{b\in B} b$ is satisfied for
$A = \set{3,9,94}$ and $B = \set{26,80}$
(as well as for various other choices).]

\subsection{Solution}

...

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

\section{Exercise 2}

\subsection{Problem}

A number of people have been settled in $n$ apartments
$B_1, B_2, \ldots, B_n$ (with each person settled in exactly one
apartment). (Roommates are allowed.)
Now, all these people are removed from their apartments and
resettled in $n+1$ new apartments $C_1, C_2, \ldots, C_{n+1}$
in such a way that none of these $n+1$ new apartments stays empty.

A person is said to have \emph{gained space} if he has fewer
roommates after the resettlement than he used to have before.

Prove that at least two people have gained space.

\subsection{Solution}

...

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

\section{Exercise 3}

\subsection{Problem}

Consider any six points on the circumference of a circle
with radius $1$.
Prove that some two of these six points have distance $\leq1$.

\subsection{Solution}

...

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

\section{Exercise 4}

\subsection{Problem}

Let $N$ be an $n$-element set with $n > 0$.
Let $A_1, A_2, \ldots, A_q$ be finitely many $2$-element
subsets of $N$. Let $m = \ceil{\dfrac{2q}{n}}$. Prove that
we can find a strictly increasing sequence
$\tup{ i_1 < i_2 < \cdots < i_m }$ of $m$
elements of $\set{1, 2, \ldots, q}$ such that
\[
\abs{ A_{i_j} \cap A_{i_{j+1}} } \geq 1
\qquad \text{for each } j \in \set{1,2,\ldots,m-1}.
\]


[\textbf{Example:} Let $n = 5$ and $N = \set{1,2,3,4,5}$ and
$q = 6$ and
\begin{align*}
A_1 &= \set{1,2}, \qquad
A_2  = \set{3,5}, \qquad
A_3  = \set{1,4}, \\
A_4 &= \set{2,3}, \qquad
A_5  = \set{3,5}, \qquad
A_6  = \set{4,5}.
\end{align*}
We have
$m = \ceil{\dfrac{2q}{n}} = \ceil{\dfrac{2 \cdot 6}{5}} = 3$.
Thus, the exercise claims that there exists a strictly
increasing sequence $\tup{i_1 < i_2 < i_3}$ of $3$ elements of
$\set{1,2,3,4,5,6}$ such that
$\abs{A_{i_1} \cap A_{i_2}} \geq 1$
and $\abs{A_{i_2} \cap A_{i_3}} \geq 1$.
And indeed, we can pick $i_1 = 1$ and $i_2 = 3$ and
$i_3 = 6$ for example.]

\subsection{Solution}

...

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

\section{Exercise 5}

\subsection{Problem}

Let $A$ be a rectangular matrix with real entries. Assume
that the entries in each \textbf{row} of $A$ are weakly increasing from left
to right. Now we sort the entries in each \textbf{column} of $A$ so that they
become weakly increasing from top to bottom. (Each entry stays within its
column.) Thus, we obtain a new matrix $B$. Prove that the entries in each
\textbf{row} of $B$ are still weakly increasing from left to right.
\medskip

[\textbf{Example:} If $A = \begin{pmatrix}
1 & 3 & 6\\
2 & 2 & 5\\
1 & 2 & 3
\end{pmatrix}$, then $B = \begin{pmatrix}
1 & 2 & 3\\
1 & 2 & 5\\
2 & 3 & 6
\end{pmatrix}$.]

\subsection{Solution}

...

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

\section{Exercise 6}

\subsection{Problem}

Let $\mathbf{q} = \tup{q_1, q_2, q_3, \ldots}$
be a sequence of positive integers that is weakly increasing (that is, we have
$q_1 \leq q_2 \leq q_3 \leq \cdots$) and unbounded from above (that is, for
each positive integer $N$, there exists some $i \geq 1$ such that $q_i \geq N$).

For each positive integer $k$, let $t\tup{k}$ be the number of
entries of $\mathbf{q}$ that do not exceed $k$ (that is, the number of all
positive integers $i$ such that $q_i \leq k$).

Prove that the two sets
\[
Q := \set{q_n+n-1 \ \mid\ n \text{ is a positive integer}}
   = \set{q_1+0,\ \ q_2+1,\ \ q_3+2,\ \ \ldots}
\]
and
\[
T := \set{t\tup{n}+n \ \mid\ n\text{ is a positive integer}}
   = \set{t\tup{1}+1,\ t\tup{ 2}+2,\ t\tup{3}+3,\ \ldots}
\]
are disjoint and their union is $\set{1,2,3,\ldots}$. \medskip

[\textbf{Example:} If $q_i = i$ for each $i$, then $t\tup{k} = k$ for
each $k$, and we have
\[
Q = \set{\text{odd positive integers}} \qquad \text{and} \qquad
T = \set{\text{even positive integers}} .
\]

If $q_i = pi$ for each $i$ for some fixed positive integer $p$, then
$t\tup{k} = \floor{\dfrac{k}{p}}$ for each $k$, and we have
\[
Q = \set{\text{positive integers that leave the remainder } p
         \text{ when divided by } p+1}
\]
and
\[
T = \set{\text{all other positive integers}},
\]
although this takes some moments to convince yourself of.

If $q_i = i^2$ for each $i$, then $t\tup{k} = \floor{\sqrt k}$
for each $k$, and we have
\[
Q = \set{n^2+n-1\ \mid\ n\text{ is a positive integer}} = \set{
1,5,11,19,\ldots}
\]
and
\[
T = \set{\floor{\sqrt n} + n \ \mid\ n
             \text{ is a positive integer}}
  = \set{2,3,4,6,7,\ldots}.
\]

Many other examples can be constructed (and have, in fact,
appeared on contests!).]

\subsection{Solution}

...



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

\begin{thebibliography}{99999999}                                                                                         %

\end{thebibliography}

\end{document}

