Problem Solving Answers to Problem Set 4

07 July 2012

1. Let f ∈ C^{1}[a, b], f(a) = 0 and suppose that λ ∈ ℝ, λ > 0

is such that

|f′(x)| ≤ λ |f(x)|

for all x ∈ [a, b]. Is it true that f(x) = 0 for all x ∈ [a, b]? Answer: My first thought is that this says f(x) is ‘subexponential’ in some sense; and if |f(x)| < Ce^{λx} then f(a) = 0 will imply that f(x) = 0. Can we make this rigorous? I think one could do it by integrating f′(x)/f(x). But it is probably easier to use the Mean Value Theorem. First, assuming the result is false we can replace a by the largest t ∈ [a, b] such that f(x) = 0 on [a, t]. So we may assume that there are reals x ∈ [a, b] arbitrarily close to a such that f(x) ≠ 0. Choose c ∈ [a, b] close to a. (We will decide later what this means.) Let

d = max_{x∈[a,c]} |f(x)| .

By the Mean Value Theorem

f(d) = f(d) − f(a)
= (d − a)f′(t)

for some t ∈ (a, d).

But then, by the hypothesis in the question

|f(d)| ≤ (d − a)λ |f(t)|
≤ (d − a)λ |f(d)| .

It follows that

d − a ≥ 1/λ,

which cannot hold if we choose

c − a < 1/λ.

2. What is the greatest sum that cannot be paid for in 2c and 5c coins? Answer: This is a simple exercise in the Chinese Remainder Theorem. We know that given n we can solve

2x + 5y = n

in integers (positive or negative). Suppose n ≥ 10; and suppose

2x + 5y = 10,

with x, y ∈ ℤ. Then (x_{0}, y_{0}) = (x + 5t, y − 2t) will also satisfy the equation

2x_{0} + 5y_{0} = 10,

for any t ∈ ℤ. We can choose t such that x_{0} ∈ [0, 5). Then 2x_{0} < 10 and so y_{0} > 0. Thus we have a solution of the equation with x, y ≥ 0. So we only need to consider 0 ≤ n < 10; and it is evident that the largest integer not expressible in the form 2x + 5y with x, y ≥ 0 is 3.

By the same argument, if m, n are coprime then any integer ≥ mn is expressible in the form mx + ny with x, y ≥ 0. It’s a little more difficult to show that the largest integer not expressible in this form is mn − (m + n). This uses the uniqueness modulo mn) part of the Chinese Remainder Theorem.