## Sunday, October 22, 2006

### Integrrr... Topic: Algebra. Level: AIME.

Problem: (1992 Putnam - A1) 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$;
(ii) $f(f(n+2)+2) = n$;
(iii) $f(0) = 1$.

Solution: We will use induction to prove the claim for $-k \le n \le k+1$ where $k$ is a nonnegative integer.

Base Case: $k = 0 \Rightarrow f(0) = 1, f(1) = 0$ which are true from (iii) and (i).

Induction Step: Assume that $f(n) = 1-n$ for $-k \le n \le k+1$.

Then $f(k+2) = f(f(-k+1)+2) = -k-1 = 1-(k+2)$ by our induction hypothesis and (ii). Also, $f(-(k+1)) = k+2 = 1-(-(k+1))$ by (i), completing the induction.

Hence $f(n) = 1-n$ for all integers. QED.

--------------------

Comment: Functional equations over the integers are not usually too hard to handle; induction is usually a good way to handle them, strong induction in particular. Most of the time you just need to find out what set to induct on, in this case $[-k,k+1]$.

--------------------

Practice Problem: Find all functions $f: \mathbb{N} \rightarrow \mathbb{N}$ such that

(1) $f(f(n)+n) = f(n)$;
(2) There exists a $n_0$ such that $f(n_0) = 1$.

#### 1 comment:

1. well if f(n_0) = 1 it follows

f(1 + n_0) = 1

and so f(k) = 1 for k \ge n_0

let f(1) = k, then
f( k + 1) = k
f( 2k + 1) = k
...
f(mk + 1) = k

but some m will have mk + 1 \ge n_0 so k = 1

QED lol