| 101. An experiment has n possible outcomes, all equally likely. Each trial is independent. We repeat until we have two trials with the same outcome. For example, we would stop after getting 1, 4, 3, 4. What is the expected number of trials f(n)? Find an asymptotic expression for f(n). | |
| 102. I have n fair coins. I toss them. I leave those that came up heads and toss those that came up tails. And so on. Each time I toss just those that came up tails the previous time, and I stop if there were none. What is the expected number of tosses f(n)? [For example, with 3 coins I might get: HTT, HT, T, H, 4 tosses.] Estimate f(n). [In other words find upper and lower bounds, or an asymptotic expression]. | |
| 103. Toss a fair coin repeatedly. Suppose the outcome of the nth toss is En. We have some decision rule whereby depending on E1, E2, ... , En we either (1) toss again, (2) declare outcome A and stop, or (3) declare outcome not A and stop. The decision rule is arranged so that the probability of A is 1/3. Show that the expected number of tosses is at least 2. | |
| 104. We are given n distinct items a1, a2, ... , an. They are arranged in a random order. What is the expected number of items for which we have ai in the ith place? | |
| 105. Define the n x n matrix A by Aij = i j. The elements of A are integers in the range 1 to n2. But some numbers appear more than once and some do not appear at all. Let B be the set of numbers which appear at least once and let f(n) = |B|/n2. Show that f(n) → 0 as n → ∞. [You may find it helpful to assume the following result. Define g(n) as the number of prime factors of n counting multiplicity, so g(p1r1p2r2 ... pmrm) = ∑ ri. Then g(n) ~ ln ln n.] | |
| 106. f is a continuous function on the non-negative reals. f has the property that f(x + a) - f(x) → 0 as x → ∞ for each a. Prove that we can find functions g and h such that: (1) f(x) = g(x) + h(x) for all x; (2) g(x) → 0 as x → ∞; (3) h is differentiable; and (4) h'(x) → 0 as x → ∞. | |
| 107. f is continuous on the non-negative reals. For each positive k the sequence f(k), f(2k), f(3k), ... tends to zero. Is it necessarily true that f(x) → 0 as x → ∞. | |
| 108. Let C be the set of all functions f on the non-negative reals with derivatives of all orders such that f(x) >= 0, f '(x) <= 0, f ''(x) >= 0, f '''(x) <= 0, ... for all x. Show that C is convex [In other words, if fi ∈ C, λi ≥ 0 and ∑i=0n λi = 1, then ∑i=0n λi fi ∈ C.]. The extreme points of C are the functions f such that if f = ∑i=0n λi fi with fi ∈ C, λi ≥ 0 and ∑i=0n λi = 1, then all but one λi are zero. Show that the extreme points are the functions a e-bx with a, b ≥ 0. | |
| 109. Place a positive real ai jat each lattice point (i, j) of the plane such that ai j = (ai+1 j + ai j+1 + ai-1 j + ai j-1)/4 for all i, j. Show that all ai j are equal. |
Donald J Newman, A problem seminar (Springer, problem books in mathematics, 1982). Highly recommended. It comes with short hints, giving the key idea and solutions which are concise but motivated (in other words, they often explain how you might have found the solution yourself).
John Scholes
jscholes@kalva.demon.co.uk
25 Sep 1999