Author: Nguyen Trung-Tuan

A math teacher.

IMO Shortlist 2008


Đại số

Bài 1. Tìm tất cả các hàm số f:(0,\infty)\mapsto(0,\infty) (tức là f là một hàm từ tập các số thực dương) thỏa mãn

\displaystyle\frac{(f(w))^{2}+(f(x))^{2}}{f(y^{2})+f(z^{2})}=\frac{w^{2}+x^{2}}{y^{2}+z^{2}}

với mọi số thực dương w, x, y, z thỏa mãn wx=yz.

Bài 2. (a) Chứng minh rằng \frac{x^{2}}{(x-1)^{2}}+\frac{y^{2}}{(y-1)^{2}}+\frac{z^{2}}{(z-1)^{2}}\ge1 với mọi số thực x, y, z khác 1 và thỏa mãn xyz=1.
(b) Chứng minh rằng đẳng thức trên xảy ra với vô số bộ ba số hữu tỉ x, y, z khác 1 và thỏa mãn xyz=1.

Bài 3. Cho S\subseteq\mathbb{R} là một tập hợp các số thực. Ta nói rằng một cặp hàm số (f, g) từ S vào S là một “Cặp đôi Tây Ban Nha” (Spanish Couple) trên S, nếu chúng thỏa mãn các điều kiện sau:
(i) Cả hai hàm số đều tăng ngặt, tức là f(x)<f(y) và g(x)<g(y) với mọi x, y\in S mà x<y;
(ii) Bất đẳng thức f(g(g(x)))<g(f(x)) đúng với mọi x\in S.
Hãy xác định xem có tồn tại một Cặp đôi Tây Ban Nha trên tập S=\mathbb{N} các số nguyên dương hay không; và trên tập S={a-\frac{1}{b}:a,b\in\mathbb{N}}.

Bài 4. Với một số nguyên m, gọi t(m) là số duy nhất thuộc {1,2,3} sao cho m+t(m) là bội của 3. Một hàm số f:\mathbb{Z}\rightarrow\mathbb{Z} thỏa mãn f(-1)=0, f(0)=1, f(1)=-1 và f(2^{n}+m)=f(2^{n}-t(m))-f(m) với mọi số nguyên m, n\ge0 sao cho 2^{n}>m. Chứng minh rằng f(3p)\ge0 đúng với mọi số nguyên p\ge0.

Bài 5. Cho a, b, c, d là các số thực dương thỏa mãn abcd=1 và a+b+c+d>\frac{a}{b}+\frac{b}{c}+\frac{c}{d}+\frac{d}{a}. Chứng minh rằng a+b+c+d<\frac{b}{a}+\frac{c}{b}+\frac{d}{c}+\frac{a}{d}.

Bài 6. Cho hàm số f:\mathbb{R}\rightarrow\mathbb{N} thỏa mãn f(x+\frac{1}{f(y)})=f(y+\frac{1}{f(x)}) với mọi x,y\in\mathbb{R}. Chứng minh rằng tồn tại một số nguyên dương không phải là giá trị của f.

Bài 7. Chứng minh rằng với bốn số thực dương a, b, c, d bất kỳ, bất đẳng thức

\displaystyle\frac{(a-b)(a-c)}{a+b+c}+\frac{(b-c)(b-d)}{b+c+d}+\frac{(c-d)(c-a)}{c+d+a}+\frac{(d-a)(d-b)}{d+a+b}\ge0

luôn đúng. Xác định tất cả các trường hợp xảy ra dấu đẳng thức.

Tổ hợp

Bài 1. Trong mặt phẳng, ta xét các hình chữ nhật có các cạnh song song với các trục tọa độ và có độ dài dương. Mỗi hình chữ nhật như vậy được gọi là một hộp. Hai hộp giao nhau nếu chúng có một điểm chung ở phần trong hoặc trên biên. Tìm số n lớn nhất sao cho tồn tại n hộp B_{1},…, B_{n} thỏa mãn B_{i} và B_{j} giao nhau khi và chỉ khi i\not\equiv j\pm1 \pmod n.

Bài 2. Cho n\in\mathbb{N} và A_{n} là tập hợp tất cả các hoán vị (a_{1},...,a_{n}) của tập {1,2,...,n} sao cho k\mid 2(a_{1}+\cdot\cdot\cdot+a_{k}) với mọi 1\le k\le n. Tìm số phần tử của tập A_{n}.

Bài 3. Trong mặt phẳng tọa độ, xét tập S gồm tất cả các điểm có tọa độ nguyên. Với một số nguyên dương k, hai điểm phân biệt A, B\in S được gọi là k-bạn bè nếu tồn tại một điểm C\in S sao cho diện tích tam giác ABC bằng k. Một tập T\subset S được gọi là k-clique nếu cứ hai điểm bất kỳ trong T đều là k-bạn bè. Tìm số nguyên dương nhỏ nhất sao cho tồn tại một k-clique có nhiều hơn 200 phần tử.

Bài 4. Cho n và k là các số nguyên dương với k\ge n và k-n là một số chẵn. Có 2n bóng đèn được đánh số từ 1 đến 2n, mỗi bóng có thể ở trạng thái bật hoặc tắt. Ban đầu tất cả các bóng đèn đều tắt. Ta xét các dãy bước thực hiện: tại mỗi bước, một trong các bóng đèn được chuyển trạng thái (từ bật sang tắt hoặc từ tắt sang bật). Gọi N là số lượng các dãy như vậy gồm k bước và dẫn đến trạng thái mà các bóng đèn từ 1 đến n đều bật, còn các bóng đèn từ n+1 đến 2n đều tắt. Gọi M là số lượng các dãy gồm k bước dẫn đến trạng thái mà các bóng đèn từ 1 đến n đều bật, các bóng đèn từ n+1 đến 2n đều tắt, nhưng không có bóng đèn nào từ n+1 đến 2n từng được bật lên. Xác định tỉ số \frac{N}{M}.

Bài 5. Cho S={x_{1},x_{2},...,x_{k+l}} là một tập hợp gồm k+l số thực nằm trong đoạn [0, 1]; k và l là các số nguyên dương. Một tập con A\subset S gồm k phần tử được gọi là “đẹp” nếu

\displaystyle \left|\frac{1}{k}\sum_{x_{i}\in A}x_{i}-\frac{1}{l}\sum_{x_{j}\in S\backslash A}x_{j}\right|\le\frac{k+l}{2kl}.

Chứng minh rằng số lượng các tập con đẹp ít nhất là \frac{2}{k+l}\binom{k+l}{k}.

Bài 6. Với n\ge2, cho S_{1},S_{2},...,S_{2^{n}} là 2^{n} tập con của A={1,2,3,...,2^{n+1}} thỏa mãn tính chất sau. Không tồn tại các chỉ số a và b với a<b và các phần tử x,y,z\in A với x<y<z sao cho y,z\in S_{a} và x,z\in S_{b}. Chứng minh rằng ít nhất một trong các tập S_{1},S_{2},...,S_{2^{n}} chứa không quá 4n phần tử.

Continue reading “IMO Shortlist 2008” →

The sum of the reciprocals of the primes


Với mỗi số nguyên dương n, ký hiệu p_n là số nguyên tố thứ n trong dãy tăng tất cả các số nguyên tố. Như vậy p_1=2, p_2=3, p_3=5,…

Trong bài này chúng tôi sẽ giới thiệu một chứng minh của kết quả sau:

Định lý. Chuỗi \displaystyle \frac{1}{p_1}+\frac{1}{p_2}+\frac{1}{p_3}+\ldots là một chuỗi phân kỳ.

Chứng minh. Giả sử ngược lại, khi đó với mỗi số nguyên dương k, chuỗi \displaystyle\sum_{m=k}^{+\infty}\frac{1}{p_m} là một chuỗi hội tụ, gọi S_k là tổng của nó. Vì \lim S_k=0 nên tồn tại số nguyên k sao cho \displaystyle S_{k+1}<\frac{1}{2}. Đặt Q=p_1p_2\ldots p_k và xét các số 1+nQ\, (n=1,2,\ldots). Mỗi số trong dãy này đều không có ước nguyên tố thuộc \{p_1, p_2, \ldots, p_k\}, do đó với mỗi số nguyên dương r, tồn tại số nguyên dương K đủ lớn để

\displaystyle\sum_{n=1}^r\frac{1}{1+nQ}\leq\sum_{t=1}^{K}S_{k+1}^t<1.

Điều này không thể xảy ra do chuỗi \displaystyle \sum_{n=1}^{+\infty}\frac{1}{1+nQ} là một chuỗi phân kỳ. \Box

Tham khảo

[1] https://nttuan.org/2018/12/30/series/

[2] https://en.wikipedia.org/wiki/Divergence_of_the_sum_of_the_reciprocals_of_the_primes

Functional equations on real line I


Trong mục này, qua các ví dụ và bài tập, chúng tôi sẽ giới thiệu các kỹ thuật cơ bản để giải các phương trình hàm trên tập số thực.

Ví dụ 1. Tìm tất cả các hàm số f:\mathbb{R}\to\mathbb{R} sao cho 

f(x)f(y)=xy-f(x+y),\quad \forall x,y\in\mathbb{R}.

Lời giải. Giả sử f là một hàm số thỏa mãn yêu cầu của đề bài, khi đó 

f(x)f(y)=xy-f(x+y),\quad \forall x,y\in\mathbb{R}.\quad (1)    

Trong (1), cho x=y=0 ta có f(0)^2=-f(0), suy ra f(0)=0 hoặc f(0)=-1. Nếu f(0)=0 thì trong (1), chọn y=0 ta có f(x)=0 với mọi số thực x. Kiểm tra ta thấy hàm số này không thỏa mãn. Bây giờ ta xét trường hợp f(0)=-1.

Trong (1), cho x=1 và y=-1 ta có f(1)f(-1)=0, suy ra f(1)=0 hoặc f(-1)=0.

Trường hợp 1: f(1)=0.

Trong (1), chọn y=1, ta có f(x+1)=x với mọi số thực x, suy ra f(x)=x-1,\quad\forall x\in\mathbb{R}.

Trường hợp 2: f(-1)=0.

Trong (1), chọn y=-1, ta có f(x-1)=-x với mọi số thực x, suy ra f(x)=-x-1,\quad\forall x\in\mathbb{R}.

Khi f(x)=x-1 thì với mỗi số thực x và y, ta có

xy-f(x+y)=xy-(x+y-1)=(x-1)(y-1)=f(x)f(y),

suy ra hàm số này thỏa mãn yêu cầu của đề bài.

Khi f(x)=-x-1 thì với mỗi số thực x và y, ta có

xy-f(x+y)=xy+(x+y+1)=(-x-1)(-y-1)=f(x)f(y),

suy ra hàm số f(x)=-x-1 cũng thỏa mãn.

Vậy có hai hàm số thỏa mãn yêu cầu của đề bài, đó là f(x)=x-1 và f(x)=-x-1. \Box

Ví dụ 2. Tìm tất cả các hàm số f:\mathbb{R}\to\mathbb{R} thỏa mãn

f(f(x)+y)=yf(x-f(y)),\quad\forall x,y\in\mathbb{R}.

Lời giải. Giả sử f là một hàm số thỏa mãn yêu cầu của đề bài. Khi đó 

f(f(x)+y)=yf(x-f(y)),\quad\forall x,y\in\mathbb{R}.\quad (1)

Trong (1), chọn y=0, ta có f(f(x))=0 với mọi số thực x. Từ đây, bằng cách thay x bởi f(y) vào (1), ta có f(y)=f(0)y với mọi số thực y. Suy ra f(0)=0 và f(x)=0 với mọi số thực x. Ngược lại, kiểm tra thấy hàm số f(x)=0 thỏa mãn. 

Vậy có đúng một hàm số thỏa mãn yêu cầu của đề bài, đó là f(x)=0 với mọi số thực x. \Box

Ví dụ 3. Tìm tất cả các hàm số f:\mathbb{R}\to\mathbb{R} thỏa mãn

\displaystyle f(xy)=\frac{f(x)+f(y)}{x+y}  

với mọi số thực x và y sao cho x+y\not=0.

Lời giải. Giả sử f là một hàm số thỏa mãn yêu cầu của đề bài. Khi đó 

\displaystyle f(xy)=\frac{f(x)+f(y)}{x+y}  

với mọi số thực x và y sao cho x+y\not=0. \quad (*)

Từ (*), với x=0 và y=1 ta có f(1)=0. Vẫn từ (*), chọn y=1 ta được

xf(x)=0,\quad\forall x\in\mathbb{R}\setminus\{-1\}.

Nói riêng, f(2)=0. Từ (*), với x=2 và y=0, ta có f(0)=0. Cuối cùng, với y=0, từ (*) ta có f(x)=0 với mọi số thực x\not=0. Suy ra f(x)=0 với mọi số thực x. Ngược lại, kiểm tra thấy hàm số f(x)=0 thỏa mãn.

Vậy có đúng một hàm số thỏa mãn yêu cầu của đề bài, đó là f(x)=0 với mọi số thực x. \Box

Ví dụ 4. Tìm tất cả các hàm số f:\mathbb{R}\to\mathbb{R} thỏa mãn

xf(y)+yf(x)=(x+y)f(x)f(y),\quad\forall x,y\in\mathbb{R}.

Lời giải. Giả sử f là một hàm số thỏa mãn yêu cầu của đề bài. Khi đó 

xf(y)+yf(x)=(x+y)f(x)f(y),\quad\forall x,y\in\mathbb{R}.\quad (1)    

Từ (1), với x=y=1 ta có f(1)^2=f(1), suy ra f(1)=0 hoặc f(1)=1. Nếu f(1)=1 thì với y=1, từ (1) ta có f(x)=0 với mọi số thực x. Kiểm tra ta thấy hàm số này thỏa mãn. Bây giờ ta xét trường hợp f(1)=1.

Trong (1), chọn y=1 và để ý f(1)=1, ta có xf(x)=x với mọi số thực x. Suy ra tồn tại số thực a để

f(x)=\begin{cases}1,\quad x\not=0\\ a,\quad x=0.\end{cases}

Kiểm tra cẩn thận ta thấy hàm số này cũng thỏa mãn.

Vậy các hàm số phải tìm là f(x)=0 với mọi số thực x, hoặc

f(x)=\begin{cases}1,\quad x\not=0\\ a,\quad x=0.\end{cases}

Ở đây a là một số thực. \Box        

Ví dụ 5. Tìm tất cả các hàm số f:\mathbb{R}\to\mathbb{R} thỏa mãn

f(x+y) = \max(f(x),y) + \min(f(y),x)

với mọi số thực x và y.         

Lời giải. Giả sử f là một hàm số thỏa mãn yêu cầu của đề bài. Khi đó 

f(x+y) = \max(f(x),y) + \min(f(y),x)

với mọi số thực x và y.\quad (*)

Từ (*), lần lượt thay x=0 và y=0, ta có

f(y) = \max(f(0),y) + \min(f(y),0),\quad\forall y\in\mathbb{R},

và

f(x) = \max(f(x),0) + \min(f(0),x),\quad\forall x\in\mathbb{R}.

Suy ra với mỗi số thực x,

2f(x)=f(x)+f(x)=(f(0)+x)+(f(x)+0),

do đó f(x)=x+f(0),\quad\forall x\in\mathbb{R}. Sử dụng điều này, khi thay x=0 và y=f(0), từ (*) ta có f(0)=\min (2f(0),0). Suy ra f(0)=0, và f(x)=x với mọi số thực x. Ngược lại, kiểm tra thấy hàm số f(x)=x thỏa mãn. 

Vậy có đúng một hàm số thỏa mãn yêu cầu của đề bài, đó là f(x)=x với mọi số thực x. \Box

Z – K[x]


Các bạn học sinh chắc rất quen thuộc với cuốn từ điển ANH – VIỆT đúng không? Hôm nay tôi sẽ giới thiệu vài trang trong cuốn từ điển SỐ NGUYÊN – ĐA THỨC. Để theo bài cho dễ dàng các bạn nên đọc lướt qua các bài sau:

[1] https://nttuan.org/2023/06/30/poly01/

[2] https://nttuan.org/2023/07/14/divisibility/

[3] https://nttuan.org/2023/08/04/prime/

Mục đích của bài này là giới thiệu một số kết quả về đa thức tương tự với các kết quả trong số học sơ cấp (xem [2] và [3]), chẳng hạn như thuật toán chia, thuật toán Euclid, và định lí cơ bản của số học. Bởi vì chúng thực sự rất tương tự nên một số chứng minh sẽ bị bỏ qua, hoặc viết vắn tắt. Các em học sinh nên viết lại cẩn thận tất cả các chứng minh để hiểu thêm về đa thức.

Trong bài K là \mathbb{C},\mathbb{R},\mathbb{Q}, hay \mathbb{F}_p.

Định lí 1 (Thuật toán chia). Cho f và g là các phần tử của K[x] với g\neq 0. Khi đó tồn tại duy nhất cặp phần tử (q,r) của K[x] thỏa mãn f=q g+r, và \deg (r)<\deg(g) hoặc r=0.

Chứng minh. Khẳng định là đúng một cách hiển nhiên nếu f=0 hoặc bậc của f bé hơn bậc của g. Bây giờ ta xét trường hợp còn lại và chứng minh nó bằng quy nạp theo bậc của f.

Nếu bậc của f bằng 0 thì bậc của g bằng 0 và khẳng định là đúng. Giả sử khẳng định đúng với mọi đa thức f có bậc bé hơn m. Xét một đa thức f có bậc m và một đa thức g khác không có bậc n\leq m. Viết f(x)=a_m x^m+\ldots+a_1 x+a_0 và g(x)=b_n x^n+\ldots+b_0.

Xét đa thức f_1(x)=f(x)-a_m b_n^{-1} x^{m-n} g(x). Ta có f_1 có bậc bé hơn m hoặc f_1=0 nên theo giả thiết quy nạp, ta có thể viết f_1=q_1 g+r, trong đó bậc của r bé hơn n hoặc r=0. Từ đây ta có f(x)=\left(q_1(x)+a_m b_n^{-1} x^{m-n}\right) g(x)+r(x). Bây giờ ta đi chứng minh phần còn lại, thương và dư là duy nhất. Giả sử f=q_1 g+r_1 và f=q_2 g+r_2. Khi đó \left(q_1-q_2\right) g=r_2-r_1. Nếu q_2-q_1 \neq 0 thì bậc của \left(q_2-q_1)\right) g không bé hơn bậc của g, trong khi bậc của r_2-r_1 bé hơn bậc của g, vô lý. Vậy q_1=q_2, và đương nhiên r_1=r_2. \Box

Định nghĩa 1. Cho hai đa thức không đồng thời bằng không f và g với hệ số trong K. Một đa thức monic d với hệ số trong K được gọi là ước chung lớn nhất của f và g nếu

(1) d là một ước của f và g, và

(2) mỗi ước của f và g cũng là một ước của d.

Ước chung lớn nhất của f và g được ký hiệu bởi (f, g). Nếu (f, g)=1 thì ta nói f và g nguyên tố cùng nhau.

Ước chung lớn nhất nếu có sẽ là duy nhất. Thật vậy, giả sử d và d_1 cùng là ước chung lớn nhất của f và g. Khi đó d \mid d_1 và d_1 \mid d, suy ra d=a d_1 và d_1=b d, do đó d=a b d. Từ đây ta có ab=1, suy ra a và b đều có bậc không. Do đó d_1 bằng d nhân với một đa thức hằng, nhưng chúng cùng monic nên d=d_1. Định lí sau chứng tỏ ước chung lớn nhất tồn tại.

Định lí 2. Với các đa thức không đồng thời bằng không f, g \in K[x], ước chung lớn nhất tồn tại và có thể biểu diễn dưới dạng (f, g)=a f+b g, với a,b \in K[x].

Chứng minh. Xét tập hợp I=\{a f+b g \mid a, b \in K[x]\}. Tập hợp I chứa ít nhất một đa thức khác không nên tồn tại đa thức monic d thuộc I mà có bậc nhỏ nhất. Dễ chứng minh được d=(f, g). \Box

Thuật toán Euclid. Cho f, g \in K[x] là hai đa thức khác không. Dùng thuật toán chia ta có f=q g+r, trong đó \deg(r)<\deg(g) hoặc r=0. Nếu r=0 thì g chia hết f, do đó (f, g)=c g với c\in K. Nếu không, ta có tập các ước chung của f và g bằng tập các ước chung của g và r, do đó (f,g)=(g,r). Quy trình này làm giảm bậc của đa thức nên nó phải kết thức sau hữu hạn bước, lúc đó ta tìm được (f,g). Tương tự như với số nguyên, dùng thuật toán này ta có thể tìm được các đa thức a và b sao cho (f, g)=a f+b g.

Định lí 3. Cho f, g,h \in K[x] với (h, f)=1 và h\mid fg. Khi đó h\mid g.

Chứng minh. Bạn đọc tự chứng minh xem như bài tập. \Box

Định nghĩa 2. Một đa thức khác hằng với hệ số trong K được gọi là bất khả quy trên K nếu nó không thể phân tích trong K[x] thành tích của hai đa thức có bậc nhỏ hơn. Nó được gọi là khả quy trên K nếu có phân tích như vậy.

Ví dụ. Đa thức x^2-x+1 bất khả quy trên \mathbb{R} nhưng khả quy trên \mathbb{C}.

Tất cả những đa thức bậc 1 là bất khả quy trên K. Mỗi đa thức có bậc lớn hơn 1 có nghiệm trong K sẽ khả quy trên K. Ngược lại không đúng, một đa thức khả quy vẫn có thể không có nghiệm trong K. Tuy nhiên, với các đa thức bậc 2 hay 3 ta có kết quả sau:

Định lí 4. Một đa thức có bậc 2 hay 3 bất khả quy trên K khi và chỉ khi nó không có nghiệm trong K.

Tương tự như với số nguyên ta có các định lí sau. Bạn đọc tự chứng minh chúng xem như bài tập.

Định lí 5. Đa thức khác hằng p \in K[x] bất khả quy trên K khi và chỉ khi với mỗi f,g \in K[x], p\mid fg kéo theo p \mid f hoặc p \mid g.

Định lí 6. Mỗi đa thức khác hằng với hệ số trong K có thể viết như là một phần tử của K nhân với tích của các đa thức monic bất khả quy trên K. Nếu không kể đến thứ tự của các nhân tử thì biểu diễn này là duy nhất.

Continue reading “Z – K[x]” →