| 71. S is a subset of {1, 2, ... , n} such that if k ∈ S, then 2k ∉ S. Let f(n) be the maximum possible number of elements in such an S. Estimate f(n). [In other words, find upper and lower bounds for f(n), or an asymptotic expression for f(n) as n → ∞, as appropriate. g(n) is an asymptotic expression for f(n), or f(n) ~ g(n), if f(n)/g(n) → 1 as n → ∞.] | |
| 72. Let a1, a2, a3, ... be the powers [positive integers of the form nm with m and n positive integers and m > 2] arranged in increasing order. The first few terms are: 1, 4, 8, 9, 16, 25, ... . Find an asymptotic expression for an. | |
| 73. Let S = {Pi} be a set of n points in the unit square. Relabel the points Q1, Q2, ... , Qn so that the path length Q1Q2 + Q2Q3 + ... + Qn-1Qn is as short as possible. Let this length be f(S). Let g(n) = sup f(S), where the supremum is taken over all possible sets S with n points (in the unit square). Estimate g(n). | |
| 74. The Euclidean algorithm for finding the greatest common divisor d of two positive integers m and n involves replacing the pair (m, n) by the pair (k, m), where k is the remainder when n is divided by m. The algorithm terminates when k = 0. The number of steps is the number of replacements. For example, (35, 20) requires 4 steps: (35, 20), (20, 35), (15, 20), (5, 15), (0, 5). Estimate the maximum number of steps for (m, n) with m, n < N. | |
| 75. How many edges can a triangle-free graph of n points have? | |
| 76. Let f(n) = n - [n/2] + [n/3] - ... . Prove that f(n)/n → ln 2 as n → ∞. | |
| 77. f(x, y) is a polynomial with real coefficients having degree m in x and degree n in y. Prove that f(x, ex) = 0 has at most mn + m + n real roots. | |
| 78. Find a real valued function f on the real line such that f(x)/x2 → 1 as x → ∞, but f '(x)/(2x) does not tend to 1 as x → ∞. Prove that such an f cannot be convex. | |
| 79. f and g are real-valued functions on [0, 1] and differentiable on (0, 1]. g'(x) > 0 on (0 ,1] and limx→0+ f '(x)/g'(x) exists (but may be ± ∞). Prove that even if f(0)/g(0) is indeterminate, limx→0+ f(x)/g(x) exists (but may be ± ∞). | |
| 80. f is a real valued function on the reals and f(x) + f '(x) → 0 as x → ∞. Prove that f(x) → 0 and f '(x) → 0 as x → ∞. |
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).
Seminar home
Seminar previous
Seminar next
John Scholes
jscholes@kalva.demon.co.uk
25 Sep 1999