Let f:R→N be a function which satisfies f(x+1f(y))=f(y+1f(x)) for all x, y∈R. Prove that there is a positive integer which is not a value of f. Proposed by Žymantas Darbėnas (Zymantas Darbenas), Lithuania
Problem
Source: IMO ShortList 2008, Algebra problem 6
Tags: function, algebra, functional equation, range, IMO Shortlist
16.07.2009 00:18
I have only been able to do this one by brute force. I'll post my solution in case it gives anybody an idea on how to finesse it... Assume that for all n∈N, a real r exists such that f(r)=n. We may assume wlog that f(0)=1, since for any real constant r, f′(x)=f(r+x) is a solution iff f(x) is a solution because if f is a solution, then f′(x+1f′(y))=f(x+r+1f(y+r))=f(y+r+1f(x+r))=f′(y+1f′(x)), and taking r such that f(r)=1, then f′(0)=f(r)=1. Now,
Moreover, if f(r)=f(r′) for any two reals r≠r′,
A contradiction is then found
After playing around for quite a while with the function, I have not been able to find any "smart shortcuts" to this solution, and finding the correct order of proving partial results was quite hard for me. The idea of playing around with reals of the form r+\frac{1}{n} where r is any real and n is a positive integer, and from there to reals of the form r+q where q is a positive rational is more or less hinted by the form of the functional relation, but the way to a contradiction was still not obvious to me after this observation... Hopefully someone smarter will come up with a more elegant solution.
17.07.2009 03:34
Hopefully this is right.
17.07.2009 04:09
Bacteria wrote: Since \mathbb{N} and \mathbb{Q} have the same size, any function from \mathbb{Q} to \mathbb{N} that is onto must also be one to one. I think this is not necessarily true; consider the function such that, for any rational q = \frac {m}{n}, where m,n are coprime integers, associates f(q) = |n|, except for f(0) = 1. This function is suprajective, but not one-to-one. The problem is that bijectivity of a suprajective function holds necessarily only when the cardinal of range and image are the same and finite, but is not necessarily true for infinite sets of the same cardinality... Otherwise, my solution would also be complete as soon as I prove that
18.07.2009 12:47
Very nice problem! Here's the solution I got: Let's assume that there are x_k's so that f(x_k)=k, \forall k\in \mathbb{N} We can assume that f(0)=f(1)=1 (An affine modification and showing that f^{-1}(1) contains at least two elements does the trick) This gives (*) f(x+1)=f(\frac{1}{f(x)}) which implies f(k)=1 \, \forall k\in \mathbb{N} also f(x+1)=f(\frac{1}{f(x)})=f(\frac{1}{f(\frac{1}{f(x-1)})})=f(\frac{1}{f(x-1)}+1)=f(x) so f is 1-periodic. this implies together with (*) f(x)=f(\frac1{f(x)}) and f(\frac1k)=k \forall k\in \mathbb{N} Now if a,b\in \mathbb{N} repeated use of our functional equation gives (**) f(x+\frac{a}{b})=f(\frac{1}{f(x)}+\frac{a}{b}) So if f(\frac34)=m then f(\frac1m+\frac14)=1 that means we can find x,y \in \mathbb{N} , (x,y)=1, y\geq 2 so that f(\frac{x}{y})=1 then let z\equiv x^{-1}\pmod{y} from repeated application of (**) we know f(z \frac{x}{y})=1 and by 1-periodicity that f(\frac{1}{y})=1 a contradiction as f(\frac1{y})=y
28.07.2009 16:55
April wrote: Let f: \mathbb{R}\to\mathbb{N} be a function which satisfies f\left(x + \dfrac{1}{f(y)}\right) = f\left(y + \dfrac{1}{f(x)}\right) for all x, y\in\mathbb{R}. Prove that there is a positive integer which is not a value of f. Proposed by Lithania Does there exist function f: R\rightarrow N \{0,a\}( where a are positive integer)such that condition problem I can't slove this problem. Can anyone help me?
17.09.2011 03:53
Suppose for the sake of contradiction that \mathbb{Z}^+\subseteq\{f(x)\}_{x\in\mathbb{R}}. By translation, WLOG f(0)=1. Lemma: If f(a)=f(b), then f(a+r)=f(b+r) for all r\in\mathbb{Q}^+. Proof: From P(x,a),P(x,b), we have f\left(a+\frac{1}{f(x)}\right) = f\left(x+\frac{1}{f(a)}\right) = f\left(x+\frac{1}{f(b)}\right) = f\left(b+\frac{1}{f(x)}\right).If r=p/q, then taking x such that f(x)=q and repeating this p times gives the desired result.\blacksquare Corollary: If f(r)=1=f(0) for some rational r, then f(k|r|)=1 for all k\in\mathbb{Z}^+. Proof: Strong induction on k with the lemma.\blacksquare Note that P(-1,0)\implies f(0) = f\left(\frac{1}{f(-1)}\right), so taking k=f(-1) in the corollary we have f(1)=f(0)=1. Now by the lemma, P(x,0)\implies f(x+1) = f\left(\frac{1}{f(x)}\right)\implies f\left(x-\frac{1}{f(x)}+2\right) = f(1) = 1.But in the same way, P\left(x-\frac{1}{f(x)}+2,0\right)\implies f\left(x-\frac{1}{f(x)}+2-\frac{1}{f(1)}+2\right) = 1as well, so again by the lemma, f(x+2) = f\left(x+4-\frac{1}{f(1)}\right) = f(x+3)for all x\in\mathbb{R}. Hence f has a period of 1, so P(x,0)\implies f(x) = f(x+1) = f\left(\frac{1}{f(x)}\right)\implies n = f\left(\frac{1}{n}\right)for all positive integers n (by assumption). Furthermore, the lemma is now obviously true for all r\in\mathbb{Q} (not necessarily positive). If f(p/q)=1=f(0) where p,q are coprime nonzero integers, then taking kp\equiv1\pmod{q} in the corollary yields q=f(1/q)=1, i.e. p/q must be an integer. Therefore P(x,0)\implies f(x+1) = f\left(\frac{1}{f(x)}\right)\implies f\left(x-\frac{1}{f(x)}\right) = 1\implies x-\frac{1}{f(x)}\in\mathbb{Z}for all x\in\mathbb{Q}. If x=p/q with \gcd(p,q)=1 and q>0, then it's easy to show that q|f(x) and f(x)|q, whence f(x)=q. But then f(1/3)=3=f(2/3)\implies 1=f(0)=f(1/3)=3 by the lemma, a contradiction.
20.04.2015 03:17
It is easy to see f(x)=f(y) \Rightarrow f(x+r)=f(y+r) for any r>0 rational. Now, let's view f as a surjective function \mathbb{Q} \rightarrow \mathbb{R}. It is surjective because if f(a)=n and a isn't rational, then take any b=a-(1/f(y)) for any rational y and we get n=f(a)=f(b+(1/f(y)))=f(y+(1/f(b))) and y+(1/f(b)) is rational. From now on I speak only about \mathbb{Q}. Now assume f(x)=f(x+r) for all sufficiently big x (say x>N) and r is fixed (call such an r good). Then take any q \le N and any y>N and write q=x+(1/f(y)) and notice z:=y+(1/f(x))>N. Therefore, by our original observation, f(q+r)=f(z+r)=f(z)=f(q) and so f(x)=f(x+r) for all x, even if x<N. Now I prove that there exists some n \in \mathbb{N} such that r=1/n satisfies this. Indeed, let y=x-(1/f(x)) for any x, and notice how f(x+1/f(y))=f(x) and therefore for any q>0, f(x+1/f(y)+q)=f(x+q) and if r=1/f(y) then for any x'>x we have f(x')=f(x+q)=f(x+1/f(y)+q)=f(x'+r) and so for sufficiently big x the equation holds and thus it holds for all x. Therefore, if n=f(y), we have f(x+1/n)=f(x) for all x. Notice 1/n is good. Now let k be any integer and let f(x)=k for some x, then f(y+1/k)=f(y+1/f(x))=f(x+1/f(y))=f(x+1/n)=f(x)=k. Thus f(y+1/k) \neq f(y+1/l) for any y \neq l, and thus 1/k-1/l is not good for any k,l. But k=n-1, l=n(n-1) implies 1/k-1/l=1/n which is good. Thus n=1, and so the only good numbers are integers. But by our first result, x-(1/f(x))-(y-(1/f(y))) is good always, and thus x-y=n+(1/f(x))-(1/f(y)) for some n. So x-y=n+1/m-1/k for some n,m,k. So any rational number is of the form n+1/m-1/k, which is clearly false. Take, for example 1/2-\epsilon, for a really small positive \epsilon. Thus, we are done.
27.04.2017 02:53
12.06.2017 00:35
Suppose for the sake of contraddiction that f is suriective. The invariance by traslation along x axis, and suriectivity let us setting WLOG f\left(0\right)=1. Let P\left(x,y\right) be the equality in the text. Lemma 1: for all k\in\mathbb{N} we have that f\left(j\right)=f\left(j+\frac{k}{f\left(j-\frac{1}{f\left(j\right)}\right)}\right)\ \ \forall\ j\in\mathbb{R}We show this by induction on k. The base case k=0 is trivial. Now suppose the lemma 1 true for k\le t. So we have that f\left(j\right)=f\left(j-\frac{1}{f\left(j\right)}+\frac{1}{f\left(j\right)}\right)\stackrel{\text{inductive hp.}}{=}f\left(j-\frac{1}{f\left(j\right)}+\frac{1}{f\left(j+\frac{t}{f\left(j-\frac{1}{f\left(j\right)}\right)}\right)}\right)=f\left(j+\frac{t}{f\left(j-\frac{1}{f\left(j\right)}\right)}+\frac{1}{f\left(j-\frac{1}{f\left(j\right)}\right)}\right)=f\left(j+\frac{t+1}{f\left(j-\frac{1}{f\left(j\right)}\right)}\right)Where the third equality is obtained by P\left(j-\frac{1}{f\left(j\right)},\ j+\frac{t}{f\left(j-\frac{1}{f\left(j\right)}\right)}\right). Now putting k=f\left(j-\frac{1}{f\left(j\right)}\right) in the lemma 1 we have that f\left(j\right)=f\left(j+1\right), so f is periodic with period 1. By P\left(x,\ 0\right) we have f\left(x\right)=f\left(1+\frac{1}{f\left(x\right)}\right)\stackrel{\text{periodicity}}{=}f\left(\frac{1}{f\left(x\right)}\right), and by suriectivity we can put f\left(x\right)=z, so f\left(\frac{1}{z}\right)=z\ \ \forall\ z\in\mathbb{Z}^+. Lemma 2: if there are a,b\in\mathbb{Q} (WLOG a<b) such that f\left(a\right)=f\left(b\right), then f is periodic with period b-a in the domain \mathbb{Q}. As math154 did, comparing P\left(x,a\right) and P\left(x,b\right) we have that f\left(a+\frac{1}{f(x)}\right)=f\left(b+\frac{1}{f(x)}\right)and so inductively f\left(a+\frac{n}{f(x)}\right)=f\left(b+\frac{n}{f(x)}\right)\ \ \forall\ n\in\mathbb{Z}^+,\ x\in\mathbb{R}hence by suriectivity of f f\left(a+\frac{n}{m}\right)=f\left(b+\frac{n}{m}\right)\ \ \forall\ n,m\in\mathbb{Z}^+hence by periodicity f\left(a-i+\frac{n}{m}\right)=f\left(b-i+\frac{n}{m}\right)\ \ \forall\ n,m\in\mathbb{Z}^+,\ i\in\mathbb{Z}and finally, putting u=a-i+\frac{n}{m} (u is a generic rational)f\left(u\right)=f\left(u+\left(b-a\right)\right)\ \ \ \blacksquareNow let's choose two positive integers 1<p<q such that \gcd\left(p,q\right)=1. Let's say that f\left(\frac{p}{q}\right)=h=f\left(\frac{1}{h}\right). So f on domain \mathbb{Q} has period \left|\frac{p}{q}-\frac{1}{h}\right|=\left|\frac{ph-q}{qh}\right|, but we also know that it has period 1, hence it has period \frac{1}{l} where 1<l=\frac{qh}{\gcd\left(qh,ph-q\right)}, so f\left(0\right)=f\left(\frac{1}{l}\right), contraddiction because f\left(0\right)=1 and f\left(\frac{1}{l}\right)=l>1.
07.07.2020 10:13
Hopefully I didn't mess anything up . Suppose that f is surjective. Claim 1: For all x\in\mathbb{R}, \left\{f(x+1), f\left(x+\frac 12\right), f\left(x+\frac 13\right),\hdots\right\}=\mathbb{N}.Proof: In the functional equation, if we fix x and vary y, we see that the right hand side varies through all positive integers, due to surjectivity. Thus the left hand side must vary through all positive integers too, hence the claim. \blacksquare Thus the restriction of f onto \mathbb{Q} is also surjective. Hence we will consider the functional equation only in \mathbb{Q}. We prove a simple claim. Claim 2: If f(a)=f(b), then f(a+t)=f(b+t) for any t\in\mathbb{Q}^+ Proof: For each x, we have f\left(a+\frac{1}{f(x)}\right) = f\left(x+\frac{1}{f(a)}\right) = f\left(x+\frac{1}{f(b)}\right) = f\left(b+\frac{1}{f(x)}\right).By choosing x so that f(x)=n, we deduce that f\left(a+\tfrac 1n\right) = f\left(b+\tfrac 1n\right). Repeating this argument, we get f\left(a+\tfrac mn\right) = f\left(b+\tfrac mn\right) for any m,n>0, hence the claim. \blacksquare Claim 3: [Main Claim] f is periodic with period 1. Proof: Fix a large positive integer M. Aiding with Claim 2, we will prove that f\mid_{\geq -M} is periodic with period 1. To that n, it suffices to show that for each prime p, f has a period t which \nu_p(t)\leq 0. Note that by Claim 1, there exists a positive integer n such that f(-(M+2020)) = f\left(-\left(M+2020+p+\frac 1n\right)\right)thus f has a period t = p+\tfrac 1n. Clearly \nu_p(t)\leq 0 so we are done. \blacksquare Now, we note that, for any a\in\mathbb{Q}, the function g(x) = f(x+a) satisfies the functional equation by plugging in (x,y) with (x+a,y+a). Thus, WLOG, assume that f(0)=1. Therefore f(1)=f(2)=\hdots=1. Moreover, f\left(\frac{1}{f(x)}\right) = f\left(x+\frac{1}{f(0)}\right) = f(x+1) = f(x), so as f is surjective, f\left(\tfrac 1n\right) = n for each positive integer n. Now we claim that we are unable to determine t=f\left(\tfrac 23\right). From the functional equation, 1 = f\left(\frac{2}{3}+\frac{1}{f\left(\tfrac 13\right)}\right) = f\left(\frac 1t + \frac 13\right), so f is periodic with period \tfrac 1t + \tfrac 13 = \tfrac{t+3}{3t}. Since \gcd(t+3,3t)\mid 9, f is periodic with period \tfrac{\gcd(t+3,9)}{3t}. This is a contradiction unless 3t=\gcd(t+3,9). This equation has no solutions.
06.05.2022 09:12
Don't know if this is correct. We look at f(x + 1/f(y)). If we plug in x = y + f(y) so we get that f(x + 1/(x-y)) = f(y+f(y)+1/f(y). Now if we plug in x = y + 1/f(y) we see that f(2x-y)=f(x+1/(x-y)). Puting this together gives f(2x-y)=f(y+f(y)+1/f(y)) and so f(2(x+n)-y)=f(y+f(y)+1/f(y)) and what follows is that f(2(x+n)-y)=f(2x-y), so f(2x-y+2n)=f(2x-y). Since n can be any real number we get that f(x) must be a constant function. This satisfies our requirement so we are done because if f(x) is constant there is a number outside of it's range
23.05.2022 16:17
Assume the contrary. By translating, WLOG f(1)=f(0)=1. Lemma: f(a)=f(b)\implies f(a+q)=f(b+q)~\forall a,b \in \mathbb{R}, q\in \mathbb{Q}. Proof. Note that f(a+\frac{1}{f(x)})=f(x+\frac{1}{f(a)})= f(x+\frac{1}{f(b)})=f(b+\frac{1}{f(x)}).Let f(x)=x \in \mathbb{N} then by induction we are done. As a corollary we also get f(q)=f(q+1) ~\forall q\in \mathbb{Q}. \square Setting y=1 and f(x)=x: x\in \mathbb{N} yields f(x)=f(\frac{1}{x}). Note also that \forall y\in \mathbb{R}, x\in \mathbb{N}, the set containing f(y+\frac{1}{x}) is \mathbb{N}. Finish: Let f(\frac{1}{x}+\frac{1}{3})=1 where x is natural. Also let \frac{1}{x}+\frac{1}{3}=\frac{a}{b}, where a,b are co prime. It is clear that that b>1. But \exists c,d \in \mathbb{N}: ac-bd=1. It forces b=1, a contradiction. Hence f is not surjective. Q.E.D.
23.05.2022 17:27
Mathboi489 wrote: Don't know if this is correct. We look at f(x + 1/f(y)). If we plug in x = y + f(y) so we get that f(x + 1/(x-y)) = f(y+f(y)+1/f(y). Now if we plug in x = y + 1/f(y) we see that f(2x-y)=f(x+1/(x-y)). Puting this together gives f(2x-y)=f(y+f(y)+1/f(y)) and so f(2(x+n)-y)=f(y+f(y)+1/f(y)) and what follows is that f(2(x+n)-y)=f(2x-y), so f(2x-y+2n)=f(2x-y). Since n can be any real number we get that f(x) must be a constant function. This satisfies our requirement so we are done because if f(x) is constant there is a number outside of it's range Your approach is wrong, plugging in x=y+f(y) doesn't give that. Also there are other errors.
03.06.2023 17:27
Solved with Siddharth03, AdhityaMV
29.05.2024 03:18
Assume for the sake of contradiction that f satisfies the condition and is surjective. We claim that for all x \{f\left(x+\frac1n\right)\mid n\in \mathbb N\}=\mathbb NOtherwise, let x,k be numbers such that for all positive integers n, f(x+\tfrac1n)\neq k. Then, let z be a real number such that f(z)=k and let y=z-\tfrac{1}{f(x)} then k=f(z)=f\left(y+\frac{1}{f(x)}\right)=f\left(x+\frac{1}{f(y)}\right)\neq kwhich is a contradiction. Suppose f(x)=f(y) then f\left(x+\frac{1}{f(a)}\right)=f\left(a+\frac{1}{f(x)}\right)=f\left(a+\frac{1}{f(y)}\right)=f\left(y+\frac{1}{f(a)}\right)Since we can arbitrarily choose a, we have f(x+\tfrac1n)=f(y+\tfrac1n) for all n, and applying this repeatedly gives f(x+q)=f(y+q) for any positive rational q. ~ Now, using the first fact and the second fact, we note that since there exists k such that f(0)=f(\tfrac{1}{k}), we have f(\tfrac{1}{k})=f(\tfrac{2}{k}). Inductively, we find that f(0)=f(1) which again using the second fact, f(q)=f(q+1) for all positive rational numbers q. Then, setting f(x)=1 in the original equation gives f\left(x+\frac{1}{f(y)}\right)=f(y+1)for some specific x then f(x+\tfrac{1}{f(y)})=f(y). Now, this means that f(x+\tfrac{1}{n})=n for all positive integers n. We have f(x+\tfrac14+\tfrac1n)=f(x) for some n. By Bezout's, we can always choose another positive rational number \tfrac{a}{b} such that \tfrac14+\tfrac1n-\tfrac{a}{b}=\tfrac{1}{bc} is a unit fraction. We have c=f\left(x+a+\frac{1}{c}\right)=f\left(x+b\left(\frac14+\frac1n\right)\right) = f(x)=1which is a contradiction.