Let X be the collection of all non-empty subsets (not necessarily finite) of the positive integer set N. Determine all functions f:X→R+ satisfying the following properties: (i) For all S, T∈X with S⊆T, there holds f(T)≤f(S). (ii) For all S, T∈X, there hold f(S)+f(T)≤f(S+T),f(S)f(T)=f(S⋅T),where S+T={s+t∣s∈S,t∈T} and S⋅T={s⋅t∣s∈S,t∈T}. Proposed by Li4, Untro368, and Ming Hsiao.
Problem
Source: 2022 Taiwan TST Round 3 Mock P4
Tags: function, algebra, functional equation, domain, ming
30.04.2022 10:24
Chef's kiss The only solution is f(S)=(min where c\ge 1 is some constant real number. The first condition holds because since T contains S, the smallest element of T is at least as small as the smallest element of S. The second condition holds because x^c is convex and multiplicative. We now show it is the only solution. Let x,y be natural numbers unless otherwise specified. For simplicity, define f(\{x\})=f(x) where x is any positive integer. Note that from condition (ii), f(x)+f(y)\le f(x+y) and f(x)f(y)=f(xy). Obviously, f(1)=1, and f is strictly increasing. Consider any y>2. Let r,s be positive integers such that \frac{r}{s}>\frac{\log y}{\log 2}. Then, 2^r>y^s\implies f(2^r)>f(y^s)\implies f(2)^r>f(y)^s\implies \frac{r}{s}>\frac{\log f(y)}{\log f(2)}. Similarly, if \frac{r}{s}<\frac{\log y}{\log 2}, then \frac{r}{s}<\frac{\log f(y)}{\log f(2)}. Since rationals are dense over \mathbb{R}, \frac{\log y}{\log 2} = \frac{\log f(y)}{\log f(2)}\implies \frac{\log f(y)}{\log y} is constant. Hence, \frac{\log f(y)}{\log y}=c\implies f(y)=y^c for some constant c. Since f(x)+f(y)\le f(x+y), we get c\ge 1. Let S be a set containing 1. Then, f(S)f(\mathbb{N})=f(\mathbb{N}) implies f(S)=1. Let S be a set with minimal element a. Then, from (i) we get f(S)\le a^c and from (ii) we get f(S)\ge f(S-(a-1))+f(a-1)=1+(a-1)^c. Hence, a^c\ge f(S)\ge 1+(a-1)^c. Take a positive integer k, f(S)^k=f(S^k)\ge 1+(a^k-1)^c. Thus, f(S)>\sqrt[k]{(a^k-1)^c}. The limit of this is a^c, and so taking k to infinity we get f(S)=a^c. This concludes the proof. wow.
30.04.2022 10:40
The only function is f(S)=(\min S)^c where c\ge1 is constant. We prove the following claims. Claim 1: f(\mathbb N)=1. Proof: Setting S=T=\mathbb N in the latter equation of condition (ii) gives f(\mathbb N)f(\mathbb N)=f(\mathbb N)\implies f(\mathbb N)=1 Claim 2: For any set S, if m=\min S, then we have f(S)=f(m\mathbb N). Proof: Since m is the minimum element of S, we have S\cdot\mathbb N=m\mathbb N. Setting T=\mathbb N in the latter of condition (ii) gives f(S)f(\mathbb N)=f(m\mathbb N)\implies f(S)=f(m\mathbb N)since f(\mathbb N)=1 from Claim 1. Because of Claim 2, we can define a function g:\mathbb N\to\mathbb R^+ such that f(S)=g(\min S) for any subset S. In terms of g, the new conditions are: (i) For all s,t\in\mathbb N with t\le s, we have g(t)\le g(s) (ii) For all s,t\in\mathbb N, we have g(s)+g(t)\le g(s+t),\quad g(s)g(t)=g(st)The proof that g(n)=n^c for some constant c follows similarly as @gghx's solution above. EDIT: Whoops. @below, yes you are right, my solution is incorrect. My apologies.
30.04.2022 10:42
P1kachu wrote: Proof: Since m is the minimum element of S, we have S\cdot\mathbb N=m\mathbb N. I dont think so? for example S=\{2,3\}.