Jay's got Random Problems
Short problems in math/stat/prob

These are some small problems/puzzles I've created, aimed roughly at the level of the Problems sections of publications like the AMS Monthly, Mathematics Magazine, and the College Mathematics Journal, or easier. Let me know what you think, especially if you find a tidier solution than the one I've given.

Problem 4. A symmetric inequality
Prove -- without induction -- that for all positive integers \(m\) and \(n\), \[ (1-1/2^n)^m +(1-1/2^m)^n \ge 1.\]
Solution
Multiplying through by the number \(2^{mn}\) of \(m\times n\) matrices with \(0/1\) entries, the desired inequality is \[ (2^m-1 )^n+ (2^n-1 )^m\ge 2^{mn},\] or equivalently \[[2^{mn}-(2^m-1 )^n]+ [2^{mn}-(2^n-1 )^m]\le 2^{mn}.\] The first quantity in square brackets is the number of such matrices with a column of all \(0\)'s, and the second quantity is the number with a row of all \(1\)'s. Since no matrix can have both, these sets are disjoint and thus their sum is no larger than the total number \(2^{mn}\).
Problem 3. A coin game
Consider the following game: You flip a fair coin repeatedly until the \(r\)th head (\(r\ge 1\)). If this occurs on or before the \(10\)th flip, you receive \(2^x\) dollars, where \(x\) is the number of flips; otherwise you receive nothing. Suppose you were given the opportunity to play this game and even allowed to choose \(r\). How should you do so to maximize your expected winnings?

Solution
The probability that the \(r\)th head occurs on flip \(x\ge r\) is \[{x-1\choose r-1}(1/2)^x,\] thus your expected winnings are \[\sum_{x=r}^{10}2^x {x-1\choose r-1}(1/2)^x = \sum_{x=r}^{10} {x-1\choose r-1} = {10\choose r},\] the last equality by the hockey-stick identity. Thus taking \(r=10/2=5\) maximizes your expected winnings at \({10\choose 5}=252\) dollars.
Problem 2. Squared flips
You know that for any positive integer \(n\), \[{n\choose 0}+{n\choose 1}+\ldots+{n\choose n}=2^n,\] and you can prove this by counting sequences of coin flips. Prove -- again by counting coin flips -- that \[{n\choose 0}^2+{n\choose 1}^2+\ldots+{n\choose n}^2={2n\choose n}.\]


Solution
The number of sequences of \(2n\) coin flips that result in \(n\) heads is of course \({2n\choose n}\). Partitioning this up into the number of such sequences with \(k\) heads in the first \(n\) flips (and \(n-k\) in the second half), of which there are \[{n\choose k}{n\choose n-k}={n\choose k}^2,\] and summing over \(k\) gives the formula.
Problem 1. Power-full sums
Prove that for all positive integers \(n\) and \(k\), \[\sum_{x=1}^n x^k+\sum_{x=1}^{n^k} \lfloor x^{1/k}\rfloor = n (n^k+1).\]
Solution
Let \(X\) be the random variable chosen uniformly from \(\{1,2,\ldots, n\}\). Then \[E(X^k) = \sum_{x=1}^n \frac{x^k}{n}.\] Alternatively, by the tail-sum formula, \[E(X^k)=\sum_{x=0}^{n^k} P(X^k>x) = \sum_{x=0}^{n^k} P\left(X>\lfloor x^{1/k}\rfloor\right)= \sum_{x=0}^{n^k} \frac{n-\lfloor x^{1/k}\rfloor}{n}.\] Setting these quantities equal, multiplying both by \(n\), and rearranging gives the desired equality.