f = 1 or f(x) = x?

Redacted

bnumbertheory wrote: math_comb01 wrote: A finite set $\mathcal{S}$ of positive integers is called cardinal if $\mathcal{S}$ contains the integer $|\mathcal{S}|$ where $|\mathcal{S}|$ denotes the number of distinct elements in $\mathcal{S}$. Let $f$ be a function from the set of positive integers to itself such that for any cardinal set $\mathcal{S}$, the set $f(\mathcal{S})$ is also cardinal. Here $f(\mathcal{S})$ denotes the set of all integers that can be expressed as $f(a)$ where $a \in \mathcal{S}$. Find all possible values of $f(2024)$ Does this work or am I misunderstanding the problem? We see that $f(\mathcal{S}) \equiv \{ 1\}$ is trivially a solution. Assume non-constant functions $f$. We claim that $f(x) = x$ is the only such solution. We induct on $|\mathcal{S}|$. Consider $\mathcal{S} = \{ 1 \}$. It follows that $|f(\mathcal{S})| = 1$ which forces $f(1) = 1$. Let $f(x) = x$ for all $x \leq n$. Consider $\mathcal{S} = \{ 1, 2 \dots n+1 \}$. It is cardinal. Thus, $f(\mathcal{S}) = \{ 1, 2, 3 \dots n, f(n+1) \}$ is also cardinal, which forces $f(n+1) = n+1$. It does not. I fakesolved in a similar way. I'll tell why a bit later.

kamatadu wrote: bnumbertheory wrote: math_comb01 wrote: A finite set $\mathcal{S}$ of positive integers is called cardinal if $\mathcal{S}$ contains the integer $|\mathcal{S}|$ where $|\mathcal{S}|$ denotes the number of distinct elements in $\mathcal{S}$. Let $f$ be a function from the set of positive integers to itself such that for any cardinal set $\mathcal{S}$, the set $f(\mathcal{S})$ is also cardinal. Here $f(\mathcal{S})$ denotes the set of all integers that can be expressed as $f(a)$ where $a \in \mathcal{S}$. Find all possible values of $f(2024)$ Does this work or am I misunderstanding the problem? We see that $f(\mathcal{S}) \equiv \{ 1\}$ is trivially a solution. Assume non-constant functions $f$. We claim that $f(x) = x$ is the only such solution. We induct on $|\mathcal{S}|$. Consider $\mathcal{S} = \{ 1 \}$. It follows that $|f(\mathcal{S})| = 1$ which forces $f(1) = 1$. Let $f(x) = x$ for all $x \leq n$. Consider $\mathcal{S} = \{ 1, 2 \dots n+1 \}$. It is cardinal. Thus, $f(\mathcal{S}) = \{ 1, 2, 3 \dots n, f(n+1) \}$ is also cardinal, which forces $f(n+1) = n+1$. It does not. I fakesolved in a similar way. I'll tell why a bit later. Nvm I am high. Got it. Let me solve it now.

math_comb01 wrote: A finite set $\mathcal{S}$ of positive integers is called cardinal if $\mathcal{S}$ contains the integer $|\mathcal{S}|$ where $|\mathcal{S}|$ denotes the number of distinct elements in $\mathcal{S}$. Let $f$ be a function from the set of positive integers to itself such that for any cardinal set $\mathcal{S}$, the set $f(\mathcal{S})$ is also cardinal. Here $f(\mathcal{S})$ denotes the set of all integers that can be expressed as $f(a)$ where $a \in \mathcal{S}$. Find all possible values of $f(2024)$ What can the function $f(x) = 1$ for all $x \neq c$ and $f(x) = 2$ for $x = c$ for some $c \neq 1$ work?

What if $f(1, \dots, 2023) = 1$ and $f(2024) = 2$?

The answer is $f(2024)=1,2,2024$ which can be proved by lots of casework.

Maybe the easiest question. Dies to observation. $f(x)=1$ gives a cardinal set every time. This is rather easy to note. Let's take $f(x) \neq c$. Let's consider the set $S=\{1\}$. This forces $f(1)=1$. Let's now consider the set $S=\{a,2\}$ where $a \neq 2$. This means either $f(a)=2$ or $f(2)=2$ but not both. As $a$ can be any real number, this is claiming that $f(x)=2, x \neq 2$ which will be false the moment we consider $S=\{a,b,3\}$. Thus, we have $f(2)=2$. Similarly, thus we will have $f(x)=x$ as a solution. Finally, $f(x)=1, x \in [1,2023] \cup [2025, \infty]$ and $f(2024)=2$ also works. We cannot repeat this for more numbers as the set $(a,2)$ will get violated. Thus, $f(2024)=1,2,2024$.

Proposed by Sutanay Bhattacharya

ATGY wrote: What if $f(1, \dots, 2023) = 1$ and $f(2024) = 2$? I have changed my answer.

Anulick wrote: ATGY wrote: What if $f(1, \dots, 2023) = 1$ and $f(2024) = 2$? What if $f(1, \dots, 2022) = 1; f(2023)=2$ and $f(2024) = 3$? We can then have it take any value from 1 to 2024. This doesn't satisfy the properties of the problem.

math_comb01 wrote: The answer is $f(2024)=1,2,2024$ which can be proved by lots of casework. I have got the same answer as this

Anulick wrote: Maybe the easiest question. Dies to observation. $f(x)=1$ gives a cardinal set every time. This is rather easy to note. Let's take $f(x) \neq c$. Let's consider the set $S=\{1\}$. This forces $f(1)=1$. Let's now consider the set $S=\{a,2\}$ where $a \neq 2$. This means either $f(a)=2$ or $f(2)=2$ but not both. As $a$ can be any real number, this is claiming that $f(x)=2, x \neq 2$ which will be false the moment we consider $S=\{a,b,3\}$. Thus, we have $f(2)=2$. Similarly, thus we will have $f(x)=x$ as a solution. Finally, $f(x)=1, x \in [1,2023] \cup [2025, \infty]$ and $f(2024)=2$ also works. We cannot repeat this for more numbers as the set $(a,2)$ will get violated. Thus, $f(2024)=1,2,2024$. What if $f(2) = f(a) = 1$?

wrong btw

Solved with Anchovy. The answer is $\boxed{1,2,2024}$. The construction for $1$ is $f\equiv 1$, the construction for $2$ is $f(x) = 1\forall x \ne 2024$ and $f(2024) = 2$, and the construction for $2024$ is $f(x) = x$. We can check that these work. Now we prove they are the only possibilities for $f(2024)$. Suppose we had $f(2024) \not \in \{1,2,2024\}$. Then $f$ isn't constant or identity. Let $f(2024) = n$. By choosing $S = \{1\}$, we see that $f(1) = 1$. Let $k$ be the smallest positive integer with $f(k) \ne k$. Clearly $k \le 2024$. Consider the cardinal set $\{1,2,\ldots, k\}$. We must have $\{1, 2, \ldots, k - 1, f(k)\}$ cardinal, so $f(k) < k$ (because if $f(k) > k$ it would have $k$ elements but not the element $k$). Now for any $m > k$, we may consider the set $S = \{1, 2, \ldots, k, m \} \setminus \{f(k)\}$. Notice that this set must be cardinal, so the set $f(S) = \{1, 2, \ldots, k-1, f(m)\}$ is also cardinal. This implies that $f(m) \le k$ for each $m > k$. In particular we have $2< n < 2024$. Now, since $ 2< n \le k$, we have $1, 2, \ldots, n-2, n, 2024$ is cardinal. Since $1, 2, \ldots, n - 2$ are fixed points, we have $1, 2, \ldots, n - 2, f(n), n$ is cardinal. If $n < k$, then $f(n) = n$, so $1, 2, \ldots, n -2, n$ is cardinal, which is false since it has $n - 1$ elements. Therefore, we have $n = k$ and $f(n) = n - 1$. If $n > 4$, then since $f(3) = 3$, we can consider the set $S = \{3,n-1,n\}$ and get $\{3, n-1\}$ is cardinal, which is absurd. If $n = 4$, then $S = \{3,4,2024\}$ gives that $\{3, 4\}$ is cardinal, which is false. If $n = 3$, then $f(2) = f(3) = 2$, so considering $S = \{2,3\}$ gives that $f(S) = \{2\}$ must be cardinal, which is false. Therefore, we must have $n\in \{1,2,2024\}$, so we are done.

Sketch: Answers are $\boxed{1,2,2024}$. Suppose range is infinite set and some not fixed point and choose a set with that number of that size -> $f(x)=x$ or $f$'s range is a finite set Choose a set of size larger than range of $f$ with cardinality something that maps to not $1$ and make everything in the set map to the same thing -> $f$ reaches everything besides $1$ finitely many times, so $1$ is reached infinitely many times Get something that maps to {1,1,...,1,>2} -> $f$ cannot reach anything above $2$ Constructions: $f(x)=1$, $f(x)=x$, and $f(x)=1$ when $x\ne 2024$ and $f(2024)=2$

Headsolved in half an hour: We claim that either $f(n)\in \{1, 2\}$ for all $n\leq N$, or $f(n)=n$ for all $3\leq n\leq N$, for any value of $N$. Then, we see the answer must be $1$, $2$, or $2024$. These can be constructed as follows: $f(n)=1$, $f(n)=1+\delta_{n, 2024}$, and $f(n)=n$. In other words, we only need to prove our claim. First, considering $\mathcal{S}=\{1\}$, we see $f(1)=1$. Considering $\{1, 2\}$, $f(2)$ must either be $1$ or $2$. Considering $\{1,2,3\}$, $f(3)$ must either be $1$, $2$, or $3$. Let us now prove our claim by induction. It is true for $N=3$. Assume it is true for $N=k$. Then: Case 1: $f(n)\in \{1, 2\}$ for all $n\leq k$. By considering $\{1, 2, \dots, k+1\}$, we must have $f(k+1)\leq 3$. If $f(k+1)=3$, considering $\{2, k+1\}$, we see $f(2)=2$. Considering $\{2,3\}$, we also see that $f(3)=1$. However, we now have a contradiction from $\{1,3,k+1\}$. Thus, $f(k+1)\leq 2$, as wanted. Case 2: $f(n)=n$ for all $3\leq n\leq k$. Considering $\{2,3\}$, we must have $f(2)=2$. Thus, $f(n)=n$ for all $n\leq k$. Considering $\{1,2,\dots, k+1\}$, we must have $f(k+1)\leq k+1$. However, if $2<f(k+1)=i<k+1$, we can see from $\{1, \dots, i-2, i, k+1\}$ a contradiction. If $f(k+1)=2$, considering $\{2, k+1\}$ gives a contradiction, and if $f(k+1)=1$, considering $\{1,3,k+1\}$ yields a contradiction. Thus, $f(k+1)=k+1$ is required. This completes our induction.

@anantmudgal09 I'm getting around 55 or so. Will I be able to get into IMO TC?

D_S wrote: @anantmudgal09 I'm getting around 55 or so. Will I be able to get into IMO TC? I don't think he knows the cutoff yet , but probably yes if you aren't in 12th. If you are in 12th, I don't know.

mannshah1211 wrote: D_S wrote: @anantmudgal09 I'm getting around 55 or so. Will I be able to get into IMO TC? I don't think he knows the cutoff yet , but probably yes if you aren't in 12th. If you are in 12th, I don't know. I'm in 10th, and cutoffs were low for last year, but this year the paper was relatively easy...

Well, last year getting 19 was pretty easy, but the cutoff was still 19, so just don't stress about it too much

Here is a really slick solution, different from the one I found during the contest (though I came out of the exam hall thinking about this). We prove that $f(2024) = 1, 2, 2024$: Let $a \sim b$ if and only if $f(a) = f(b)$. Suppose $f(2024) \neq 2024$.

Then there are finitely many equivalence classes.

The only infinite equivalence class is the set satisfying f(n) ₌ 1.

Let $S$ be a set of $2023$ integers satisfying $f(n) = 1$. $S \cup {2024}$ is cardinal, and its image under $f$ is ${1, f(2024)}$. Thus ${1, f(2024)}$ is cardinal, which means $f(2024) = 1, 2$.

My solution - Observe $f(1) = 1$. Now, $f(2)$ can be 1 or 2. Case 1 - Assume $f(2) = 1$ Since the set $\{2,k\}$ is cardinal $\forall k \in \mathbb{N}$ (other than 2), we can say that $f(2024)$ is either 1 or 2. Case 2 - Assume $f(2) = 2$ Since $\{2,k\}$ is cardinal $\forall k \in \mathbb{N}$ (other than 2), $\{f(2),f(k)\}$ is also cardinal forcing $f(k) \neq 2$, $\forall k \neq 2$. We have $f(3) = 1$ or $3$ Case 2a - Assume $f(3) = 1$ The set $\{1,3,k\}$ is cardinal $\forall k \in \mathbb{N}$ (other than 1 and 3). This implies the set $\{1,1,f(k)\}$ is also cardinal forcing $f(k) = 1$ or $2$, but since $2024 \neq 2, f(2024) = 1$ Case 2b - Assume $f(3) = 3$ Claim - $f(n) = n$ Proof - We know $f(1) = 1$ Assume $f(i) = i$, $\forall i \in \{1,\dots, k\}$. Now consider $k+1$. Let $f(k+1) = c \leq k$, so $c \in \{1,\dots,k\}$. Consider the set $\{1,2,\dots,c-3,c-2,c,k+1\}$. Clearly this set is cardinal. This implies $\{f(1),f(2),\dots,f(c-3),f(c-2),f(c),f(k+1)\}$ is cardinal. But that means the set $\{1,2,\dots,c-3,c-2,c,c\}$ is cardinal which is clearly false (only $c-1$ distinct elements). Contradiction, so $f(k+1) \geq k+1$. The set $\{1,2,\dots,k,k+1\}$ is cardinal, so $\{f(1),f(2),\dots,f(k),f(k+1)\}$ is cardinal. This means $\{1,2,\dots,k,f(k+1)\}$ is cardinal. This set has $k+1$ distinct elements, so $f(k+1) = k+1$ Hence by induction $f(n) = n$, $\forall n \in \mathbb{N}$. So $f(2024) = 2024$. Hence proved $f(2024)$ can have 3 values - $1,2,2024$

Claim: $f(2024)\in\boxed{\{1, 2, 2024\}}.$ It is easy to see that $f(\{1\})=\{f(1)\}$ and $f(1)=1$. Now, $f:\{1,2\}\rightarrow\{1,f(2)\}\implies f(2)=1$ or $f(2)=2$. Define a set $T=\{k:f(k)=2\}$, not necessarily be non-empty. Lemma 1: $|T|\leq\min(T)-1$. Proof: Suppose not. If $|T|\geq\min(T)$, then we choose $V\subset T$ where $\min(T)\in V$ and $|V|=\min(T)$. Evidently, $V$ is cardinal. So, $f:V\rightarrow\{2\}$, but $\{2\}$ is not cardinal, a contradiction. $\blacksquare$ Case 1: $f(2)=1$. We see that the codomain of $f$ is hence restricted to $\{1,2\}$. Proof: Suppose there exists $x$ such that $f(x)\geq3$. Then $f:\underbrace{\{2,x\}}_{\text{2 elements}}\rightarrow\underbrace{\{1,f(x)\}}_{\text{2 elements}}$, but $\{1, f(x)\}$ is not cardinal, a contradiction. $\blacksquare$ Case 2: $f(2)=2$. Note that $f(3)\neq2$ by lemma 1, and $f:\{1,2,3\}\rightarrow\{1,2,f(3)\}\implies$ either $f(3)=1$ or $f(3)=3$. Subcase 1: $f(3)=1$. Again, we see that the codomain of $f$ is restricted to $\{1,2\}$. Proof: Suppose there exists $x$ such that $f(x)\geq3$. Then $f:\underbrace{\{1,3,x\}}_{\text{3 elements}}\rightarrow\underbrace{\{1,f(x)\}}_{\text{2 elements}}$, but $\{1, f(x)\}$ is not cardinal, a contradiction. $\blacksquare$ Therefore, combining the results of the cases above, we get a viable family of functions satisfying the criteria: $f(T)=\{2\}$ where $T=\{k:f(k)=2\}$ and $|T|\leq\min(T)-1$ and $f(\mathbb{N}-T)=\{1\}$. It is easy to verify that they indeed work. From here, we can construct $f$ accordingly. If $T=\phi$, then $f(n)=1$ for all $n\in\mathbb{N}$ and $\boxed{f(2024)=1}$. If $T=\{2024\}$, then $f(n)=1$ for all $n\in\mathbb{N}-\{2024\}$ and $\boxed{f(2024)=2}$. Subcase 2: $f(3)=3$. If so, we claim that $f(n)=n$ for all $n\in\mathbb{N}$. We proceed by induction. We have already covered the base cases $n=1, 2$ and $3$. Now, suppose $f(i)=i$ for all $i\in\{1, 2,\dots, k\}$. Lemma 2: $f(k+1)\leq k+1$. Proof: For the sake of contradiction, suppose $f(k+1)>k+1$. But then $$f:\underbrace{\{1, 2,\dots, k-1, k, k+1\}}_{\text{k+1 elements}}\rightarrow\underbrace{\{1, 2,\dots, k-1, k, f(k+1)\}}_{\text{k+1 elements}}$$and the latter cannot be a cardinal set, a contradiction. $\blacksquare$ Let us assume for the sake of contradiction that $f(k+1)=l$, where $l\in\{1, 2,\dots, k-1, k\}$ to be consistent with lemma 2. If $l=1$, then $$f:\underbrace{\{1, 2,\dots, k-2, k, k+1\}}_{\text{k elements}}\rightarrow\underbrace{\{1, 2,\dots, k-2, k\}}_{\text{k-1 elements}}$$but the latter is not cardinal, which is impossible. If $l=2$, then $$f:\{2, k+1\}\rightarrow\{2\}$$but the latter is not cardinal, which is impossible. If $3\leq l \leq k$, then $$f:\underbrace{\{1, 2,\dots, l-2, l, k+1\}}_{\text{l elements}}\rightarrow\underbrace{\{1, 2,\dots, l-2, l\}}_{\text{l-1 elements}}$$but the latter is not cardinal, which is impossible. Therefore, $f(k+1)=k+1$ is forced and $f(n)=n$ for all $n\in\mathbb{N}$ inductively, which certainly works. $\blacksquare$ From here, we get $\boxed{f(2024)=2024}$ as another possibility. Hence, we must have $f(2024)\in\{1, 2, 2024\}$, as desired. $\square$

OG! It is clear that $f(1)=1$, now $f({1,2})={1,f(2)} \implies f(2)=1$ or 2 , Case1: $f(2)=1$, then $f({2,2024})={1,f(2024)}\implies f(2024)=1$ or 2. Case2: $f(2)=2$ Note that $f(3) \neq 2$ as if $f(3)=2$, then $f({2,3})= {2,2}$ is not cardinal. Case2a: $f(3)=1$ Now we prove that $f(n)=1$, for all $n \geq 3$ using stong induction on $n$ with $n=3$ being trivial. ASSUME holds for $n=3,4...k$. ASSUME $f(k+1)>1$, then consider the cardinal set ${1,3,....k,k+1}$. Thus the set $N=f({1,3,....k,k+1})={f(1),f(3)...f(k),f(k+1)}$ is cardinal. If $f(k+1)>2$ So, set $N$ is not cardinal. Thus $f(k+1)=2$, however then the set $f({2,k+1})= {2,2}$ is not cardinal, though it was to be cardinal as ${2,k+1}$ is cardinal. Thus $f(k+1)=1$, completing our induction and thus we get $f(2024)=1$ in this case. Case2a: $f(3)=3$ Now we prove that $f(n)=n$, for all $n \geq 3$ using stong induction on $n$ with $n=3$ being trivial. If it holds for $n=3,4...k$ then let $f(k+1)=m$. If $m>k+1$, then consider the cardinal set $S={1,2,3....k,k+1}$, then the set $f(S)={1,2,3....k,m}$ , where $m>k+1$, thus $f(S)$ is clearly not cardinal. If $2< m < k+1$, then consider the cardinal set $L={1,2,....m-2,m,k+1}$, then the set $f(L)={1,2,3....m-2,m,m}$ , where $m>k+1$, thus $f(S)$ is clearly not cardinal. If $f(k+1)=2$, then consider the cardinal set $M={2,k+1}$, then the set $f(M)={2,2}$ is clearly not cardinal. If $f(k+1)=1$, then consider the cardinal set $X={1,3,k+1}$, then the set $f(X)={1,3,1}$ is clearly not cardinal. Thus, $f(k+1)=k+1$ and our induction is complete. So we get $f(2024)=2024$ Hence we get 3 proosible values 1,2, 2024. Now, to prove that these are achievable, consider $f(x)$ as (1)$f(x)=1$ for all $x \in Z-{2024}$ and $f(2024)=2$ and (2) $f(x)=1$ for all $x \in Z$. (3) $f(x)=x$ for all $x \in Z$. It is easy to see that all the constructions works, making 1,2,2024 achievable values. This $f(2024)=1,2$ or $2024$.

We uploaded our solution https://calimath.org/pdf/INMO2024-4.pdf on youtube https://youtu.be/4ZRngVZY7B8.

The answer is $f(2024)=1,2$ or $2024$, $f(2024)=1$ achievable by $f(n)=1 \ \forall \ n \in \mathbb{N}$. And $f(2024)=2024$ is achievable by $f(n)=n \ \forall n \in \mathbb{N}$, while $f(2024)=2$ is achievable by $$f(n)=1 \ \forall \ n\in \mathbb{N} \setminus \{2024\}, \ f(2024)=2$$. Clearly these constructions are valid, now let's prove $f(2024)$ cannot take any other values. Notice that, since $f: \mathbb{N} \rightarrow \mathbb{N}$, either $f$ is bounded or unbounded. For notation purposes, let $A\cong B$ means that $A$ is a set which contains every distinct element of a multiset $B$ exactly once. For example $\{1,2\} \cong \{1,1,2\}$. Case 1. $f$ is unbounded Note that we can choose natural numbers $2024<a_1<a_2<\cdots<a_{2023}$ that satisfy $$max\{f(2024),2024\}<f(a_1)<f(a_2)<\cdots<f(a_{2023})$$. Since $\{2024,a_1,a_2,\cdots,a_{2023}\}$ is cardinal, the set $\{f(2024),f(a_1),f(a_2),\cdots,f(a_{2023})\}$ is also cardinal. Clearly $\{f(2024),f(a_1),f(a_2),\cdots,f(a_{2023})\}$ contains $2024$ elements, so it must be the case that $f(2024)=2024$. Case 2. $f$ is bounded Since $f$ is bounded, there exist $M \in \mathbb{N}$ where there are infinitely many $x \in \mathbb{N}$ that satisfy $f(x)=M$. We can choose natural numbers $2024<b_1<b_2<\cdots<b_{2023}$ that satisfy $$f(b_1)=f(b_2)=\cdots=f(b_{2023})=M$$. Note that $\{2024,b_1,b_2,\cdots,b_{2023}\}$ is cardinal. If $f(2024)=M$, then the set $\{M\} \cong \{f(2024),f(b_1),f(b_2),\cdots ,f(b_{2023}) \}$ is also cardinal which forces $M=1$, this yields $f(2024)=1$. If $f(2024)\neq M$, then the set $\{f(2024), M\} \cong \{f(2024),f(b_1),f(b_2),\cdots,f(b_{2023})\}$ yields $f(2024)=2$ or else $M=2$. It suffices to prove that $M \neq 2$ FTSOC, assume $M=2$. Then for any $m \in \mathbb{N} \setminus \{1 \}$, we can choose natural numbers $m<c_1<c_2<\cdots c_{m-1}$ such that $$f(c_1)=f(c_2)=\cdots=f(c_{m-1})=2$$. Note that the set $\{ m,c_1,c_2,\cdots, c_{m-1}\}$ is cardinal. If $f(m)=2$ for some $m \in \mathbb{N} \setminus \{1 \}$, then the set $\{2 \} \cong \{ f(m), f(c_1),f(c_2),\cdots, f(c_{m-1})\}$ is cardinal. A contradiction, that means $f(m)\neq 2$ for all $m \in \mathbb{N} \setminus \{1 \}$. Which is absurd. Hence $f(2024)=1$ or $2$. Since we have exhausted all cases, we are done.

I have discussed this question in my INMO 2024 video on my channel "little fermat". Here is the Video