Find all surjective functions f:N→N such that for all positive integers a and b, exactly one of the following equations is true: f(a)=f(b),f(a+b)=min Remarks: \mathbb{N} denotes the set of all positive integers. A function f:X\to Y is said to be surjective if for every y\in Y there exists x\in X such that f(x)=y.
Problem
Source: MEMO 2015, problem I-1
Tags: function, algebra
27.08.2015 19:13
It's easy to see that f(n)=v_2(n)+1 is a solution and we want to prove that it's the only one. Denote P(a,b) the assertion that either f(a)=f(b) either f(a+b)=\min\{f(a),f(b)\}. Define a function g:\mathbb{N}_0 \to \mathbb{N} satisfying g(n)=f(2^n). P(a,a) implies that f(a) \ne f(2a). P(a,2a) implies that f(3a) =\min\{f(a),f(2a)\} Assume f(3a)=f(2a) < f(a) for some a. Then P(a,3a) implies that f(4a)=f(a)<f(2a) since f(4a) \ne f(2a). So f(a)<f(2a)<f(a). Absurd! Hence our assumtion must have been wrong and we conclude that f(3a)=f(a) must hold for all a. Also P(a,2a) implies f(a)<f(2a) for all a. In particular, we conclude that g is a strictly increasing function. Now we are going to prove by induction over k that f(n)=g(v_2(n)) holds for all n \le 2^k. For k=0,1,2 we already proved it. Now we do the induction step from k to k+1. Take any a \in \{1,2,\dotsc,2^k-1\} and we want to prove f(2^k+a)=g(v_p(2^k+a)) i.e. f(2^k+a)=g(v_p(a)) i.e. f(2^k+a)=f(a). Indeed, it is clear that f(a) \ne f(2^k) and so P(2^k,a) implies that f(2^k+a)=\min\{f(2^k),f(a)\}=f(a) since f(2^k)=g(k)>g(v_2(a))=f(a). So we proved the induction step and thus for all n it holds f(n)=g(v_2(n)). But since f is surjective, also g must be surjective. As g is also strictly increasing, the only possible function is g(n)=n+1 and hence \boxed{f(n)=v_2(n)+1} which is indeed a solution.
27.08.2015 19:35
randomusername wrote: Find all surjective functions f:\mathbb{N}\to\mathbb{N} such that for all positive integers a and b, exactly one of the following equations is true: \begin{align*} f(a)&=f(b), \\ f(a+b)&=\min\{f(a),f(b)\}. \end{align*} Remarks: \mathbb{N} denotes the set of all positive integers. A function f:X\to Y is said to be surjective if for every y\in Y there exists x\in X such that f(x)=y. Let P(x,y) be the assertion (f(x)=f(y) and f(x+y)\ne\min(f(x),f(y))) or (f(x)\ne f(y) and f(x+y)=\min(f(x),f(y))) P(x,x) \implies f(2x)\ne f(x) 1) f(2n-1)=1 and f(2n)\ne 1 \forall n Since surjective, let u>0 such that f(u)=1 If f(1)>f(u)=1, then P(u,1) \implies f(u+1)=\min(f(1),f(u))=1 and so f(x)=1 \forall x\ge u. Impossible since surjective. So f(1)=1 (and f(2)>1) Let u such that f(u)=1. P(u,2) \implies f(u+2)=1 and so f(2n-1)=1 \forall n\in\mathbb N And also f(2n)\ne 1 \forall n else f(x)=1 \forall x\ge n (impossible since surjective) 2) f(4n-2)=2 and f(4n)\ne 2 \forall n Since surjective, let v>0 such that f(v)=2 If f(2)>f(v)=2, then P(v,2) \implies f(v+2)=\min(f(2),f(v))=2 and so f(x)\in\{1,2\} \forall x\ge v. Impossible since surjective. So f(2)=2 (and f(4)>2) Let v (even)such that f(v)=2. P(v,4) \implies f(v+4)=2 and so f(4n-2)=2 \forall n\in\mathbb N And also f(4n)\ne 2 \forall n else f(x)\in\{1,2\} \forall x\ge n (impossible since surjective) 3) Result. The process 1) and 2) can easily be reproduced to show with induction the result : \boxed{f(x)=v_2(x)+1\text{ }\forall x>0} which indeed is a solution Too late, I know
27.08.2015 19:54
We can actually solve the problem with the weaker condition that at least one of the two conditions is satisfied, i.e. f(a)\neq f(b)\implies f(a+b)=\min\{f(a),f(b)\}. Fix some positive integer M, and let m be the smallest value at which f(m) is at least M. Let f(m)=t. Then f(1),f(2),\dots,f(m-1)<M. We will now prove by induction that from now on, f(n)\ge t if m\mid n and else f(n)<M. (*) We will do this by looking at blocks of m. Note that f(m+n)=\min\{f(n),f(m)\}=f(n)<t if f(n)<t, call this (*). Because of (*), we cannot have m consecutive values of f which are <t, because then the next m values are also <t, and so on until infinity, which means f attains finitely many values, contradicting the surjectivity. Moreover, if f(km)\ge t for some positive integer k, then we have f(km+r)=\min\{f(r),f(km)\}=f(r)<M for 0<r<m. Now we cannot have f((k+1)m)<t as it would give m consecutive <t values, so f((k+1)m)\ge t. By induction, our claim is proven. Also, if we'd have M<t, then f wouldn't attain the value M, hence we must have t=M. This turns out to be enough to determine f. For i=1,2,3,\dots, denote b_i as the smallest positive integer for which f(b_i)=i. Because of the above, f(1) can only be 1, else all the values would be >1. Also, b_{i}\mid b_{i+1} because of the above, so let a_i=\frac{b_i}{b_{i-1}}\ge 2. Thus, b_1=1 and b_i=a_ia_{i-1}\dots a_2. Let j be the largest i such that b_i\mid n. Then b_j\mid n implies f(n)\ge j by (*). Also, f(n)<j+1 because b_{j+1}\not| n. So f(n)=j. This function satisfies our condition because if f(c)\neq f(d), say i=f(c)<f(d)=j, then f(c+d)=i=\min\{f(c),f(d)\} because b_i\mid c+d, but if b_{i+1}\mid c+d, then as b_{i+1}\mid b_j\mid d, we get b_{i+1}\mid c, false. To solve the MEMO problem from here, we just need to note that f(2n)\neq f(n), which follows from the MEMO problem's condition for a=b.
05.02.2017 07:48
For n\in \mathbb N, let's define the sets A_n=\left\{x\in\mathbb N\mid f(x)=n\right\} and B_n=\left\{x\in\mathbb N\mid \nu_2(x)+1=n\right\}. By induction on n, we'll prove that A_n=B_n for all n\in\mathbb N. Interestingly enough, the base case n=1 is not trivial; at least, it's way more non-trivial than the actual induction step. Let's settle this case first. If f(1)=a\neq 1, then 1\in A_a, and it's meaningful to consider the set A_{a-1}. Because of surjectivity, this set is nonempty; so let x\in A_{a-1}. Since f(x)=f(1)\iff a-1=a doesn't hold, we must have f(x+1)=\min\{f(x),f(1)\}=\min\{a-1,a\}=a-1. Therefore x\in A_{a-1}\implies x+1\in A_{a-1}. Continuing ad infinitum, we see that all numbers from x onwards map to a-1, so f can only attain finitely many values; a contradiction to the surjectivity of f. So a=1 must hold. Now that we have figured out f(1)=1, let's see how many more values of f we can ascertain. Note that: For any x\in\mathbb N, f(x)=1=f(1)\implies f(x+1)\neq \min\{f(x),f(1)\}=1. In other words, x\in A_1\implies x+1\not\in A_1. On the other hand, if f(x)\neq 1=f(1), we must have f(x+1)=\min\{f(x),f(1)\}=\min\{f(x),1\}=1. Id est, x\not\in A_1\implies x+1\in A_1. These two points imply one thing; the elements of \mathbb N alternately occur and don't occur in A_1. Since 1 does occur in A_1, all odd numbers are in A_1, and none of the even numbers are in A_1; that is, A_1=B_1. Great thing. Next, suppose we have already proved A_1=B_1,\cdots, A_m=B_m. All the numbers of \mathbb N that haven't found a home in the A_i's yet are those divisible by 2^m. Let's now define a function g:\mathbb N\to\mathbb N as follows: g(n)=f(2^mn)-m. Note that this is a perfectly legit definition, because 2^mn\not\in B_i for any 1\le i\le m, hence it's not in any of the corresponding A_i's either, so f(2^mn)>m. This brand new function has some spectacular properties: g is surjective, since f takes all integer values>m for arguments divisible by 2^m; For any (a,b)\in\mathbb N^2, exactly one of the statements hold: g(a)=g(b) or g(a+b)=\min\{g(a),g(b)\}, because, meh, it's merely a scaled and shifted version of f. Now that's interesting; g satisfies the same conditions as f itself. So by the exact same analysis as the base case, one can show that g(n)=1\iff n is odd, i.e., f(n)=m+1\iff \nu_2(n)=m. In other words, A_{m+1}=B_{m+1},completing the induction step. The result proved above trivially implies \boxed{f(n)=\nu_2(n)+1}, which fortunately, satisfies the given conditions. \blacksquare
07.02.2017 19:48
randomusername wrote: We can actually solve the problem with the weaker condition that at least one of the two conditions is satisfied, i.e. f(a)\neq f(b)\implies f(a+b)=\min\{f(a),f(b)\}. Fix some positive integer M, and let m be the smallest value at which f(m) is at least M. Let f(m)=t. Then f(1),f(2),\dots,f(m-1)<M. We will now prove by induction that from now on, f(n)\ge t if m\mid n and else f(n)<M. (*) We will do this by looking at blocks of m. Note that f(m+n)=\min\{f(n),f(m)\}=f(n)<t if f(n)<t, call this (*). Because of (*), we cannot have m consecutive values of f which are <t, because then the next m values are also <t, and so on until infinity, which means f attains finitely many values, contradicting the surjectivity. Moreover, if f(km)\ge t for some positive integer k, then we have f(km+r)=\min\{f(r),f(km)\}=f(r)<M for 0<r<m. Now we cannot have f((k+1)m)<t as it would give m consecutive <t values, so f((k+1)m)\ge t. By induction, our claim is proven. Also, if we'd have M<t, then f wouldn't attain the value M, hence we must have t=M. This turns out to be enough to determine f. For i=1,2,3,\dots, denote b_i as the smallest positive integer for which f(b_i)=i. Because of the above, f(1) can only be 1, else all the values would be >1. Also, b_{i}\mid b_{i+1} because of the above, so let a_i=\frac{b_i}{b_{i-1}}\ge 2. Thus, b_1=1 and b_i=a_ia_{i-1}\dots a_2. Let j be the largest i such that b_i\mid n. Then b_j\mid n implies f(n)\ge j by (*). Also, f(n)<j+1 because b_{j+1}\not| n. So f(n)=j. This function satisfies our condition because if f(c)\neq f(d), say i=f(c)<f(d)=j, then f(c+d)=i=\min\{f(c),f(d)\} because b_i\mid c+d, but if b_{i+1}\mid c+d, then as b_{i+1}\mid b_j\mid d, we get b_{i+1}\mid c, false. To solve the MEMO problem from here, we just need to note that f(2n)\neq f(n), which follows from the MEMO problem's condition for a=b. how did you strike with that non trivial observation of the weaker condition.
18.02.2024 13:17
We claim the only solution is f(x) = \nu_2(x) + 1. Clearly this function does work. Now we prove it is the only one. We prove the same using induction. Base case (n = 1): Let m be the smallest number such that f(m) = 1. If m \ne 1, then clearly f(m+1) = \min\{f(1), f(m)\} = 1, and so on, i.e. f(x) = 1 \forall x \ge m. However, in this case, f would not be surjective. Therefore m = 1. Now we induct. If x is even and f(x-1) = 1, then f(1) = f(x-1) \implies f(x) \ne 1, and for odd x f(1) \ne f(x-1) \implies f(x) = f(1) = 1. Inductive step: Let the statement hold for n = 1, 2, \dots , k-1. We now show it holds for n = k. Let m_k be the smallest element such that f(m_k) = k. We claim that m_k = 2^{n-1}. Indeed, if this is not the case, f(m_k + p*2^{n-1}) = k \forall p \in \mathbb{N}in a similar argument as the base case, and so f would not be surjective. Now from a similar argument as the base case, if 2^n \mid x and f(x-2^{n-1}) = n, then f(x) \ne n, and if \nu_2(x) = n-1, and f(x-2^{n-1}) \ne n, then f(x) = n. \square.