Problem Solving Answers to Problem Set 1

04 July 2012

1. Let f ∈ C^{1}(a, b), lim_{x→a+} f(x) = +∞, lim_{x→b−} f(x) = −∞ and f′(x) + f^{2}(x) ≥ −1 for x ∈ (a, b). Prove that b − a ≥ π and give an example where b − a = π. Answer: I misread this when I first read it (without my glasses), as I read f^{1} for f′, and so thought f^{2} meant f′′. Which is probably irrelevant, except to read the problems carefully, and make sure you are wearing glasses if necessary! But once I had understood the problem, I wrote it as

\frac{df}{f^{2} + 1} ≥ −dx.

(It’s probably not fashionable to treat df, dx as “real” quantities, but it can be justified, and I often find it helpful.) We may assume that a = 0, on replacing f(x) by f(x − a). We have to show that b ≥ π. Integrating,

∫_{∞}^{−∞} \frac{df}{f^{2} + 1} ≥ −b,

ie

[arctan(f)]_{∞}^{−∞} ≥ −b,

ie

−π ≥ −b,

or

b ≥ π.

2. A collection of subsets of {1, 2, …, n} has the property that each pair of subsets has at least one element in common. Prove that there are at most 2^{n−1} subsets in the collection. Answer: I got this from a collection of problems on the pigeon-hole principle, so that gave me a starting-point. Let N = {1, 2, …, n}, and let S = 2^{N}, ie the set of 2^{n} subsets of N. We are told we have a subset

X ⊂ S,

ie a collection of subsets of N. To apply the pigeon-hole principle we must divide S into 2^{n−1} subsets, ie with an average of 2 elements per subset. The obvious way is to pair off the complementary subsets {Z, N \Z} of S. The pigeon-hole principle tells us that if we have a subset X ⊂ S containing > 2^{n−1} elements then two of these elements must be in the same subset {Z, N \ Z}. Since Z and N \ Z have no element in common, this will contradict the hypothesis of the question. Hence there must be ≤ 2^{n−1} subsets. [I was told that this makes the question seem much more complicated than it really is!]