Define the function $f: \mathbb N \cup \{0\} \to \mathbb{Q}$ as follows: $f(0) = 0$ and \[ f(3n+k) = -\frac{3f(n)}{2} + k , \] for $k = 0, 1, 2$. Show that $f$ is one-to-one and determine the range of $f$.
Problem
Source: USA TST 2004
Tags: function, modular arithmetic, induction, algebra unsolved, algebra
18.03.2006 18:14
It give for $n=a_0+a_13+\dots +a_k3^k,a_i \in \{0,1,2\}$ $f(n)=a_0+a_1(-3/2)+a_2(-3/2)^2+\dots +a_k(-3/2)^k$. If f(n)=f(m) we have n=m.
18.03.2006 23:10
Wouldn't this imply the existence of a bijection from the reals to the rationals?
18.03.2006 23:50
I've modified the statement of the problem. It's probably the intended statement (of course there is no one-to-one map from the nonnegative reals to the rational numbers ).
17.05.2007 04:45
As pointed out earlier, \[f(\sum_{n=0}^{m} a_{n}3^{n}) = \sum_{n=0}^{m}a_{n}(\frac{-3}{2})^{n})\] where $a_{n}\in \{0,1,2\}$. Now suppose that this mapping is not one-to-one, then \[\sum_{n=0}^{m}a_{n}(-1.5)^{n}= \sum_{n=0}^{m}b_{n}(-1.5)^{n}\] or \[\sum_{n=0}^{m}(a_{n}-b_{n}) (-1.5)^{n}= 0\] so there is some non-zero weighting that causes the sum to come out to zero. Now, multiply by $2^{m}$, and let $d_{n}= a_{n}-b_{n}$, then we get \[\sum_{n=0}^{m}d_{n}(-3)^{n}2^{m-n}= 0\] and taking this in mod $3$ we get $d_{0}\equiv 0$, so $d_{0}= 0$. Now factor out a $(\frac{-3}{2})$ from the sum, and by the same logic we get $d_{1}= 0$, etc., so that $d_{i}= 0$ for all $i$ and the function is one-to-one. We claim the range is all fractions of the form $\frac{n}{2^{m}}$. Note that all fractions not of this form are unattainable, since only two can divide the denominator of any value of this function. We start by showing that all integers are attainable, for, given $n$, we can get both $n+1$ and $n-1$, using the identities $2*(\frac{-3}{2})^{2}+1*(\frac{-3}{2})+0 = 3$ and $2*(\frac{-3}{2})+3 = 0$ to carry, treating the addition as addition in base $\frac{-3}{2}$. Since we have $0$, by this observation we have all the integers. Now, suppose we have all multiples of $\frac{1}{2^{n}}$. Then we have $\frac{k}{2^{n}}$ for all $k$, and so also $\frac{-3k}{2^{n+1}}+\{0,1,2\}$ for all $k$. But we can always satisfy the equation \[\frac{m}{2^{n+1}}= \frac{-3k}{2^{n+1}}+\{0,1,2\}\] as it is equivalent to \[m =-3k+\{0,2^{n+1},2^{n+2}\}\] or \[m \equiv \{0,1,2\}\pmod{3}\] which is of course always true. We therefore have all fractions of the form $\frac{m}{2^{n}}$, as stated.
09.01.2008 12:19
This problem seems too simple to be Q6 in USA TST Here's a slightly different approach $ f(n)$ concisely: Suppose $ f$ is not injective. Then for some $ a \neq b$, we have $ f(a) = f(b)$. Pick the pair $ (a,b)$ with smallest value of $ min (|a|, |b|)$, such that $ a \neq b$ and $ f(a) = f(b)$. Let $ a = 3s+t, b=3u+v$ where $ t,v$ are $ 0,1$ or $ 2$. We have $ \frac{-3}{2} f(s) + t = \frac{-3}{2} f(u) + v$. If $ u=v$, then $ f(s)=f(u)$, and $ min (|s|, |u|) < min (|a|, |b|)$, which contradicts the minimality of the pair $ (a,b)$. If $ u \neq v$, we have $ f(s) - f(u) = \frac {-2}{3} (v-t)$. But we can easily see, from the condition that the range of $ f(n)$ is a subset of all rationals, with denominator a power of $ 2$, and so $ f(s) - f(u)$ is also is a rational, with denominator a power of $ 2$. Since $ 3$ does not divide $ v-t$ (since $ v-t \neq 0$), we know that $ \frac {-2}{3} (v-t)$ is a fraction, that when reduced, has a denominator divisible by $ 3$, which is a contradiction. Next we prove that all integers $ n$ are part of the range of $ f$: By some simple calculations we can see that small integers, $ (-4, -3 ... 3)$ are part of the range. Now suppose there exists an integer $ n$ that is not part of the range of $ f$. Pick the integer with smallest value of $ |n|$ which is not part of the range of $ f$. Let $ n_{1}$ be the residue of $ n$ mod $ 3$ (so $ n_{1}$ is $ 0, 1$ or $ 2$). If $ m = \frac {-2}{3} (n-n_{1})$ is part of the range of $ f$ suppose $ f(t) = \frac {-2}{3} (n-n_{1})$, then we have $ f(3t+n_{1}) = n$, which is a contradiction since $ n$ cannot be expressed such. Thus $ m = \frac {-2}{3} (n-n_{1})$ is also not part of the range of $ f$. But $ |m| < |n|$ (since $ n$ is not small: we have shown small integers, $ -4... 3$ are part of the range of f), which contradicts the minimality of $ |n|$. Now we can prove by induction, that if all rationals of form $ \frac {k}{2^{l}}$ are part of the range of $ f$, then all rationals $ \frac {k}{2^{l+1}}$ can be expressed such. We have proven this for $ l=0$ above. Now for some rational $ \frac {k}{2^{l+1}}$: first choose $ t$ so that $ 3 | k - t*2^{l+1}$, and $ t = 0, 1$ or $ 2$. By induction, there exists $ s$ so that $ f(s) = - \frac { k - t*2^{l+1}}{3*2^l}$, so choose $ u = 3s+t$ and we can compute that $ f(u) = \frac {k}{2^{l+1}}$, as required. Since it's clear that all numbers in range of $ f$ are of the form $ \frac {k}{2^l}$, and we have proved all such numbers are part of the range, the range consists of those numbers.