Maths Olympiad Prep

Library / /277 of 397

, 2022

Algebra Difficulty 6.4 National Olympiad Prove it Taiwan

X\mathcal{X} 為正整數集 N\mathbb{N} 的所有非空子集 (不一定有限) 所組成的集合。試求所有函數 f:XR+f: \mathcal{X} \to \mathbb{R}^+ 滿足以下性質:

Let X\mathcal{X} be the set consisting of all nonempty subsets (not necessarily finite) of the set of positive integers N\mathbb{N}. Find all functions f:XR+f: \mathcal{X} \to \mathbb{R}^+ satisfying the following properties:

(i) If STS \subseteq T are both nonempty subsets of N\mathbb{N}, then f(T)f(S)f(T) \le f(S);

(ii) For all S,TXS, T \in \mathcal{X},
f(S)+f(T)f(S+T),f(S)f(T)=f(ST), f(S) + f(T) \le f(S + T), \quad f(S)f(T) = f(S \cdot T),
where S+T={s+tsS,tT},ST={stsS,tT}S + T = \{s + t \mid s \in S, t \in T\}, S \cdot T = \{s \cdot t \mid s \in S, t \in T\}.

Solution

f(S)=(minS)α,SXf(S) = (\min S)^\alpha, \forall S \in \mathcal{X}, where α1\alpha \ge 1. It is easy to see that all such functions are solutions. We now prove that only functions of this form satisfy all the conditions.

Since {1}{1}={1}\{1\} \cdot \{1\} = \{1\}, NN=N\mathbb{N} \cdot \mathbb{N} = \mathbb{N}, we have
f({1})2=f({1}),f(N})2=f(N})    f({1})=f(N})=1. f(\{1\})^2 = f(\{1\}), \quad f(\mathbb{N\})^2 = f(\mathbb{N\}) \implies f(\{1\}) = f(\mathbb{N\}) = 1. }}}

For all sets SS containing 1, by condition (i), 1=f(N})f(S)f({1})=11 = f(\mathbb{N\}) \le f(S) \le f(\{1\}) = 1}, that is,
f(S)=1f(S) = 1.

For positive integer nn, define g(n)=f({n})g(n) = f(\{n\}); then condition (ii) tells us
g(m)+g(n)g(m+n),g(mn)=g(m)g(n). g(m) + g(n) \le g(m + n), \quad g(mn) = g(m)g(n).
The former inequality implies that gg is a strictly increasing function on N\mathbb{N}. Choose α\alpha such that g(2)=2αg(2) = 2^\alpha; then 2α=g(2)g(1)+g(1)=22^\alpha = g(2) \ge g(1) + g(1) = 2 tells us that α1\alpha \ge 1.

We now prove g(n)=nαg(n) = n^\alpha: for n=1,2n = 1, 2 this is obvious. For any n3n \ge 3 and positive integer kk, take a positive integer \ell such that 2nk<2+12^\ell \le n^k < 2^{\ell+1}. Since gg is completely multiplicative, we have
2αg(n)k<2(+1)α    2/kg(n)1/α<2(+1)/k. 2^{\ell\alpha} \le g(n)^k < 2^{(\ell+1)\alpha} \implies 2^{\ell/k} \le g(n)^{1/\alpha} < 2^{(\ell+1)/k}.
Since 2/kn<2(+1)/k2^{\ell/k} \le n < 2^{(\ell+1)/k}, we know
21/k<2/kng(n)1/αn<2(+1)/kn21/k. 2^{-1/k} < \frac{2^{\ell/k}}{n} \le \frac{g(n)^{1/\alpha}}{n} < \frac{2^{(\ell+1)/k}}{n} \le 2^{1/k}.

Since this holds for all positive integers kk, g(n)1/αg(n)^{1/\alpha} must equal nn, that is, f({n})=g(n)=nαf(\{n\}) = g(n) = n^\alpha.

For any set SS not containing 1, let m=minSm = \min S. Since {m}S\{m\} \subseteq S, by condition (i) and the above result,
f(S)f({m})=mα.(1) f(S) \le f(\{m\}) = m^{\alpha}. \qquad (1)
Since 1=m(m1)S{m1}:={s(m1)sS}1 = m - (m-1) \in S - \{m-1\} := \{s - (m-1) \mid s \in S\}, we have
f(S)f({m1})+f(S{m1})=(m1)α+1. f(S) \ge f(\{m-1\}) + f(S - \{m-1\}) = (m-1)^{\alpha} + 1.
Replacing SS in the above with Sk:={s1sks1,,skS}S^k := \{s_1 \cdots s_k \mid s_1, \dots, s_k \in S\}, we obtain
f(S)k=f(Sk)(min(Sk)1)α+1=(mk1)α+1. f(S)^k = f(S^k) \ge (\min(S^k) - 1)^\alpha + 1 = (m^k - 1)^\alpha + 1.
Therefore, when k>αk > \alpha,
f(S)>(mk1)α/k=mα(11mk)α/kmα(11mk). f(S) > (m^k - 1)^{\alpha/k} = m^{\alpha} \left(1 - \frac{1}{m^k}\right)^{\alpha/k} \ge m^{\alpha} \left(1 - \frac{1}{m^k}\right).
Since this holds for all positive integers k>αk > \alpha, we have f(S)mαf(S) \ge m^\alpha. Combining this with (1) gives
f(S)=mα=(minS)α. f(S) = m^{\alpha} = (\min S)^{\alpha}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.