Lucas sequences and Vietnam TST 2023/4b

Cho $P$ và $Q$ là hai số nguyên lẻ nguyên tố cùng nhau thỏa mãn $D=P^2-4Q>0.$ Dãy Lucas $(U_n)$ và dãy Lucas đồng hành $(V_n)$ với tham số $P$ và $Q$ được xác định như sau: $U_0=0,U_1=1,U_n=PU_{n-1}-QU_{n-2},\quad\forall n\geq 2,$ và $V_0=2,V_1=P,V_n=PV_{n-1}-QV_{n-2},\quad\forall n\geq 2.$ Khi $P=1$ và $Q=-1$ ta có $(U_n)$ là dãy số Fibonacci. Vào quãng năm 1996, Paulo Ribenboim và Wayne L. McDaniel đã chứng minh được kết quả:

Định lí. Nếu $n$ là số tự nhiên sao cho một trong bốn số $U_n,2U_n,V_n$ và $2V_n$ là số chính phương thì $n<13.$

Phương pháp của họ như sau. Chẳng hạn giả sử $U_n$ là số một chính phương, khi đó với mỗi số nguyên dương lẻ $M$ nguyên tố cùng nhau với $U_n$ ta có ký hiệu Jacobi $(U_n\mid M)=1.$ Với hầu hết $n,$ họ chọn được các modulo $M_i$ sao cho $\prod (U_n\mid M_i)=-1,$ suy ra $U_n$ không phải là số chính phương, vô lý! Bạn đọc quan tâm có thể đọc trong bài:

$\text{[P-W]}$ Paulo Ribenboim and Wayne L. McDaniel, The Square Terms in Lucas Sequences. Journal of number theory 58, 104 -123 (1996).

Mục đích chính của tôi khi viết bài này chỉ là giới thiệu $\text{[P-W]}$ đến các đồng nghiệp và các học sinh. Trong đó có nhiều kết quả sơ cấp về dãy Lucas và dãy Lucas đồng hành, những dãy số mà chúng ta biết ít hơn so với dãy số Fibonacci. Tiếp theo tôi giới thiệu một lời giải cho bài toán sau, nó là ý b trong bài 4 của đề thi chọn đội tuyển IMO 2023.

Bài toán (TST2023/4b). Cho hai số nguyên dương lẻ $a>2$ và $b$ nguyên tố cùng nhau. Xét dãy số $(x_n)_{n\geq 0}$ xác định bởi $x_0=2,x_1=a,x_{n+2}=ax_{n+1}+bx_n,\quad\forall n\geq 0.$ Chứng minh rằng không tồn tại bộ ba số nguyên dương $(m,n,p)$ sao cho $mnp$ chẵn và $\displaystyle \frac{x_m}{x_nx_p}$ là số chính phương.

Lời giải. Với giả thiết của bài toán ta thấy $(x_n)$ là dãy Lucas đồng hành với tham số $P=a$ và $Q=-b,$ bởi vậy chúng ta có thể dùng các kết quả trong $\text{[P-W]}$ . Giả sử $(m,n,p)$ là một bộ ba số nguyên dương sao cho $mnp$ chẵn và $\displaystyle \frac{x_m}{x_nx_p}$ là số chính phương. Khi đó $x_n\mid x_m$ và $x_p\mid x_m,$ suy ra theo (9) trong $\text{[P-W]}$ (trang 107) ta có $m/n$ và $m/p$ là các số nguyên dương lẻ. Do đó cấp $2-$ adic của $m,n$ và $p$ bằng nhau, để ý thêm $mnp$ chẵn ta có $m,n$ và $p$ đều chẵn. Bây giờ theo bổ đề 1 trong $\text{[P-W]}$ ta có $(2\mid D)=1,$ điều này không thể xảy ra vì $(2\mid D)=(-1)^{\frac{D^2-1}{8}}=-1.$

Bài toán được giải.

—

Vậy tôi giải được bài toán này nhờ tôi biết nhiều, chứ không cần điều gì đặc biệt. Có đúng không các bạn học sinh? 🙂

—

18/04/2023: Anh Nguyễn Xuân Thọ (Đại học Bách Khoa) cho tôi biết là kết quả TST2023/4b này đã có trong Colloquium Mathematicum, Vol. 130, No. 1, 2013.

Một điểm không phù hợp nữa của bài toán này là đoạn đặc trưng các cặp $(m,n)$ sao cho $x_m\mid x_n$ đã có trong đề thi chọn HSG QG năm 2018, cụ thể là Bài 6.

IMO2021/6

Trong bài này tôi giới thiệu hai lời giải cho bài 6 trong đề thi IMO 2021, lời giải thứ hai có dùng bổ đề Siegel mà tôi đã giới thiệu cách đây rất lâu ở đường dẫn https://nttuan.org/2007/10/21/siegel/. Các bạn có thể tìm các bài toán khác trong đề IMO 2021 ở đây https://nttuan.org/2021/07/25/imo2021/

Bài toán (IMO2021/6). Cho số nguyên $m\ge 2,$ $A$ là một tập hữu hạn các số nguyên và $B_1,$ $B_2,$ …, $B_m$ là các tập con của $A$ . Giả sử rằng với mỗi $k=1,2,...,m$ , tổng các phần tử của $B_k$ là $m^k$ . Chứng minh rằng $A$ có ít nhất $\frac{m}{2}$ phần tử.

Lời giải 1. Đặt $k=|A|$ và giả sử $A = \{a_1,a_2,\ldots,a_k\}$ . Từ giả thiết, với mỗi $i\in [m]$ , ta có $\displaystyle m^i = \sum_{j=1}^{k}b_{i,j}a_{j}\quad (1)$ với các $b_{i,j} \in \{0;1\}$ . Với mỗi $0 \le x \le m^{m}-1$ , biểu diễn $mx$ theo cơ số $m$ và kết hợp với $(1)$ ta được $\displaystyle mx = \sum_{j=1}^{k}c_{j}a_{j},$ trong đó các $c_j$ là số nguyên thỏa mãn $0 \le c_j \le (m-1)m,\quad\forall j\in [k]$ . Vế trái của đẳng thức này nhận đúng $m^{m}$ giá trị, do đó $\displaystyle m^{m} \le [m(m-1)+1]^{k} < m^{2k},$ suy ra $|A|=k>m/2$ . $\Box$

Continue reading →

Square roots are linearly independent

Trong bài này tôi giới thiệu nhiều lời giải cho bài toán quan trọng sau:

Bài toán. Cho $a_1,\ldots,a_k$ là các số nguyên không đồng thời bằng $0$ . Chứng minh rằng nếu $n_1,$ $n_2,\ldots,$ $n_k$ là các số nguyên dương đôi một khác nhau và không có ước chính phương lớn hơn $1$ thì $\sum a_i\sqrt{n_i}\not=0$ .

Lời giải 1. Ta sẽ chứng minh bằng quy nạp theo $N$ , số ước nguyên tố của $\prod n_i$ , khẳng định: Tồn tại tổng $S'=\sum b_i\sqrt{m_i}$ sao cho $SS'$ là số nguyên khác $0$ , ở đây $m_i$ là các số nguyên dương đôi một khác nhau và không có ước chính phương khác $1$ , tập các ước nguyên tố của $\prod m_i$ là tập con của tập các ước nguyên tố của $\prod n_i$ , $b_i$ là các số nguyên, và $S=\sum a_i\sqrt{n_i}$ . Từ đó suy ra $S\not=0$ .

Với $N=0$ ta chọn $S'=1$ .

Với $N=1$ ta chọn $S'=\sqrt{p_1}$ khi $S=a_1\sqrt{p_1}$ , chọn $S'=-a_1\sqrt{p_1}+a_2$ nếu $S=a_1\sqrt{p_1}+a_2$ .

Continue reading →

Tài liệu cho học sinh lớp 10 Chuyên toán

Trong bài này chúng tôi sẽ giới thiệu một số cuốn sách hoặc bài giảng mà học sinh chuẩn bị vào học lớp 10 Chuyên toán nên có.

[1] Tài liệu giáo khoa chuyên toán, Đại số 10

[2] Tài liệu giáo khoa chuyên toán, Hình học 10

[3] Chen Chuan-Chong và Koh Khee-Meng., Principles and Techniques in Combinatorics

[4] Hojoo Lee., Topics in Inequalities

[5] Dusan Djukic., Polynomials in One Variable

[6] David Burton., Elementary Number Theory

[7] B.J. Venkatachala., Functional Equations

Lagrange interpolating polynomial

Đây là bài thứ bốn về đa thức của tôi, các bạn học sinh nên xem lại ba bài trước để học cho dễ dàng hơn.

[1] https://nttuan.org/2007/10/26/poly01/

[2] https://nttuan.org/2009/01/11/poly02/

[3] https://nttuan.org/2018/08/25/poly03/

—

Đa thức có thể được sử dụng để xấp xỉ các đường cong phức tạp, hay tính giá trị của các hàm logarit và lượng giác. Đầu tiên, chọn một vài dữ liệu đã biết, sau đó tìm một đa thức có bậc đủ bé có cùng dữ liệu đã chọn, cuối cùng xem đa thức vừa tìm được như là hàm số đang xét. Điều này dẫn đến việc tính toán nhanh hơn đáng kể.

Định lí. Cho số nguyên dương $n$ và $n+1$ số phức đôi một khác nhau $x_0,$ $x_1,$ $\ldots,$ $x_{n}.$ Khi đó với mỗi $n+1$ số phức $y_0,$ $y_1,$ $\ldots,$ $y_n,$ có đúng một đa thức $P(x)$ với hệ số phức có bậc không lớn hơn $n$ sao cho

$P(x_i)=y_i,\quad \forall i=\overline{0,n}.$

Chứng minh. Nếu $P$ và $Q$ là các đa thức thỏa mãn các điều kiện của định lí thì đa thức $P-Q$ có bậc không lớn hơn $n$ và có ít nhất $n+1$ nghiệm, suy ra $P-Q$ là đa thức không và $P=Q.$ Mặt khác, đa thức $\displaystyle P(x)=\sum_{i=0}^ny_i\prod_{j\not =i}\frac{x-x_j}{x_i-x_j}$ thỏa mãn $P(x_i)=y_i,\quad \forall i=\overline{0,n},$ do đó định lí được chứng minh. $\Box$

Hệ quả (Công thức nội suy Lagrange). Cho số nguyên dương $n$ và đa thức $P(x)$ với hệ số phức có bậc không lớn hơn $n.$ Khi đó với mỗi $n+1$ số phức đôi một khác nhau $x_0,$ $x_1,$ $\ldots,$ $x_{n},$ ta có

$\displaystyle P(x)=\sum_{i=0}^nP(x_i)\prod_{j\not =i}\frac{x-x_j}{x_i-x_j}.$

Trong công thức trên, $n+1$ số phức $x_0,$ $x_1,$ $\ldots,$ $x_{n}$ được gọi là các nút nội suy. Ta thường dùng công thức nội suy Lagrange trong tình huống: Biết thông tin của $P$ tại các $x_i$ , cần tìm thông tin của $P$ tại $y\not\in \{x_i\}.$

Ví dụ 1. Cho hai đa thức $A(x)=x^{81}+x^{49}+x^{25}+x^9+x$ và $B(x)=x^3-x.$ Tìm dư khi chia $A(x)$ cho $B(x).$

Lời giải. Giả sử $Q(x)$ và $R(x)$ lần lượt là thương và dư trong phép chia $A(x)$ cho $B(x).$ Ta có $A(x)=B(x)Q(x)+R(x)$ và $\deg R<3.$ Vì $B(0)=B(1)=B(-1)=0$ nên $R(0)=0,$ $R(1)=5$ và $R(-1)=-5,$ do đó áp dụng công thức nội suy Lagrange cho $R$ với các nút $0;1$ và $-1$ ta có

$\displaystyle R(x)=R(0).\frac{(x-1)(x+1)}{(0-1)(0+1)}+R(1).\frac{(x-0)(x+1)}{(1-0)(1+1)}+R(-1).\frac{(x-0)(x-1)}{(-1-0)(-1-1)}$

$\displaystyle =\frac{5}{2}x(x+1)-\frac{5}{2}x(x-1)=5x.$ $\Box$

Ví dụ 2. Cho số nguyên dương $n$ và đa thức $P$ có bậc $n$ thỏa mãn $\displaystyle P(k)=\frac{k}{k+1},\quad \forall k=\overline{0,n}.$ Tính $P(n+1).$

Lời giải. Do $P$ có bậc $n$ nên áp dụng công thức nội suy Lagrange cho $P$ với $n+1$ nút $0,$ $1,$ $\ldots,$ $n$ ta có $\displaystyle P(x)=\sum_{k=0}^nP(k)\prod_{j\not =k}\frac{x-j}{k-j}$

$\displaystyle =\sum_{k=0}^n\frac{k}{k+1}\prod_{j\not =k}\frac{x-j}{k-j}=\sum_{k=0}^n\frac{(-1)^{n-k}k}{(k+1)!(n-k)!}\prod_{j\not =k}(x-j),\quad\forall x\in\mathbb{R}.$ Suy ra

$\displaystyle P(n+1)=\sum_{k=0}^n\frac{(-1)^{n-k}k}{(k+1)!(n-k)!}\prod_{j\not =k}(n+1-j)$

$\displaystyle =\sum_{k=0}^n\frac{(-1)^{n-k}k}{(k+1)!(n-k)!}.\frac{(n+1)!}{n+1-k}$

$\displaystyle =\frac{1}{n+2}\sum_{k=0}^nk(-1)^{n-k}C^{k+1}_{n+2}=\frac{1}{n+2}\sum_{k=0}^n\left[(k+1)(-1)^{n-k}C_{n+2}^{k+1}+(-1)^{n-k+1}C_{n+2}^{k+1}\right]$

$\displaystyle =\frac{1}{n+2}\left(\sum_{k=0}^n(-1)^{n-k}(n+2)C_{n+1}^k+\sum_{i=1}^{n+1}(-1)^{n+2-i}C_{n+2}^i\right)=\dfrac{n+1+(-1)^{n+1}}{n+2}. \Box$

Ví dụ 3. Cho số nguyên dương $n$ và các số nguyên $x_0 > x_1 > \ldots > x_n.$ Chứng minh rằng một trong các số $|F(x_0)|,$ $|F(x_1)|,$ $|F(x_2)|,$ $\ldots,$ $|F(x_n)|$ lớn hơn hoặc bằng $\displaystyle \frac{n!}{2^n}.$ Trong đó

$F(x) = x^n + a_1x^{n-1} + \cdots+ a_n$

là một đa thức với hệ số thực.

Lời giải. Giả sử $\displaystyle |F(x_i)|<\dfrac{n!}{2^n},\quad \forall i=\overline{0,n}.$ Áp dụng công thức nội suy Lagrange cho $P$ với $n+1$ nút $x_0,$ $x_1,$ $\cdots,$ $x_n$ ta có

$\displaystyle x^n + a_1x^{n-1} + \cdots+ a_n\equiv \sum_{k=0}^nF(x_k)\prod_{j\not =k}\frac{x-x_j}{x_k-x_j},$ để ý đến hệ số của $x^n$ trong hai vế ta có $\displaystyle 1=\left|\sum_{k=0}^n\prod_{j\not =k}\frac{F(x_k)}{x_k-x_j}\right|\leq \sum_{k=0}^n\prod_{j\not =k}\frac{|F(x_k)|}{|x_k-x_j|}<$ $\displaystyle \sum_{k=0}^n\prod_{j\not =k}\frac{\frac{n!}{2^n}}{|x_k-x_j|}\leq \sum_{k=0}^n\prod_{j\not =k}\frac{\frac{n!}{2^n}}{|k-j|}=1,$ không thể xảy ra điều này. $\Box$

Ví dụ 4. Chứng minh rằng với mỗi số thực $a$ và với mỗi số nguyên dương $n$ ta có

$\displaystyle \sum_{k = 0}^n( - 1)^k\binom{n}{k}(a - k)^n = n!.$

Lời giải. Vế trái là đa thức của $a$ nên chỉ cần chứng minh đẳng thức khi $a$ là số nguyên. Sau đây ta chứng minh đẳng thức khi $a= 0$ và $n\geq 3$ , hay chứng minh

$\displaystyle \sum_{k = 0}^n( - 1)^{n + k}\binom{n}{k}k^n = n!.$ Theo công thức nội suy Lagrange với các nút $1,$ $2,$ $\ldots,$ $n$ ta có $\displaystyle x^n - (x - 1)(x - 2)\cdots (x - n) \equiv \sum_{k = 1}^nk^n\cdot\prod_{i\not = k}\dfrac{x - i}{k - i},\quad\forall x\in\mathbb{R}.$ Nói riêng, khi $x = 0$ ta có $\displaystyle ( - 1)^{n + 1}\cdot n! = \sum_{k = 1}^nk^n\cdot \dfrac{1}{k}\cdot \dfrac{( - 1)^{n - 1}\cdot n!}{(k - 1)!\cdot (n - k)!\cdot ( - 1)^{n - k}},$ từ đây thu được điều cần chứng minh. $\Box$ .

Continue reading →