\documentclass{article} \usepackage[margin=1in]{geometry} \usepackage[all]{xy} \usepackage{graphicx} \usepackage{enumerate} \usepackage{color} \usepackage{amssymb} \usepackage{amsmath} \usepackage{float} \usepackage{url} \usepackage{mathrsfs} \usepackage[vcentermath]{youngtab} \usepackage{framed} \usepackage{mathtools} \usepackage{tikz} \usepackage{tikz-cd} \usetikzlibrary{% matrix,% calc,% arrows% } \usepackage{enumerate} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\C}{\mathbb{C}} \newcommand{\F}{\mathbb{F}} \renewcommand{\H}{\mathbb{H}} \renewcommand{\P}{\mathbb{P}} \newcommand{\eps}{\varepsilon} \newcommand*{\todo}{\textcolor{red}} \newcommand*{\Hom}{\textnormal{Hom}} \newcommand{\Gr}{\operatorname{Gr}} \newcommand{\Aut}{\operatorname{Aut}} \newcommand{\End}{\operatorname{End}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\SL}{\operatorname{SL}} \newcommand{\id}{\textnormal{id}} \newcommand{\Perm}{\operatorname{Perm}} \newcommand{\Stab}{\operatorname{Stab}} \newcommand{\ob}{\operatorname{ob}} \renewcommand{\O}{\operatorname{O}} \newcommand{\U}{\operatorname{U}} \newcommand{\SU}{\operatorname{SU}} \newcommand{\SO}{\operatorname{SO}} \newcommand{\Fl}{\mathbb{F}\ell} \newcommand{\Spec}{\operatorname{Spec}} \newcommand{\mSpec}{\operatorname{mSpec}} \newcommand{\mProj}{\operatorname{mProj}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\p}{\mathfrak{p}} \newcommand{\rad}{\operatorname{rad}} \newcommand{\Log}{\operatorname{Log}} \newcommand{\csch}{\operatorname{csch}} \newcommand{\sech}{\operatorname{sech}} \newcommand{\A}{\mathcal{A}} \newcommand{\Int}{\operatorname{Int}} \newcommand{\EXT}{\operatorname{EXT}} \newcommand{\Ext}{\operatorname{Ext}} \newcommand{\im}{\operatorname{im}} \newcommand{\Mod}{\operatorname{Mod}} \newcommand{\spn}{\operatorname{span}} \newcommand{\disc}{\operatorname{disc}} \newcommand{\Sym}{\operatorname{Sym}} \newcommand{\coker}{\operatorname{coker}} \newcommand{\cI}{\mathcal{I}} \newcommand{\cC}{\mathcal{C}} \newcommand{\cD}{\mathcal{D}} \newcommand{\Tor}{\operatorname{Tor}} \newcommand{\Pf}{\operatorname{Pf}} \makeatletter \newcommand{\Wedge}{\@ifnextchar^\@Wedge{\@Wedge^{\,}}} \def\@Wedge^#1{\mathop{\bigwedge\nolimits^{\!#1}}} \makeatother \newcommand{\burl}[1]{\textcolor{blue}{\url{#1}}} \newenvironment{solution}{%\small% \begin{framed}\begin{trivlist} \item \textbf{Solution}. }{% \hspace*{\fill} \end{trivlist}\end{framed}}% \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{remark}[theorem]{Remark} \newtheorem{problem}{Problem} \newtheorem{exercise}[theorem]{Exercise} \newtheorem{innercustomprob}{Problem} \newenvironment{customprob}[1] {\renewcommand\theinnercustomprob{#1}\innercustomprob} {\endinnercustomprob} \newtheorem{innercustomprop}{Proposition} \newenvironment{customprop}[1] {\renewcommand\theinnercustomprop{#1}\innercustomprop} {\endinnercustomprop} \begin{document} \title{Group Assignment 5 Solutions} \date{} \author{} \maketitle \begin{enumerate} \item We prove the statement. Let $a, b \in \N$ and let $x_1, x_2, \dots, x_{ab+1}$ be a sequence of $ab+1$ distinct integers. Assume by means of contradition that there is no strictly increasing subsequence of length $a+1$ and no strictly decreasing subsequence of length $b+1$. To each $x_j$ in our original sequence, associate an ordered pair $(i_j, d_j)$ where $i_j$ is the length of the longest increasing subsequence starting with $x_j$ and $d_j$ is the length of the longest decreasing subsequence starting with $x_j$. Note that $i_k, d_k \geq 1$ for all $k$ (because there is always at least a length one increasing/decreasing subsquence starting at $x_j$ -- name just length one sequence $\{x_j\}$). Furthermore, by our assumption, each $i_j$ must be less than or equal to $a$ and each $d_j$ must be less than or equal to $b$ for all $j \in \{1, \dots, ab+1\}$. Therefore, looking at all possible ordered pairs $(i_j, d_j)$, the number of possible \emph{distinct} pairs is $a \cdot b$. But note that we have $ab + 1$ pairs (one associated to each $x_j$) and therefore by the pigeonhole principle, some pair must be the same. That is, there exist distinct $m, n$ such that $(i_m, d_m) = (i_n, d_n)$. We will show that this gives us a contradiction. Assume without loss of generality that $m < n$. Now consider $x_m$ and $x_n$. Since each of our original integers is distinct, either $x_m < x_n$ or $x_m > x_n$. First assume that $x_m < x_n$. Then we have an increasing subsequence of length $i_n$ which starts at $x_n$. However, we can take this exact subsequence and prepend $x_m$ to it, giving us a subsequence of length $x_n+1 = x_m+1$ starting at $x_m$. This contradicts the fact that $i_m$ is the length of the longest increasing subsequence starting with $x_m$. On the other hand, if $x_m > x_n$, we have a decreasing subsequence of length $d_n$ starting at $x_n$. Again, if we prepend $x_m$ to that sequence, we get a decreasing subsequence of length $d_n+1=d_m+1$ starting at $x_m$ -- a contradiction. Therefore, we have shown that we have a strictly increasing subsequence of length $a+1$ or a strictly decreasing subsequence of length $b+1$. \item \textbf{Theorem:} We show that for $x, y \in \R$, $n \in \Z^+$, \[ (x+y)^n = \sum_{j=0}^n \binom{n}{k} x^{n-k}y^k. \] \vspace{1em} \textbf{Proof:} Let $x, y \in \R$. Let $P(n)$ denote the statement that \[ (x+y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k}y^k. \] We will show that $P(n)$ is true for arbitrary $n$. \vspace{1em} \textbf{Base case:} If $n=1$, we have that \[ (x+y)^1 = x+y\] and \[ \sum_{k=0}^1 \binom{n}{k} x^{n-k}{y^k} = x+y.\] \vspace{1em} \textbf{Induction step:} Let $n \in \Z^+$. We assume that $P(n)$ is true and show that $P(n+1)$ is true. We have that \begin{align*} (x+y)^{n+1} &= (x+y)^n(x+y)\\ &= \left(\sum_{k=0}^n \binom{n}{k}x^{n-k}y^k\right)(x+y)\\ &= \sum_{k=0}^n \binom{n}{k}x^{n-k+1}y^k + \sum_{k=0}^n \binom{n}{k}x^{n-k}y^{k+1}\\ &= \binom{n}{0} x^{n+1} y^0 + \sum_{k=1}^n \binom{n}{k} x^{n-k+1} y^k + \sum_{k=0}^{n-1} \binom{n}{k} x^{n-k} y^{k+1} + \binom{n}{n} x^0 y^{n+1}. \end{align*} Now by Pascal's identity, grouping like terms in the middle two sums, the coefficient in front of $x^{n-k+1}y^k$ is \[ \binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k} \] and so after reindexing our sums, we have that \begin{align*} (x+y)^{n+1} &= \binom{n}{0} x^{n+1}y^0 + \sum_{k=1}^n \binom{n+1}{k} x^{(n+1)-k}y^k + \binom{n}{n} x^0 y^{n+1}. \end{align*} But note that $\binom{n}{0} = \binom{n+1}{0}$ and $\binom{n}{n} = \binom{n+1}{n+1}$ and thus we finally gett hat \[ (x+y)^{n+1} = \sum_{k=0}^{n+1} \binom{n+1}{k} x^{(n+1)-k}y^k\] as desired. \item Let's first consider Problem 1a. There are five possibilities, and for any one given possibility, there are two options: correct (that is, circled if it should be circled and not circled if shouldn't be) and incorrect (the opposite), where each one is equally likely. Therefore, the number of different ways to answer the question is $2^5 = 32$, which each one equally likely. There is exactly one way to answer the question correctly, which results in 4 points, so \[ P(4 \text{ pts}) = 1/32.\] The next highest point value is 2.5 points (so one thing incorrect). There are $\binom{5}{1} = 5$ different ways to choose the one incorrect options, giving that \[ P(2.5\text{ pts}) = 5/32.\] Next, getting two incorrect answers can occur in $\binom{5}{2} = 10$ different ways, giving that \[ P(1 \text{ pt}) = 10/32.\] All of the rest options result in $0$ points. (Note that it doesn't matter what the probability of 0 points is because we're looking for an expected value of points, so that probability will get multiplied by 0 anyway.) From this, we see that our expected number of points for problem 1a is $4 \cdot (1/32) + 2.5 \cdot (5/32) + 1 \cdot (10/32) \approx 0.828$. The other four parts of problem 1 also have 5 different possibilities to circle, so the expected number of points for each of those is the same as 1a. Thus, the expected number of points on problem 1 is $5 \cdot 0.828 = 4.14$. \vspace{1em} For Problem 2, there are three parts worth 2 points each, each with 4 possible options to circle. Therefore, there are $2^4 = 16$ possible answers for any given part. There is exactly one way to answer the question correctly, so \[ P(2 \text{ pts}) = 1/16.\] If there is one incorrect option, this results in 1 point off. This can happen in $\binom{4}{1} = 4$ ways, so \[ P(1 \text{ pt}) = 4/16.\] The rest of the answers result in 0 points. So the expected number of points for each part of problem 2 is $2 \cdot (1/16) + 1 \cdot (4/16) = 0.375$. Since there are three parts, this results in an expected value of $3 \cdot 0.375 = 1.125$ points. \vspace{1em} For problem 3, there are two possible answers to this question, depending on whether you assume that this test-taker circles only one answer for parts d and e or circles any number. Assuming only \emph{one} answer: For each of parts a, b, and c we have $2^3 = 8$ possible ways to circle, one of which results in 1 point (and the rest in 0). So for any given part, the expected number of points is $1/8$, resulting in $3/8$ points expected for the first three parts. For the last 2 parts, there are $3$ possible ways to circle, one of which results in one point, so for each part the expected number of points is $1/3$; the total expected points for parts d and e is $2/3$. Therefore, the total points for the problem is $3/8 + 2/3 \approx 1.042$. Assuming \emph{any number} of answers: As argued above, for any of the 5 parts the expected number of points is $1/8$, and so the expected number of points for the whole problem is $5/8$. \vspace{1em} Looking at problem 4, there were technically two correct (accepted) answers for part c. Depending on whether or not that was accounted for, we get different answers. Assuming \emph{only one} correct answer to part c: For parts a and b, there are $2^5 = 32$ possible ways to circle answers, one of which results in 2 points (and the rest in 0), so the expected number of points for each of these is $2/32$. For part c, there are $2^4 = 16$ possible ways to circle answers, one of which results in 2 point, so the expected number of points is $2/16$. Therefore, the total number of points is $4/32 + 2/16 = 0.25$. Assuming \emph{both} correct answers to part c: Parts a and b remain the same, but the expected points for part c is $2\cdot2/16$, giving a total expected value of $4/32 + 4/16 = 0.375$. \item First note that the total number of possible poker hands is $\binom{52}{5} = 2,598,960$. We count the number of ways to get a hand as good as or higher than three threes. \vspace{1em} \textbf{High 3 of a kind:} \[ \binom{12}{1}\binom{4}{3}\binom{12}{2}\binom{4}{1}\binom{4}{1} = 50,688\] \textbf{Straight (no straight flush or royal flush):} \[ \binom{10}{1}\binom{4}{1}^5 - \binom{10}{1}\binom{4}{1} = 10,200\] \textbf{Flush (no royal flush or straight flush):} \[ \binom{13}{5}\binom{4}{1} - \binom{10}{1}\binom{4}{1} = 5,108\] \textbf{Full House:} \[ \binom{13}{1}\binom{4}{3}\binom{12}{1}\binom{4}{2} = 3,744\] \textbf{Four of a kind:} \[ \binom{13}{1}\binom{4}{4}\binom{12}{1}\binom{4}{1} = 624\] \textbf{Straight flush (no royal flush):} \[ \binom{10}{1}\binom{4}{1} - \binom{4}{1} = 36\] \textbf{Royal flush:} \[ \binom{4}{1} = 4\] and therefore the probability is \[ \frac{ 50,688 + 10,200 + 5,108 + 3,744 + 624 + 36 + 4}{2,598,960} \approx 0.027.\] \end{enumerate} \end{document}