Surjective function

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

soruz

1067 posts

soruz

#1 h Jun 8, 2011, 7:22 PM • 7 Y

Y by Amir Hossein, Wizard_32, Math_olympics, dragonbreath3, Adventure10, Mango247, and 1 other user

Find all surjective functions $f:\mathbb{N}\to\mathbb{N}$ if $f (n) \ge n+(-1)^n, \forall n \in \mathbb{N}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pco

23514 posts

pco

#2 h Jun 9, 2011, 6:16 AM • 5 Y

Y by Amir Hossein, Math_olympics, Adventure10, Mango247, and 1 other user

soruz wrote:

Find all surjective functions $f:\mathbb{N}\to\mathbb{N}$ if $f (n) \ge n+(-1)^n, \forall n \in \mathbb{N}$ .

Let $S_n$ be the set of natural numbers solutions of the equation $x+(-1)^x\le n$ :
Obviously, this set is the set of all even numbers $\le n-1$ and all odd numbers $\le n+1$ and so :

$S_{2p}=\{1,2,3,...,2p-1,2p+1\}$
$S_{2p+1}=\{1,2,3,...,2p+1\}$

So $S_1=\{1\}$ and so $f(1)=1$

We clearly have $f^{-1}([1,n])\subseteq\bigcup_{k\in[1,n]}S_k$
So $f^{-1}([1,2p])\subseteq \{1,2,3,...,2p-1,2p+1\}$
And $f^{-1}([1,2p+1])\subseteq \{1,2,3,...,2p+1\}$

So $|f^{-1}([1,n])|=n$ and this implies that $f^{-1}(\{n\})=f^{-1}([1,n])\setminus f^{-1}([1,n-1])$

Hence the unique solution :
$f(1)=1$
$f(2p)=2p+1$ $\forall p\ge 1$
$f(2p+1)=2p$ $\forall p\ge 1$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

andreass

25 posts

andreass

#3 h May 19, 2012, 4:17 PM • 8 Y

Y by esi, nicky-glass, Wizard_32, Amir Hossein, othman, Mathmick51, Adventure10, Mango247

We otherwise use induction which is fairly simple.
First easily prove $f(1)=1, f(2)=3, f(3)=2$ .
Then assume that for some $k \in \mathbb{N} , \forall n \in \mathbb{N}, 1 \le n \le k, f(2k)=2k+1$ and $f(2k+1)=2k$ .
Then the equations $f(x)=2k+2$ and $f(y)=2k+3$ both have solutions since the function is surjective and obviously $x \neq y$ .
However $\forall n \ge k+2, f(2n) \ge 2n+1 \ge 2k+5$ and $f(2n+1) \ge 2n+1-1\ge 2k+4$ hence $x,y \in \{2k+2,2k+3\}$ . But we know $f(2k+2) \ge 2k+3$ therefore $x \neq 2k+2 \Rightarrow x=2k+3 \Rightarrow y=2k+2$ .
And by induction we have proved that the solution to the functional equation is:
$f(n)=\begin{cases}1 &\textrm{ if } n=1\\ n+1 &\textrm{ if } n \equiv 0\pmod 2,\\ n-1 &\textrm{ if } n \equiv 1\pmod 2\end{cases}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Chirantan

579 posts

Chirantan

#4 h Apr 9, 2015, 12:47 PM • 2 Y

Y by Math_olympics, Adventure10

andreass wrote:

We otherwise use induction which is fairly simple.
First easily prove $f(1)=1, f(2)=3, f(3)=2$ .
Then assume that for some $k \in \mathbb{N} , \forall n \in \mathbb{N}, 1 \le n \le k, f(2k)=2k+1$ and $f(2k+1)=2k$ .
Then the equations $f(x)=2k+2$ and $f(y)=2k+3$ both have solutions since the function is surjective and obviously $x \neq y$ .
However $\forall n \ge k+2, f(2n) \ge 2n+1 \ge 2k+5$ and $f(2n+1) \ge 2n+1-1\ge 2k+4$ hence $x,y \in \{2k+2,2k+3\}$ . But we know $f(2k+2) \ge 2k+3$ therefore $x \neq 2k+2 \Rightarrow x=2k+3 \Rightarrow y=2k+2$ .
And by induction we have proved that the solution to the functional equation is:
$f(n)=\begin{cases}1 &\textrm{ if } n=1\\ n+1 &\textrm{ if } n \equiv 0\pmod 2,\\ n-1 &\textrm{ if } n \equiv 1\pmod 2\end{cases}$

How do I proove $f(1)=1, f(2)=3, f(3)=2$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AE-TheRocket

51 posts

AE-TheRocket

#5 h Sep 10, 2016, 3:33 PM • 3 Y

Y by Math_olympics, Adventure10, Mango247

But as the function is surjective , $0$ must have an inverse which seems to be omitted in both solutions! am i wrong ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pco

23514 posts

pco

#6 h Sep 10, 2016, 3:43 PM • 3 Y

Y by AE-TheRocket, Adventure10, Mango247

AE-TheRocket wrote:

But as the function is surjective , $0$ must have an inverse which seems to be omitted in both solutions! am i wrong ?

As usual in this international forum, the set $\mathbb N$ is considered as the set of all positive integers (and so $0\notin\mathbb N$ ).

We all know that in some countries (mine, for example, and likely yours), the convention is that $0\in\mathbb N$ . But since convention is different in each country, a kind of commun choice must be done on such an international forum.

The best thing to do would generally be to add the definition of $\mathbb N$ in each problem using it.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

i_am_not_the_one_who

2 posts

i_am_not_the_one_who

#7 h Apr 20, 2017, 12:40 PM • 2 Y

Y by Adventure10, Mango247

How about trigonometric functions like x+cos(pi*x) and x-sin((2x-1)pi/2)? Do we usually neglect solutions of this type?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pco

23514 posts

pco

#8 h Apr 20, 2017, 1:06 PM • 3 Y

Y by Math_olympics, Adventure10, Mango247

i_am_not_the_one_who wrote:

How about trigonometric functions like x+cos(pi*x) and x-sin((2x-1)pi/2)? Do we usually neglect solutions of this type?

Considering $\mathbb N$ as the set of positive integers, none of these two functions (which are the same, in fact) is a surjective function from $\mathbb N\to\mathbb N$ , as required.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

omarius

91 posts

omarius

#9 h Jun 18, 2017, 10:12 PM • 3 Y

Y by Math_olympics, Adventure10, Mango247

please how can we prove that f(1)=1 ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Delray

348 posts

Delray

#10 h Jul 23, 2017, 9:55 PM • 3 Y

Y by Math_olympics, Adventure10, Mango247

omarius wrote:

please how can we prove that f(1)=1 ?

We have that $f(1)\geq 0$ . Similarly, $f(2)\geq3$ and $f(3)\geq 2$ . Since $f$ is surjective, there must be some value $x$ , such that $f(x)=1$ , and since one is the only possible value in this range, we must have that $f(1)=1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

omarius

91 posts

omarius

#11 h Jul 29, 2017, 10:08 AM • 1 Y

Y by Adventure10

pco wrote:

soruz wrote:

Find all surjective functions $f:\mathbb{N}\to\mathbb{N}$ if $f (n) \ge n+(-1)^n, \forall n \in \mathbb{N}$ .

Let $S_n$ be the set of natural numbers solutions of the equation $x+(-1)^x\le n$ :
Obviously, this set is the set of all even numbers $\le n-1$ and all odd numbers $\le n+1$ and so :

$S_{2p}=\{1,2,3,...,2p-1,2p+1\}$
$S_{2p+1}=\{1,2,3,...,2p+1\}$

So $S_1=\{1\}$ and so $f(1)=1$

We clearly have $f^{-1}([1,n])\subseteq\bigcup_{k\in[1,n]}S_k$
So $f^{-1}([1,2p])\subseteq \{1,2,3,...,2p-1,2p+1\}$
And $f^{-1}([1,2p+1])\subseteq \{1,2,3,...,2p+1\}$

So $|f^{-1}([1,n])|=n$ and this implies that $f^{-1}(\{n\})=f^{-1}([1,n])\setminus f^{-1}([1,n-1])$

Hence the unique solution :
$f(1)=1$
$f(2p)=2p+1$ $\forall p\ge 1$
$f(2p+1)=2p$ $\forall p\ge 1$

can you please clarify this solution? it's beautiful but i haven't managed yes to get it fully
thank you

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pco

23514 posts

pco

#12 h Jul 29, 2017, 10:12 AM • 2 Y

Y by Math_olympics, Adventure10

omarius wrote:

can you please clarify this solution? it's beautiful but i haven't managed yes to get it fully

Dont hesitate to indicate what is the first line you dont understand.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Anis2017

87 posts

Anis2017

#13 h Feb 4, 2018, 4:36 PM • 2 Y

Y by Math_olympics, Adventure10

i havn't understood nothing
can you explain more please?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

EmathB

1 post

EmathB

#14 h Jan 21, 2020, 7:32 PM • 2 Y

Y by Math_olympics, Adventure10

can you explain me the line : We clearly have...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pco

23514 posts

pco

#15 h Jan 22, 2020, 9:11 AM • 2 Y

Y by Math_olympics, Adventure10

EmathB wrote:

can you explain me the line : We clearly have...

$f(x)\le n$ $\implies$ $x+(-1)^x\le f(x)\le n$ $\implies$ $x+(-1)^x=k$ for some $k\le n$ $\implies$ $x\in S_k$ for some $k\in\{1,2,...,n\}$

So $f(x)\le n$ $\implies$ $x\in\bigcup_{k\in[1,n]}S_k$

So $f^{-1}([1,n])\subseteq \bigcup_{k\in[1,n]}S_k$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

BroBro561

7 posts

BroBro561

#17 h Feb 2, 2021, 11:48 AM • 1 Y

Y by Math_olympics

Actually f(n) = n+1 applies for all values of n, either even or odd. How f(1) is equal to 1. Is not f(1) is equal to or greater than 0. And, f(n) = n-1 for odd numbers, and f(n) is equal to or greater than n-1 for even and odd numbers. So, f(n) = n+1 and f(n) are greater than or equal to n-1 are the only solutions. Right? Can anyone please evaluate what I said ???

This post has been edited 1 time. Last edited by BroBro561, Feb 2, 2021, 11:51 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pco

23514 posts

pco

#18 h Feb 2, 2021, 12:36 PM • 1 Y

Y by Math_olympics

BroBro561 wrote:

Actually f(n) = n+1 applies for all values of n, either even or odd. How f(1) is equal to 1. Is not f(1) is equal to or greater than 0. And, f(n) = n-1 for odd numbers, and f(n) is equal to or greater than n-1 for even and odd numbers. So, f(n) = n+1 and f(n) are greater than or equal to n-1 are the only solutions. Right? Can anyone please evaluate what I said ???

I did not quite understand your post.
What is sure is that $f(n)=n+1$ $\forall n\in\mathbb Z_{>0}$ is not a solution since it is not surjective, as required (there exists no positive integer such that $f(n)=1$ with this proposed solution).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

BroBro561

7 posts

BroBro561

#19 h Feb 6, 2021, 4:12 PM • 2 Y

Y by Math_olympics, Mango247

pco wrote:

BroBro561 wrote:

Actually f(n) = n+1 applies for all values of n, either even or odd. How f(1) is equal to 1. Is not f(1) is equal to or greater than 0. And, f(n) = n-1 for odd numbers, and f(n) is equal to or greater than n-1 for even and odd numbers. So, f(n) = n+1 and f(n) are greater than or equal to n-1 are the only solutions. Right? Can anyone please evaluate what I said ???

I did not quite understand your post.
What is sure is that $f(n)=n+1$ $\forall n\in\mathbb Z_{>0}$ is not a solution since it is not surjective, as required (there exists no positive integer such that $f(n)=1$ with this proposed solution).

I mean that f(x) = x +1 is the solution since if you made a table of domains, you will notice that a domain of odd numbers has a solution of f(x) is greater than or equal to x -1 while a domain of even numbers has a solution of f(x) is greater than or equal to x +1. So, to satisfy these conditions f(x)is greater than or equal to x +1 satisfies the conditions of the odd and even numbers. Did you understand what I say ?? In addition, x+1 is bijective, which is both injective and surjective. How f(x) = x+1 is not surjective ?? Moreover, there is someone who posted the same solution as I did but with different words..

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pco

23514 posts

pco

#21 h Feb 6, 2021, 4:24 PM • 1 Y

Y by Mango247

BroBro561 wrote:

How f(x) = x+1 is not surjective ??.

Have you simply read my previous post ?
The explanation of " $f(x)=x+1$ is not surjective" was clearly written :
(there exists no positive integer such that $f(n)=1$ with this proposed solution

Remember we are from $\mathbb Z_{>0}\to\mathbb Z_{>0}$ (and if you prefer $N=\mathbb Z_{\ge 0}$ , then there exists no nonnegative integer such that $f(n)=0$ with this proposed solution).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

BroBro561

7 posts

BroBro561

#23 h Feb 6, 2021, 8:11 PM • 2 Y

Y by Math_olympics, Mango247

pco wrote:

BroBro561 wrote:

How f(x) = x+1 is not surjective ??.

Have you simply read my previous post ?
The explanation of " $f(x)=x+1$ is not surjective" was clearly written :
(there exists no positive integer such that $f(n)=1$ with this proposed solution

Remember we are from $\mathbb Z_{>0}\to\mathbb Z_{>0}$ (and if you prefer $N=\mathbb Z_{\ge 0}$ , then there exists no nonnegative integer such that $f(n)=0$ with this proposed solution).

Actually, I pressed on your link, and it did not work. Can you resend it?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pco

23514 posts

pco

#24 h Feb 7, 2021, 7:58 AM • 3 Y

Y by Aritra12, Math_olympics, Mango247

BroBro561 wrote:

Actually, I pressed on your link, and it did not work. Can you resend it?

I posted no link at all. Just direct clear understandable (I think) texts.
Just read. No need to press everywhere on your screen.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pco

23514 posts

pco

#25 h Feb 7, 2021, 8:03 AM • 2 Y

Y by Math_olympics, Mango247

I repost my previous post, deleted for some unknown reason (without any explanation message for me

, quite impressive mod behaviour !) :

Basicaly, surjectivity is " $f(\text{domain})=\text{codomain}$ "

So it depends not only on the expression of $f(x)$ , but also on domain and codomain :

$f(x)=x^2$ is a surjection from $\mathbb R\to\mathbb R_{\ge 0}$
But $f(x)=x^2$ is a not surjection from $\mathbb R\to\mathbb R$

$f(x)=x$ is a surjection from $\mathbb N\to\mathbb N$
But $f(x)=x$ is not a surjection from $\mathbb N\to\mathbb Z$

$f(x)=2x$ is a surjection from $\mathbb R\to\mathbb R$
But $f(x)=2x$ is not a surjection from $\mathbb Z\to\mathbb Z$

And, here :
$f(x)=x+1$ is a surjection from $\mathbb Z\to\mathbb Z$
But $f(x)=x+1$ is not a surjection from $\mathbb Z_{>0}\to\mathbb Z_{>0}$ (which is the problem statement)
And $f(x)=x+1$ is not a surjection from $\mathbb Z_{\ge 0}\to\mathbb Z_{\ge 0}$
But $f(x)=x+1$ is a surjection from $\mathbb Z_{\ge 0}\to\mathbb Z_{> 0}$

For the fun, note that $f(x)$ is always a surjection from its domain in its image

This post has been edited 2 times. Last edited by pco, Feb 8, 2021, 6:49 AM
Reason: Typos (surjection -> bijection)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

BroBro561

7 posts

BroBro561

#26 h Feb 7, 2021, 6:26 PM • 2 Y

Y by Math_olympics, Mango247

pco wrote:

I repost my previous post, deleted for some unknown reason (without any explanation message for me

, quite impressive mod behaviour !) :

Basicaly, surjectivity is " $f(\text{domain})=\text{codomain}$ "

So it depends not only on the expression of $f(x)$ , but also on domain and codomain :

$f(x)=x^2$ is a surjection from $\mathbb R\to\mathbb R_{\ge 0}$
But $f(x)=x^2$ is a not surjection from $\mathbb R\to\mathbb R$

$f(x)=x$ is a surjection from $\mathbb N\to\mathbb N$
But $f(x)=x$ is not a surjection from $\mathbb N\to\mathbb Z$

$f(x)=2x$ is a surjection from $\mathbb R\to\mathbb R$
But $f(x)=2x$ is not a surjection from $\mathbb Z\to\mathbb Z$

And, here :
$f(x)=x+1$ is a surjection from $\mathbb Z\to\mathbb Z$
But $f(x)=x+1$ is not a bijection from $\mathbb Z_{>0}\to\mathbb Z_{>0}$ (which is the problem statement)
And $f(x)=x+1$ is not a bijection from $\mathbb Z_{\ge 0}\to\mathbb Z_{\ge 0}$
But $f(x)=x+1$ is a bijection from $\mathbb Z_{\ge 0}\to\mathbb Z_{> 0}$

For the fun, note that $f(x)$ is always a surjection from its domain in its image

So, after all, is the solution I posted incorrect? I ask because I am a beginner to math olympiad problem- solving ... Is my answer a wort try or not ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pco

23514 posts

pco

#27 h Feb 7, 2021, 6:39 PM • 1 Y

Y by Math_olympics

BroBro561 wrote:

So, after all, is the solution I posted incorrect? I ask because I am a beginner to math olympiad problem- solving ... Is my answer a wort try or not ?

Yes, your solution is indeed incorrect : the question is to find all surjective functions from $\mathbb Z_{>0}\to\mathbb Z_{>0}$ which match the given equation and your solution ( $f(x)=x+1$ ) is not a surjective function from $\mathbb Z_{>0}\to\mathbb Z_{>0}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

BroBro561

7 posts

BroBro561

#28 h Feb 7, 2021, 7:02 PM • 1 Y

Y by Math_olympics

Chirantan wrote:

andreass wrote:

We otherwise use induction which is fairly simple.
First easily prove $f(1)=1, f(2)=3, f(3)=2$ .
Then assume that for some $k \in \mathbb{N} , \forall n \in \mathbb{N}, 1 \le n \le k, f(2k)=2k+1$ and $f(2k+1)=2k$ .
Then the equations $f(x)=2k+2$ and $f(y)=2k+3$ both have solutions since the function is surjective and obviously $x \neq y$ .
However $\forall n \ge k+2, f(2n) \ge 2n+1 \ge 2k+5$ and $f(2n+1) \ge 2n+1-1\ge 2k+4$ hence $x,y \in \{2k+2,2k+3\}$ . But we know $f(2k+2) \ge 2k+3$ therefore $x \neq 2k+2 \Rightarrow x=2k+3 \Rightarrow y=2k+2$ .
And by induction we have proved that the solution to the functional equation is:
$f(n)=\begin{cases}1 &\textrm{ if } n=1\\ n+1 &\textrm{ if } n \equiv 0\pmod 2,\\ n-1 &\textrm{ if } n \equiv 1\pmod 2\end{cases}$

How do I proove $f(1)=1, f(2)=3, f(3)=2$ .

But is not my solution ,pco, the same as what Chirantan wrote ? That n+1 is for even integers and n-1 is for odd integers

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pco

23514 posts

pco

#29 h Feb 8, 2021, 5:13 AM • 1 Y

Y by Math_olympics

BroBro561 wrote:

But is not my solution ,pco, the same as what Chirantan wrote ? That n+1 is for even integers and n-1 is for odd integers

BroBro561 wrote:

Actually f(n) = n+1 applies for all values of n, either even or odd.

??????????? Same solution ? ?????????

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

BroBro561

7 posts

BroBro561

#30 h Feb 9, 2021, 6:52 PM

Y by

pco wrote:

BroBro561 wrote:

So, after all, is the solution I posted incorrect? I ask because I am a beginner to math olympiad problem- solving ... Is my answer a wort try or not ?

Yes, your solution is indeed incorrect : the question is to find all surjective functions from $\mathbb Z_{>0}\to\mathbb Z_{>0}$ which match the given equation and your solution ( $f(x)=x+1$ ) is not a surjective function from $\mathbb Z_{>0}\to\mathbb Z_{>0}$ .

How is that !? If you put any domain( which is greater than one), in this function, a range greater than one will show a result! I still do not understand how they function I wrote is not surjective? In addition, is there any formal source that gives a solution to this functional equation

This post has been edited 1 time. Last edited by BroBro561, Feb 9, 2021, 6:53 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

IAmTheHazard

5001 posts

IAmTheHazard

#31 h Feb 9, 2021, 6:57 PM • 2 Y

Y by centslordm, Mango247

From wikipedia: "In mathematics, a function f from a set X to a set Y is surjective (also known as onto, or a surjection), if for every element y in the codomain Y of f, there is at least one element x in the domain X of f such that f(x) = y."
In this case, $f(x)=x+1$ from $\mathbb{Z}_{>0} \to \mathbb{Z}_{>0}$ is not surjective because there does not exist $x \in \mathbb{Z}_{>0}$ such that $f(x)=1$ , since that implies $x=0$ and $0 \not \in \mathbb{Z}_{>0}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

BroBro561

7 posts

BroBro561

#32 h Feb 9, 2021, 9:18 PM • 2 Y

Y by Mango247, Mango247

IAmTheHazard wrote:

From wikipedia: "In mathematics, a function f from a set X to a set Y is surjective (also known as onto, or a surjection), if for every element y in the codomain Y of f, there is at least one element x in the domain X of f such that f(x) = y."
In this case, $f(x)=x+1$ from $\mathbb{Z}_{>0} \to \mathbb{Z}_{>0}$ is not surjective because there does not exist $x \in \mathbb{Z}_{>0}$ such that $f(x)=1$ , since that implies $x=0$ and $0 \not \in \mathbb{Z}_{>0}$ .

IAmTheHazard wrote:

From wikipedia: "In mathematics, a function f from a set X to a set Y is surjective (also known as onto, or a surjection), if for every element y in the codomain Y of f, there is at least one element x in the domain X of f such that f(x) = y."
In this case, $f(x)=x+1$ from $\mathbb{Z}_{>0} \to \mathbb{Z}_{>0}$ is not surjective because there does not exist $x \in \mathbb{Z}_{>0}$ such that $f(x)=1$ , since that implies $x=0$ and $0 \not \in \mathbb{Z}_{>0}$ .

Oh, thanks a lot. I now understood why it is not surjective!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AshAuktober

1007 posts

AshAuktober

#33 h Jun 21, 2024, 11:52 AM

Y by

We claim the required solution set is
$f(x) = \begin{cases} 1, & \text{if } x = 1 \\ 2p, & \text{if } x = 2p+1, \text{ for each } p \in \mathbb{N} \\ 2p+1, & \text{if } x = 2p \end{cases}$
The proof is by induction.

Note that $f(x) = 1 \implies x + (-1)^x \leq 1 \implies x \equiv 1 \pmod{2}$ , $x = 1$ . But since $f$ is surjective, $f(x) = 1 \iff x = 1$ . Similarly, one can prove $f(2) = 3$ , $f(3) = 2$ .

Now we prove that given $f(x)$ as
$f(x) = \begin{cases} 1, & \text{if } x = 1 \\ 2p, & \text{if } x = 2p+1, \text{ for } p = 1, 2, \cdots, m \\ 2p+1, & \text{if } x = 2p \end{cases}$ we can prove the same for $p = m+1$ .

Indeed, consider $x$ such that $f(x) = 2p+2$ . Then
$\begin{cases} x \leq 2p+1, x \equiv 0 \pmod{2} \\ x \leq 2p+3, x \equiv 1 \pmod{2} \end{cases}$ But now notice that the first one isn't possible as all values of $f(x)$ for $x \leq 2p+1$ have been found not equal to $2p+2$ . So $x \leq 2p+3 \implies x = 2p+2 \pmod{2}$ .

But now all for the odd values of $x \leq 2p+3$ , $f(x)$ has been discovered, so $x \leq 2p+3$ . Therefore, $f(2p+2) = 2p+3$ , $f(2p+3) = 2p+2$ and the induction is complete. $\square$

Z K Y