PUTNAM PROBLEM SOLVING SEMINAR WEEK 6: FUN WITH FUNCTIONAL EQUATIONS (AND VIN DE SILVA)

VIN DE SILVA AND RAVI VAKIL

The Putnam is this Saturday! See the website for details.

The Rules. These are way too many problems to consider. Just pick a few problems you like and play around with them.

You are not allowed to try a problem that you already know how to solve. Otherwise, work on the problems you want to work on. If you would like to practice with the Pigeonhole Principle or Induction (a good idea if you haven’t seen these ideas before), try those problems.

The Hints. Work in groups. Try small cases. Do examples. Look for patterns. Draw pictures. Use lots of paper. Talk it over. Choose effective notation. Look for symmetry. Divide into cases. Work backwards. Argue by contradiction. Consider extreme cases. Eat pizza. Modify the problem. Generalize. Don’t give up after five minutes. Don’t be afraid of a little algebra. Sleep on it if need be. Ask.

Miscellaneous interesting problems.

1. Suppose f(n) is a function from {0, 1, … } to ℝ, such that f(0) = 3, f(1) = 8, and f(n) = 5f(n − 1) − 6f(n − 2). Find a general formula for f(n). (Hint: Guess an answer of the form ab^{n} + cd^{n}).

2. Suppose f(n) is a function from {0, 1, … } to ℝ such that f(0) = 2, f(1) = 6, and f(n) = 4f(n − 1) − 4f(n − 2). Find a general formula for f(n). (Hint: Guess an answer of the form (an + b)c^{n}.)

Useful fact: Solutions to recurrence relations of the above forms are always sums of terms of type (a_{i}n^{i} + a_{i−1}n^{i−1} + ⋯ + a_{0})b^{n}. You can try this out in the next two problems.

3. Suppose f(n) is a function from {0, 1, … } to the positive real numbers such that f(n) = −f(n − 1) + 2f(n − 2). Show that f(n) = f(0) for all n, i.e. that f is a constant function.

4. Suppose f(n) is a function from {0, 1, … } to ℝ such that f(0) = 0, f(1) = 1, and f(n) = f(n − 1) + f(n − 2). (These are the Fibonacci numbers!) Find a general formula for f(n).

Date: Tuesday, December 3, 2002.

Two classical functions, disguised.

5. Suppose f(x, y) is a function from ordered pairs of positive integers, to the positive integers, satisfying the following properties:

(i) f(x, y) = f(y, x), (ii) f(x, x) = x, (iii) If y > x, then f(x, y) = f(x, y − x).

What is the function f? Prove it!

6. Suppose f(x, y) is a function from ordered pairs of non-negative integers, to the nonnegative integers, such that f(x, y) is the smallest non-negative integer not appearing in the set

{f(x′, y) : x′ < x} ∪ {f(x, y′) : y′ < y}.

For example, f(0, 0) = 0, f(1, 0) = 1, and f(1, 1) = 0. What is the function f? Prove it! (Hint: People in computer science may recognize this function fastest.)

Putnam Problems.

1992A1. Prove that f(n) = 1−n is the only integer-valued function defined on the integers that satisfies the following conditions:

(i) f(f(n)) = n, for all integers n; (ii) f(f(n + 2) + 2) = n for all integers n; (iii) f(0) = 1.

1999A1. Find polynomials f(x), g(x), and h(x), if they exist, such that, for all x,

|f(x)| − |g(x)| + h(x) = \begin{cases}−1 & if x < −1 \\ 3x + 2 & if −1 ≤ x ≤ 0 \\ −2x + 2 & if x > 0. \end{cases}

1988A5. Prove that there exists a unique function f from the set ℝ^{+} of positive real numbers to ℝ^{+} such that

f(f(x)) = 6x − f(x)  and  f(x) > 0  for all x > 0.

1986B5. Let f(x, y, z) = x^{2} + y^{2} + z^{2} + xyz. Let p(x, y, z), q(x, y, z), r(x, y, z) be polynomials with real coefficients satisfying

f(p(x, y, z), q(x, y, z), r(x, y, z)) = f(x, y, z).

Prove or disprove the assertion that the sequence p, q, r consists of some permutation of ±x, ±y, ±z, where the number of minus signs is 0 or 2.

Problems from past International Mathematical Olympiads.

Here is some past IMO problems involving functional equations. I made full use of John Scholes excellent website at http://www.kalva.demon.co.uk/ in compiling this list. 1968. Let f : ℝ → ℝ satisfy the functional equation:

f(x + a) = 1/2 + \sqrt{f(x) − f(x)^{2}}

for some fixed a > 0. Prove that f is periodic, and give an example of a non-constant f satisfying the equation for a = 1. 1981. The function f(x, y) is defined for all pairs of non-negative integers x, y and satisfies the following functional equations:

f(0, y) = y + 1
f(x + 1, 0) = f(x, 1)
f(x + 1, y + 1) = f(x, f(x + 1, y))

Determine f(4, 1981). 1988. A function f is defined on the positive integers by the following formulae:

f(1) = 1
f(3) = 3
f(2n) = f(n)
f(4n + 1) = 2f(2n + 1) − f(n)
f(4n + 3) = 3f(2n + 1) − 2f(n)

Determine the number of positive integers n ≤ 1988 for which f(n) = n. 1973. Let G be a class of functions ℝ → ℝ of the form f(x) = ax + b, where a ≠ 0. The class G is closed under taking inverses and under composition of functions. Now suppose that for each f ∈ G there is a point fixed by f. Prove that the functions in G have a common fixed point. 1987. Prove that there is no function f from the set of non-negative integers to itself which satisfies the functional equation f(f(n)) = n + 1987. 1978. The set of positive integers is expressed as the union of two disjoint subsets

{f(1), f(2), f(3), … } and {g(1), g(2), g(3) … },

where f(1) < f(2) < f(3) < … and g(1) < g(2) < g(3) …, and g(n) = f(f(n)) + 1 for all n. Determine f(240). 2002. Find all functions f : ℝ → ℝ satisfying the functional equation:

(f(x) + f(y))(f(u) + f(v)) = f(xu − yv) + f(xv + yu)

Technical exercise.

T1. Let f : ℝ → ℝ satisfy the functional equation f(x+y) = f(x)+f(y). Is it necessarily true that f(x) = cx, where c = f(1) is constant? Which of these conditions makes that conclusion true: f is continuous; f is monotone; f also satisfies f(x^{2}) = f(x)^{2}.

Suppose the graph of f, that is the points {(x, f(x)|x ∈ ℝ} ⊂ ℝ^{2}, doesn’t contain any points in the disk of radius 0.0001 centered at the point (10, 1001). Show that f(x) = cx.

[Very technical] If f is measurable, show that f(x) = cx. Curious geometry.

G1. [from Andreescu–Gecla, Mathematical Olympiad Challenges] Let n ≥ 3 be an integer. Suppose f : ℝ^{2} → ℝ is a function such that whenever x_{1}, x_{2}, …, x_{n} lie at the vertices of a regular n-gon we have:

f(x_{1}) + f(x_{2}) + ⋯ + f(x_{n}) = 0

Show that f = 0.

G2. We define a cuboid to be a set Q ⊂ ℝ^{2} of the form:

Q = {(x, y)|a_{1} ≤ x ≤ a_{2}, b_{1} ≤ y ≤ b_{2}}

and a polycuboid to be a set P ⊂ ℝ^{2} which can be expressed as a finite union of cuboids. Let P denote the set of polycuboids. Let f : P → ℝ be a function satisfying the functional equation:

f(P_{1} ∪ P_{2}) + f(P_{1} ∩ P_{2}) = f(P_{1}) + f(P_{2})

and also f(∅) = 0. Find some interesting examples of such f.

This handout can (soon) be found at

http://math.stanford.edu/˜ vakil/stanfordputnam/

  E-mail address: silva@math.stanford.edu, vakil@math.stanford.edu