7 replies to this topic

[supermember]

Bài Toán :

Cho dãy số nguyên dương $ \{ a_n \}_{n\ge 1}^{ + \infty}$ thỏa mãn : $ a_1 = 1 ; a_2 = 2 $ và :

$ a_{mn} = a_m \cdot a_n \;; a_{m+n} \le C \left( a_m + a_n \right) \; \forall m ;n \in \mathbb{N^{*}} $


Trong đó $ C \ge 1 $ là hằng số cho trước .


Chứng minh rằng : $ a_n = n \ \ \forall n \in \mathbb{N^{*}} $

[PSW]

Bài toán này thuộc Gameshow NHỮNG BÀI TOÁN TRONG TUẦN. Bài toán đã được công bố lại nhiều ngày nhưng chưa ai giải được. BTC đã đặt hoa hồng hi vọng cho bài toán này.

Hoa hồng hi vọng sẽ mang lại 50 điểm cho người đầu tiên giải đúng được bài toán này. Nếu hết ngày 10/12 mà vẫn không có ai giải được, BTC sẽ công bố bài toán khác, tuy nhiên hoa hồng hi vọng sẽ vẫn tồn tại cho đến khi có người giải được bài toán này.

[gogo123]

Đặt $f(n)=a_n$ để dễ trình bày, dễ thấy $f(0)=0$
Ta có: $f(n)$ là hàm nhân tính trên tập số nguyên dương; $f(1)=1;f(2)=2$
Suy ra: $f(2^{n})=2^{n}$ với mọi $n$.
Xét số nguyên dương $n$ bất kì, viết $n$ dưới dang $n= \sum_{i=0}^{k-1}a_i2^{i}$, với $a_i \in \left \{ 0;1 \right \} $.
Khi đó ta có: $3^{k-1}\leq n<3^{k}$.
Theo tính chất (2) của dãy ta có:
$$f(n)=f(\sum_{i=0}^{k-1}a_i2^{i})\leq C(\sum_{i=0}^{k-1}f(a_i)2^{i})\leq C(\sum_{i=0}^{k-1}2^{i})=C(2^{k}-1)<2Cn$$
Vậy $f(n)<2Cn$ với mọi n.
Do tính nhân tính của $f$ nên ta có
$(f(n))^{t}=f(n^{t})<2Cn^{t} \Rightarrow f(n)<\sqrt[t]{2C}n$
Cho $t \rightarrow + \infty $ thì $ \sqrt[t]{2C} \rightarrow 1$
Vậy với mọi $n$ ta có: $f(n) \leq n$
Bây giờ ta sẽ chứng minh $f(n)\geq n$ với mọi $n$.
Thật vậy: Vì $n<2^{k}$ nên tồn tại số nguyên dương $a$ sao cho $n+a=2^{k}$. Theo tính chất 2ta có:
$$f(n) \geq C(2^{k}-f(a))$$
Mặt khác theo tính chất đã chứng minh ở trên thì $f(a)\leq a \leq 2^{k}-2^{k-1}$
Suy ra: $f(n) \geq 2^{k}-(2^{k}-2^{k-1} \geq 2^{k-1} \geq \frac{nC}{2}$
Do đó : $(f(n))^{t}=f(n^{t}) \geq \frac{C}{2}.n^{t} \Rightarrow f(n) \geq \sqrt[t]{\frac{C}{2}}.n$
Tiếp tục cho $t \rightarrow + \infty $ ta có $f(n) \geq n$ với mọi $n$
Vậy ta có $f(n)=n$ với mọi $n$ hay $a_n=n$ (đpcm)

Edited by gogo123, 10-12-2012 - 23:26.

[Primary]

Không biết cách này được không:
**Ta chứng minh bổ đề: Với mọi hàm $f(x)>0$ liên tục và $f(xy)=f(x)+f(y),\forall x,y>0$ thì $f(x)=log_ax$ với a là hằng số dương khác 1
Thật vậy: xét hàm số $\varphi (x)=f(e^x),\forall x>0$. Suy ra: $\varphi (x)$ là hàm liên tục $\forall x>0$
$\forall x,y>0: \varphi (x+y)=f(e^{x+y})=f(e^x.e^y)=f(e^x)+f(e^y)=\varphi (x)+\varphi (y)$
Theo phương trình hàm Cauchy suy ra $\varphi (x)=cx$ với $c=const$
*Rõ ràng $c\neq 0$. Vì nếu $c=0$$\Rightarrow \varphi (x)=0\Rightarrow f(x)=0$ (vô lí!)
$\Rightarrow f(e^x)=cx\Rightarrow f(t)=c.lnt,\forall x>0$
*Đặt $c=\frac{1}{lna}\Rightarrow f(t)=\frac{lnt}{lna}=log_at,\forall a>0,a\neq 1$ hay $f(x)=log_ax\Leftrightarrow Q.E.D$
**Trờ lại bài toán:
*Đặt $f(n)=a_n\Rightarrow \left\{\begin{matrix}f(1)=1;f(2)=2 & & & \\ f(m.n)=f(m).f(n) & & & \\f(m+n)\leq C(f(m)+f(n)) & & & \end{matrix}\right. ,\forall m,n\in \mathbb{N}^*$
Nếu $f(n)<0$ thì $\left\{\begin{matrix}f(m.n)<0 & & \\ f(m).f(n)>0 & & \end{matrix}\right.$ (Vô lí!)
Nếu $f(n)=0$ thì $f(1)=0$ (vô lí!)
$\Rightarrow f(n)>0,\forall n\in \mathbb{N}^*$
*Đặt $\phi (x)=lnf(x)\Rightarrow \phi (m.n)=lnf(m.n)=ln(f(m).f(n))=lnf(m)+lnf(n)$ $=\phi (m)+\phi (n)$
Do đó $\phi (x)$ thỏa mãn bổ đề, suy ra $\phi (n)=log_ax,\forall n\in \mathbb{N}^*,a\in (0;+\infty )$
$\Rightarrow f(n)=n^{\frac{1}{lna}}$ với mọi số nguyên dương n (1)
Mà $f(1)=1;f(2)=2$ nên ta có $\left\{\begin{matrix}lnf(1)=log_a1 & & & \\ lnf(2)=log_a2 & & & \\ (m+n)^{\frac{1}{lna}}\leq C(m^{\frac{1}{lna}}+n^{\frac{1}{lna}})\Leftrightarrow & & & \end{matrix}\right. \Leftrightarrow \left\{\begin{matrix}a=e & \\ C\geq 1 & \end{matrix}\right.$ (2)
Từ (1) và (2): $\Rightarrow f(n)=n\Leftrightarrow a_n=n\Leftrightarrow Q.E.D$

Edited by Primary, 24-01-2013 - 18:44.

[perfectstrong]

Khi bạn đặt hàm $\phi (x)=ln f(x)$, bạn có đảm bảo $\phi (x)$ liên tục?

[Primary]

Khi bạn đặt hàm $\phi (x)=ln f(x)$, bạn có đảm bảo $\phi (x)$ liên tục?

Lúc đầu, em làm bài này cũng thấy nghi điểm ở chỗ liên tục. Em sẽ suy nghĩ lại

[Trungpbc]

Đặt $f(n)=a_n$ để dễ trình bày, dễ thấy $f(0)=0$
Ta có: $f(n)$ là hàm nhân tính trên tập số nguyên dương; $f(1)=1;f(2)=2$
Suy ra: $f(2^{n})=2^{n}$ với mọi $n$.
Xét số nguyên dương $n$ bất kì, viết $n$ dưới dang $n= \sum_{i=0}^{k-1}a_i2^{i}$, với $a_i \in \left \{ 0;1 \right \} $.
Khi đó ta có: $3^{k-1}\leq n<3^{k}$.
Theo tính chất (2) của dãy ta có:
$$f(n)=f(\sum_{i=0}^{k-1}a_i2^{i})\leq C(\sum_{i=0}^{k-1}f(a_i)2^{i})\leq C(\sum_{i=0}^{k-1}2^{i})=C(2^{k}-1)<2Cn$$
Vậy $f(n)<2Cn$ với mọi n.
Do tính nhân tính của $f$ nên ta có
$(f(n))^{t}=f(n^{t})<2Cn^{t} \Rightarrow f(n)<\sqrt[t]{2C}n$
Cho $t \rightarrow + \infty $ thì $ \sqrt[t]{2C} \rightarrow 1$
Vậy với mọi $n$ ta có: $f(n) \leq n$
Bây giờ ta sẽ chứng minh $f(n)\geq n$ với mọi $n$.
Thật vậy: Vì $n<2^{k}$ nên tồn tại số nguyên dương $a$ sao cho $n+a=2^{k}$. Theo tính chất 2ta có:
$$f(n) \geq C(2^{k}-f(a))$$
Mặt khác theo tính chất đã chứng minh ở trên thì $f(a)\leq a \leq 2^{k}-2^{k-1}$
Suy ra: $f(n) \geq 2^{k}-(2^{k}-2^{k-1} \geq 2^{k-1} \geq \frac{nC}{2}$
Do đó : $(f(n))^{t}=f(n^{t}) \geq \frac{C}{2}.n^{t} \Rightarrow f(n) \geq \sqrt[t]{\frac{C}{2}}.n$
Tiếp tục cho $t \rightarrow + \infty $ ta có $f(n) \geq n$ với mọi $n$
Vậy ta có $f(n)=n$ với mọi $n$ hay $a_n=n$ (đpcm)

Ý tưởng trong lời giải của gogo123 khá độc đáo nhưng nếu để ý các bạn sẽ thấy nó đã phạm phải một sai lầm căn bản. Cụ thể ở chỗ mình bôi đỏ trên, đã thừa nhận tính chất: $$f\left ( n_{1}+n_{2}+\cdots +n_{k} \right )\leqslant C\left [ f(n_{1})+f(n_{2})+\cdots +f(n_{k}) \right ]$$ Chứng minh điều này không dễ và có lễ cũng là mấu chốt của bài toán. Dưới đây, ta sẽ chứng minh khẳng định mạnh hơn: $$f(x+y)\leqslant f(x)+f(y),\forall x,y\in \mathbb{N^{*}}$$ để rồi từ đó giải quyết bài toán rất nhẹ nhàng. Thật vậy, từ giả thiết, ta có: $$f(x+y+z)\leqslant C\left [ f(x)+f(y+z) \right ]\leqslant Cf(x)+C^{2}f(y)+C^{2}f(z)$$ Hoán đổi vai trò của $x,y,z$ rồi cộng theo vế các BĐT đó, ta được: $$f(x+y+z)\leqslant \frac{C+2C^{2}}{3}\left [ f(x)+f(y)+f(z) \right ]$$ Từ đó, với chú ý $f$ là hàm nhân tính và $f(2)=2$, suy ra:

$$ f(m+n)^{2}=f(m^{2}+2mn+n^{2})\leqslant \frac{C+2C^{2}}{3}\left [ f(m^{2})+f(2mn)+f(n^{2}) \right ]=\frac{C+2C^{2}}{3}\left [ f(m)+f(n) \right ]^{2} $$ Thành thử: $$ f(m+n)\leqslant \sqrt{\frac{C+2C^{2}}{3}}\left [ f(m)+f(n) \right ] $$ với mọi số nguyên dương $m,n$. Xét dãy $\left (c_{n}  \right ) $ được xác định như sau: $ c_{1}=C,c_{n+1}=\sqrt{\frac{c_{n}+2c_{n}^{2}}{3}} $. Dễ thấy, bằng quy nạp ta có được: $$ f(m+n)\leqslant c_{k}\left [ f(m)+f(n) \right ] $$ với mọi số nguyên dương $k$ và $c_{k}$ giảm dần về 1 khi $k$ dần ra vô cùng. Như vậy: $$ f(m+n)\leqslant f(m)+f(n) $$ với mọi số nguyên dương $m,n$. Một hệ quả dễ thấy là $f(n)\leqslant n$ với mọi số nguyên dương $n$.

Cố định một số nguyên dương $n$ bất kì và chọn số nguyên dương $k$ thỏa mãn $2^{k}>n$, khi đó: $$ 2^{k}=f(2^{k})\leqslant f(2^{k}-n)+f(n)\leqslant 2^{k}-n+n=2^{k} $$ Suy ra, dấu đẳng thức phải xảy ra, hay $ f(n)=n $. Phép chứng minh hoàn tất.

Edited by Trungpbc, 25-03-2013 - 21:13.

[PSW]

Chấm bài Trungpbc 50 điểm

Edited by PSW, 25-03-2013 - 22:21.