Product of injective/surjective functions

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

w

22 users

TOPICS

B

No tags match your search

M

B

No tags match your search

M

Product of injective/surjective functions

G H J

Reveal topic tags

pigeonhole principle

algebra proposed

L

G H BBookmark kLocked kLocked NReply

Source: Romanian TST 2001

The post below has been deleted. Click to close.

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

1347 posts

WakeUp

#1 h Jan 16, 2011, 4:04 PM • 2 Y

Y by Adventure10, Mango247

a) Let $f,g:\mathbb{Z}\rightarrow\mathbb{Z}$ be one to one maps. Show that the function $h:\mathbb{Z}\rightarrow\mathbb{Z}$ defined by $h(x)=f(x)g(x)$ , for all $x\in\mathbb{Z}$ , cannot be a surjective function.

b) Let $f:\mathbb{Z}\rightarrow\mathbb{Z}$ be a surjective function. Show that there exist surjective functions $g,h:\mathbb{Z}\rightarrow\mathbb{Z}$ such that $f(x)=g(x)h(x)$ , for all $x\in\mathbb{Z}$ .

Z K Y

The post below has been deleted. Click to close.

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

1345 posts

#2 h Jan 16, 2011, 4:16 PM • 1 Y

Y by Adventure10

WakeUp wrote:

a) Let $f,g:\mathbb{Z}\rightarrow\mathbb{Z}$ be one to one maps. Show that the function $h:\mathbb{Z}\rightarrow\mathbb{Z}$ defined by $h(x)=f(x)g(x)$ , for all $x\in\mathbb{Z}$ , cannot be a surjective function.

Here is a solution.

Let $p_1,p_2,p_3,p_4,p_5$ be five distinct prime numbers. If $h$ is surjective, then for all $p_i, \: i=1,2,3,4,5$

there exist distinct integers $n_1,n_2,n_3,n_4,n_5$ satisfying $h(n_i)=p_i$

So, $f(n_i)g(n_i)=p_i$

Since $p_i$ 's are prime numbers, for all $i$ 's, either $|f(n_i)|=1$ or $|g(n_i)|=1$

So, by Pigeonhole Principle, either $f$ or $g$ takes the same value at different points, hence it cannot be one to one, and this finishes the proof.

Z K Y

The post below has been deleted. Click to close.

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

15142 posts

#3 h Jan 16, 2011, 5:10 PM • 3 Y

Y by Adventure10, Mango247, and 1 other user

b) There exists $x_0$ with $f(x_0) = 0$ ; Take $g(x_0) = h(x_0) = 0$ .
Enumerate the not-null integers as $n_1, n_2, \ldots$ . Let $A_0 = \{x_0\}$ . For $k\geq 1$ perform the following, starting with $k=1$ .

The set $F_k = \{ x \in \mathbb{Z} \ ; \ n_k \mid f(x)\}$ is infinite. Take $x_k \in F_k \setminus A_{k-1}$ , define $g(x_k) = n_k$ , $h(x_k) = f(x_k)/g(x_k)$ , and $B_{k-1} = A_{k-1} \cup \{x_k\}$ . Then take $y_k \in F_k \setminus B_{k-1}$ , define $h(y_k) = n_k$ , $g(x_k) = f(x_k)/h(x_k)$ , and $A_k = B_{k-1} \cup \{y_k\}$ .

The sets $A_k$ are always finite, so the procedure may continue indefinitely. This ensures that the functions $g$ and $h$ take all integer values when $x$ runs over $\bigcup_{k\geq 0} A_k$ , while always having $f(x) = g(x)h(x)$ .
For any $x \in \mathbb{Z} \setminus \bigcup_{k\geq 0} A_k$ (if not empty), take $g(x) = 1$ and $h(x)=f(x)$ (or any such combination of values as to have $f(x) = g(x)h(x)$ ).

Z K Y

The post below has been deleted. Click to close.

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

437 posts

#4 h Feb 9, 2024, 4:15 AM

Y by

(a) Suppose for the sake of contradiction that $h$ is surjective. Take five distinct prime numbers $p_1, p_2, p_3, p_4, p_5$ and five distinct integers $a_1, a_2, a_3, a_4, a_5$ such that $h(a_i) = p_i$ for all $1 \leq i \leq 5$ . For each $i$ , we clearly must have $(f(a_i), g(a_i)) \in \{(1, p_i), (-1, -p_i), (p_i, 1), (-p_i, -1)\}$ only, so by pigeonhole principle two of the tuples $(f(a_i), g(a_i))$ must coincide, implying that $f$ and $g$ are not bijective, a contradiction.

(b) We will first give an algorithm to construct surjective functions $p$ , $q$ such that $x = p(x) q(x)$ for all integers $x$ . Let $p(0) = q(0) = 0$ .

Let $\mathcal{S}$ be the empty set, and set $i = 1$ initially. Now let $u, v$ be the two smallest positive multiples of $i$ greater than $\operatorname{max} \mathcal{S}$ , and let $p(u) = q(v) = i$ , $q(u) = \frac{u}{i}$ , $p(v) = \frac{v}{i}$ , after which we add $u$ and $v$ to $\mathcal{S}$ . Similarly, for negative numbers we let $\mathcal{S}$ be the empty set $i = -1$ and $u, v$ be the two largest negative multiples of $i$ less than $\operatorname{min} \mathcal{S}$ , and we proceed similarly. For all $p(i), q(i)$ not defined by this procedure we can simply set those values to be anything satisfying $p(i) q(i) = i$ .

Now just setting $g(i) = p(j)$ and $h(i) = q(j)$ where $j$ is defined as $f(i)$ works.

Z K Y

The post below has been deleted. Click to close.

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

1437 posts

Jndd

#5 h Jul 26, 2024, 4:39 PM

Y by

(a) The answer is no. Suppose that $h$ is surjective, so $x,y,z$ exist such that $h(x)$ , $h(y)$ , and $h(z)$ are three distinct primes. Then, three of $f(x), f(y), f(z), g(x), g(y), g(z)$ must be $1$ . However, since $f$ and $g$ are both bijective, this is a contradiction.

(b) The answer is yes. We can simply assign values to $f$ and $g$ to make this work. Suppose for any $N\in \mathbb{Z}$ , no $t$ has been chosen yet such that $f(t)=N$ . Since there are infinitely many multiples of $N$ and we have assigned only a finite number of values to $f$ and $g$ so far, we can simply select a $t$ such that $h(t)=Nk$ such that $f(x)g(x)\neq Nk$ for any previous assignments of $f$ and $g$ , so now we can let $f(t)=N$ and $g(t)=k$ . Since we can repeat these steps with $f$ and $g$ indefinitely, we are able to force $f$ and $g$ to be surjective.

Z K Y

The post below has been deleted. Click to close.

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

1 post

#6 h Jul 26, 2024, 6:19 PM

Y by

b) I will put my functions here:
h(n)=\left\{ \begin{array}{ccc}
0 & \text{if} & f(n)=0
-1 & \text{if} & f(n)=1
3 & \text{if} & f(n)=3
\sqrt{f(n)} & \text{if} & \exists k\in\mathbb{Z}:k^2=f(n)
-k & \text{if} & \exists k\in\mathbb{Z}^{+}:k(k+1)=f(n)
1 & \text{else}
\end{array}\right.

g(n)=\left\{ \begin{array}{ccc}
0 & \text{if} & f(n)=0
-1 & \text{if} & f(n)=1
1 & \text{if} & f(n)=3
\sqrt{f(n)} & \text{if} & \exists k\in\mathbb{Z}:k^2=f(n)
-(k+1) & \text{if} & \exists k\in\mathbb{Z}^{+}:k(k+1)=f(n)
n & \text{else}
\end{array}\right.

all the if's here are "else if", meaning you go from top to bottom until the condition on the right is right, then you look at the left side and figure out what the output is supposed to be

(aops does not allow me to use latex so put it in a latex decoder)

This post has been edited 3 times. Last edited by MrCoolNerd, Jul 26, 2024, 6:56 PM

Z K Y

The post below has been deleted. Click to close.

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

591 posts

#7 h Mar 17, 2025, 5:15 PM

Y by

a) Observe that $h(x)$ attains all primes, meaning that either $f(x)$ or $g(x)$ must attain $1$ or $-1$ at infinitely many values, a contradiction. Thus the answer is no.

b) Observe that if we want $f(x)=k$ for some $k$ as there are infinitely many multiples of $k$ that $g(x)$ can attain we can use one of them to get $f(x)=k,$ and create $g(x)$ accordingly. We can use the same argument for $g(x).$ Thus the answer is yes.

Z K Y

The post below has been deleted. Click to close.

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

3113 posts

#8 h Jun 6, 2025, 9:43 PM

Y by

Solution

This post has been edited 1 time. Last edited by lpieleanu, Jun 6, 2025, 9:43 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a