\( \def\bbN{{\mathbb N}} \def\bbQ{{\mathbb Q}} \def\bbR{{\mathbb R}} \def\bbZ{{\mathbb Z}} \)
© | Dror Bar-Natan: Classes: 2015-16: Math 475 - Problem Solving Seminar: (46) Next: Blackboards for Tuesday April 5
Previous: Blackboards for Wednesday March 31

Handout for April 5, "Consider Extreme Cases" and "Generalize"

Reading. Sections 1.11 and 1.12 of Larson's textbook.

Last Quiz. Thursday April 7, on this handout and those sections.

Evaluation Responses. 2/38 at 9:20AM on April 4. Now?

Problem 0 (Larson's 3.3.20, reworded). Prove that if $n>1$, the sum $1+\frac12+\frac13+\ldots+\frac1n$ is not an integer.
Hint. Multiply by $\operatorname{lcm}(1,2,\ldots,n)$ and consider the parity of the result.

Problem 1 (Larson's 1.11.1, hinted). Given a finite number of points in the plane, not all of them on the same line, prove that there is a straight line that passes through exactly two of them.
Hint. Consider the triangle with least height whose vertices.

Problem 2 (Larson's 1.11.2, reworded). Let $A$ be a set of $2n$ points in the plane, no three of them on the same line. Suppose that $n$ of them are coloured red and $n$ are coloured blue. Show that you can choose a pairing of the reds and the blues such the straight line segments between the pairs do not intersect.

Problem 3 (Larson's 1.11.3). In a party, no boy dances with every girl and each girl dances with at least one boy. Prove that there two couples $bg$ and $b'g'$ which dance, whereas $b$ does not dance with $g'$ and $g$ does not dance with $b'$.

Problem 4 (Larson's 1.11.5). Let $f(x)$ be a polynomial of degree $n$ with real coefficients and such that $f(x)\geq 0$ for every real $x$. Show that $f(x)+f'(x)+\ldots+f^{(n)}(x)\geq 0$ for every real $x$.

Problem 5 (useful in group theory). Say that a matrix $A$ is ``$\bbZ$-equivalent'' to a matrix $B$ if you can reach from $A$ to $B$ by a sequence of invertible row- and column-operations that involve only integer coefficients (namely, swap two rows, add an integer multiple of one row to another, negate one row, or the same with columns). Show that every matrix $A$ with integer entries is $\bbZ$-equivalent to a diagonal matrix.
Hint. Consider the least of all entries in any matrix $\bbZ$-equivalent to $A$, its row and its column.

Problem 6 (Larson's 1.11.7). Show that there exists a rational number $c/d$, with $d<100$, such that $\lfloor k\frac{c}{d}\rfloor = \lfloor k\frac{73}{100}\rfloor$ for $k=1,2,\ldots,99$.

Problem 7. Let $A$ be a subset of $[0,1]$ which is both open and closed, and assume that $0\in A$. Prove that also $1\in A$.

Problem 8 (From Larson's 1.12.1, 1.12.4, 5.1.9, 5.4.4). Evaluate the sum $\sum_{k=1}^\infty k^2/2^k$, and then also the sums
  1. $\displaystyle\sum_{k=1}^n k^2/2^k$.
  2. $\displaystyle\sum_{k=1}^n (2k+1)\binom{n}{k}$.
  3. $\displaystyle\sum_{k=1}^n k(k-1)\binom{n}{k}$.
  4. $\displaystyle\sum_{k=1}^n k^2\binom{n}{k}$.
  1. $\displaystyle\sum_{k=1}^n 3^k\binom{n}{k}$.
  2. $\displaystyle\sum_{k=1}^n \frac{1}{k+1}\binom{n}{k}$.
  3. $\displaystyle\sum_{k=1}^n \frac{(-1)^k}{k+1}\binom{n}{k}$.
  4. $\displaystyle\sum_{k=0}^\infty \frac{(k+1)^2}{k!}$.

Problem 9 (Larson's 4.1.4). Prove that none of the following integers is prime: \[ 1,\ 10001,\ 100010001,\ 1000100010001,\ \ldots \]

Problem 10 (Larson's 2.4.3, reworded). Let $S$ denote an $n\times n$ lattice of equally-spaced points, for $n\geq 3$. Prove that there exists a polygonal path made of $2n-2$ straight segments which passes through all $n^2$ points of $S$.