Chủ đề này có 4 trả lời

[ducvipdh12]

Xin được nêu ra 2 kết quả của nguyên lý Dirichlet liên quan đến dãy số:

Định lý 1: (Weil,về sự phân bố đều) Nếu $\alpha$ là số vô tỉ thì dãy $\left \{ n\alpha \right \}_{n=1}$ phân bố đều trên khoảng $(0,1)$

Định lý 2: (Về sự tuần hòan của các số dư) Cho dãy số nguyên $\left \{ x_n \right \}$ xác định bởi công thức truy hồi $x_{n+k}=a_1x_{n+k-1}+...+a_kx_n$ và $k$ số hạng đầu tiên nguyên. Khi đó, với mọi số nguyên dương $N$, dãy số dư của $x_n$ khi chia cho $N$ sẽ tuần hòan 

P/S: phần ví dụ và bài tập tối mình sẽ đánh

Bài viết đã được chỉnh sửa nội dung bởi ducvipdh12: 01-06-2015 - 21:14

[ducvipdh12]

Ví dụ 1: ( tạp chí AMM ) Xét $n$ số nguyên dương $a_1< a_2<...a_n\leq 2n$ sao cho $\left [ a_i,a_j \right ]>2n$ với mọi $i\neq j$. Chứng minh rằng $a_1> \frac{2n}{3}$

Giải: Nếu $a_1\leq \frac{2n}{3}$, ta xét $n+1$ số $2a_1,3a_1,a_2,...,a_n$. Các số này đều không lớn hơn $2n$ và không có số nào là bội của số nào. Điều này mâu thuẫn với kết quả bài tóan trên

 

Ví dụ 2: ( Canada,2000 ) Cho $A=(a_1,a_2,...,a_n)$ là dãy các số nguyên thuộc đoạn $[-1000,1000]$. Giả sử tổng các số hạng của $A$ bằng $1$. CMR tồn tại một dãy con ( chứa ít nhất 1 phần tử ) của $A$ có tổng bằng $0$

Giải: Ta có thể giả sử trong $A$ không có phần tử nào bằng $0$, vì nếu ngược lại bài tóan hiển nhiên. Ta sắp xếp dãy $A$ thành dãy $B=(b_1,b_2,...,b_{2000})$ bằng cách chọn dần từ các số hạng của dãy $A$ theo quy tắc sau: $b_1>0,b_2<0$. Với mỗi $i\geq 3$ chọn $b_i$ là  số có dấu ngược với dấu của tổng $s_{i-1}=b_1+...+b_{i-1}$. Bằng cách xây dựng như thế, ta được $2000$ số $s_1,s_2,...,s_{2000}$ nằm trong đoạn $[-999,1000]$. Nếu trong các số $s_i$ có 1 số bằng $0$ thì bài tóan đúng. Trong trường hợp ngược lại, nguyên lý Dirichlet tồn tại $i<j$ sao cho $s_i=s_j$. Khi đó $b_{i+1}+...+b_j=0$

 

Bài tập:

Bài 1: Chứng minh rằng tồn tại vô hạn số hạng của dãy Fibonacci chia hết cho $2015$

Bài 2: Cho dãy số $(a_n)$ được xác định bởi:

$\left\{\begin{matrix} a_0=29,a_1=105,a_2=381 & \\ a_{n+3}=3a_{n+2}+2a_{n+1}+a_n(1)\forall n\geq 0& \end{matrix}\right.$

Chứng minh rằng với mỗi số nguyên dương $m$ luôn tồn tại số tự nhiên $n$ sao cho các số $a_n,a_{n+1}-1,a_{n+2}-2$ đều chia hết cho $m$

Bài 3: Cho dãy số $(x_n)$ xác định bởi:

$\left\{\begin{matrix} x_0=22,x_1=9 & \\ x_{n+2}=x_{n+1}.x_n+1\forall n\geq 0 & \end{matrix}\right.$

a/ Cho $p$ là số nguyên tố. Chứng minh rằng nếu tồn tại $x_k\vdots p$ thì tồn tại $m>k$ sao cho $x_m\vdots p$

b/ Giả sử $x_k\vdots p$ và $k\geq 1$. Chứng minh rằng dãy $(x_n)$ tuần hoàn kể từ chỉ số $n\geq k$

[ducvipdh12]

xin được phân tích và giải bài tóan số 1:

Khi nhìn số 2015, chắc nhiều bạn cũng đóan nhận được là có thể giải bài tóan trong trường hợp tổng quát. Vì vậy khi nếu chúng ta xử lý được bài tóan tổng quát thì sẽ xử lý được với bất kỳ con số nào, có thể là 2015,2016,...

Bài tóan tổng quát:

Chứng minh tồn tại vô hạn số tự nhiên của dãy FIbonacci chia hết cho $n$

Xét các cặp số dư khi chia 2 số hạng liên tiếp trong dãy Fibonacci theo modulo $n$ $(F_0,F_1);(F_1,F_2);...;$

Vì dãy Fibonacci là vô hạn mà chỉ có $n^2$ khả năng cho mỗi cặp số dư theo modulo $n$ nên tồn tại $(F_i,F_{i+1})$ sao cho $F_i\equiv F_{i+m};F_{i+1}\equiv F_{i+m+1}$ ( mod $n$ ) với $m\in \mathbb{Z^+}$

Xét $i> 1$ ta có: $F_{i-1}=F_{i+1}-F_i\equiv F_{i+m+1}-F_{i+m}=F_{i+m-1}$ ( mod $n$ )

Quá trình cứ tiếp diễn dẫn đến $F_j\equiv F_{j+m}$ ( mod $n$ ) $\forall j\geq 0$

Suy ra $0\equiv F_0\equiv F_m\equiv ...$ ( mod $n$ ), tức là có vô hạn các số $F_{km}$ thỏa mãn yêu cầu bài tóan

DPCM

[Karl Heinrich Marx]

xin được phân tích và giải bài tóan số 1:

Khi nhìn số 2015, chắc nhiều bạn cũng đóan nhận được là có thể giải bài tóan trong trường hợp tổng quát. Vì vậy khi nếu chúng ta xử lý được bài tóan tổng quát thì sẽ xử lý được với bất kỳ con số nào, có thể là 2015,2016,...

Bài tóan tổng quát:

Chứng minh tồn tại vô hạn số tự nhiên của dãy FIbonacci chia hết cho $n$

Xét các cặp số dư khi chia 2 số hạng liên tiếp trong dãy Fibonacci theo modulo $n$ $(F_0,F_1);(F_1,F_2);...;$

Vì dãy Fibonacci là vô hạn mà chỉ có $n^2$ khả năng cho mỗi cặp số dư theo modulo $n$ nên tồn tại $(F_i,F_{i+1})$ sao cho $F_i\equiv F_{i+m};F_{i+1}\equiv F_{i+m+1}$ ( mod $n$ ) với $m\in \mathbb{Z^+}$

Xét $i> 1$ ta có: $F_{i-1}=F_{i+1}-F_i\equiv F_{i+m+1}-F_{i+m}=F_{i+m-1}$ ( mod $n$ )

Quá trình cứ tiếp diễn dẫn đến $F_j\equiv F_{j+m}$ ( mod $n$ ) $\forall j\geq 0$

Suy ra $0\equiv F_0\equiv F_m\equiv ...$ ( mod $n$ ), tức là có vô hạn các số $F_{km}$ thỏa mãn yêu cầu bài tóan

DPCM

Sau bài toán này em liên hệ được điều gì?

Về cơ bản là nhờ $F_0=0$ nên bài toán đúng với mọi $n$. Nhưng đâu chỉ dãy dirichlet mới có $F_0$ bằng 0. Kết hợp với đl 2 ở trên có thể suy ra nếu mà $u_0=0$ với mọi dãy số truy hồi $u_n$ thì dãy tồn tại vô số số chia hết cho $n$. Nhưng $u_0$ nó rõ ràng quá giả dụ ta cho $u_1=-2,u_2=5,u_3=4$ sau đấy thiết lập một công thức truy hồi $u_{n+3}=au_{n+2}+bu_{n+1}+cu_n$ ta thiết kế $a,b,c$ sao cho tính toán một chút được $u_5=0$ chẳng hạn, như vậy ta sẽ thu được một bài toán cho  $u_1=-2,u_2=5,u_3=4$ và $u_{n+3}=au_{n+2}+bu_{n+1}+cu_n$ cmr có vô hạn số hạng của dãy chia hết cho $n$ hoặc người ta muốn đánh lạc hướng hơn tí thì bảo là chia hết cho mọi số nguyên tố $p$. Muốn nó lắt léo hơn một chút thì thông thường chúng ta quan niệm một cách đơn thuần một dãy số $u_n$ thường bắt đầu từ $u_0$ hoặc $u_1$ rồi đi dần lên, nhưng khái niệm "tuần hoàn số dư" làm ta nghĩ đến dãy số này như một vòng tròn nó sẽ quay đêu và lặp lại, mà vòng tròn k có điểm bắt đầu, thế thì trước $u_0$ vẫn có thể có $u_{-1},u_{-2}$ chẳng sao cả. Vậy giờ ta tìm $a,b,c$ sao cho nếu mà tính ngược về $u_{-2}=0$ chẳng hạn thì lại ra một bài toán mới!

Muốn màu mè thêm một chút thì bài này ta dễ dàng thấy $u_n$ là số nguyên thì giờ thêm hệ số vào  $t.u_{n+3}=au_{n+2}+bu_{n+1}+cu_n$ thiết kế các hệ số sao cho dãy này lúc nào cũng nguyên thế là lại ra một bài toán mới!

Hoặc đặt ra giả dụ một dãy dạng $u_{n+1}=au_n+bu_{n-1}^2$ chẳng hạn thì nó có tuần hoàn số dư không?.....Chẳng bao giờ thiếu cách để đặt ra vấn đề.

Có quá nhiều cách để phát triển lên từ một ý tưởng ta cảm thấy thú vị! Vấn đề là phải đánh bật tư duy của mình ra ngoài những khuôn phép, ngoài những định kiến vốn cho là quen thuộc. Từ đây bạn có thể tạo ra một lớp các vấn đề rồi theo dạng toán này rồi! Thử bắt tay vào những ý tưởng nêu trên xem thế nào?

Bài viết đã được chỉnh sửa nội dung bởi Karl Heinrich Marx: 07-06-2015 - 23:43

[hxthanh]

Nhân tiện nói về sự tuần hoàn của các số dư, tôi xin kể cho các bạn một chuyện thế này:

Ngày trước, tôi được dạy về phương pháp quy nạp toán học như thế này: Để chứng minh mệnh đề $f(n)$ nào đó đúng với mọi số nguyên $n$ từ $n_{min}$ nào đó trở đi. Đầu tiên ta xác nhận rằng $f(n_{min})$ đúng. Sau đó giả sử $f(n)$ đúng, suy ra được $f(n+1)$ đúng! Vậy là xong!

Nguyên lý thật đơn giản! $f(n)\Rightarrow f(n+1)$ rồi $f(n+1)\Rightarrow f(n+2)$, v.v...

Tôi tự hỏi rằng có nhất thiết phải từ $f(n)$ đúng rồi suy ra $f(n+1)$ đúng mới là đúng quy tắc, đúng phương pháp quy nạp hay không?

Giả sử có trường hợp $f(n)$ đúng, nhưng tôi không thể suy ra được $f(n+1)$ đúng thì phải làm thế nào? Hay phương pháp quy nạp là không thể sử dụng được?

Giả sử từ $f(n)$ đúng, tôi chỉ suy ra được $f(n+3)$ đúng, nhưng tôi kiểm tra thấy $f(0), f(1), f(2)$ đều đúng? Vậy $f(n)$ đã được chứng minh bằng quy nạp hay chưa?

Câu trả lời: Đó chính là ĐPCM!

Thậy vậy:

$f(0)\Rightarrow f(3)\Rightarrow f(6)\Rightarrow ...\Rightarrow f(3k)$

$f(1)\Rightarrow f(4)\Rightarrow f(7)\Rightarrow ...\Rightarrow f(3k+1)$

$f(2)\Rightarrow f(5)\Rightarrow f(8)\Rightarrow ...\Rightarrow f(3k+2)$

Chúng ta cùng xem xét ví dụ sau:

 

Chứng minh rằng: Với $n$ không âm, $m$ nguyên dương ta có:
$$\sum_{k=0}^n \left\lfloor\frac{k}{m}\right\rfloor=\left(n+1-\frac{m}{2}\right)\left\lfloor\frac{n}{m}\right\rfloor-\frac{m}{2}\left\lfloor\frac{n}{m}\right\rfloor^2\quad(1)$$

Bài này nếu dùng nguyên tắc quy nạp thông thường thì đúng là không được rồi! Còn để chứng minh trực tiếp (tìm hiểu xem công thức ở đâu mà ra) thì cũng tốn không ít chất xám đâu! Thế nhưng nếu áp dụng phương pháp quy nạp "kiểu đồng dư" thì không thành vấn đề:

- Dễ thấy với $0\le n\le m-1$ thì $VT = VP=0$

- Giả sử $(1)$ đúng với $n$, ta chứng minh rằng $(1)$ cũng đúng với $n+m$

$\sum_{k=0}^{n+m} \left\lfloor\frac{k}{m}\right\rfloor=\sum_{k=0}^n \left\lfloor\frac{k}{m}\right\rfloor+\sum_{k=n+1}^{n+m}\left\lfloor\frac{k}{m}\right\rfloor=\sum_{k=0}^n \left\lfloor\frac{k}{m}\right\rfloor+\sum_{k=0}^{m-1}\left\lfloor\frac{n+1+k}{m}\right\rfloor$

 

$=\left(n+1-\frac{m}{2}\right)\left\lfloor\frac{n}{m}\right\rfloor-\frac{m}{2}\left\lfloor\frac{n}{m}\right\rfloor^2+n+1\quad$ (Theo giả thiết quy nạp và định lý Hermite)

 

Mặt khác, khi thay $n$ bởi $n+m$ ở VP của $(1)$, ta được:

 

$\left(n+1-\frac{m}{2}+m\right)\left(\left\lfloor\frac{n}{m}\right\rfloor+1\right)-\frac{m}{2}\left(\left\lfloor\frac{n}{m}\right\rfloor+1\right)^2$

 

$=\left(n+1-\frac{m}{2}\right)\left\lfloor\frac{n}{m}\right\rfloor+m\left\lfloor\frac{n}{m}\right\rfloor+n+1+\frac{m}{2}-\frac{m}{2}\left\lfloor\frac{n}{m}\right\rfloor^2-m\left\lfloor\frac{n}{m}\right\rfloor-\frac{m}{2}$

 

$=\left(n+1-\frac{m}{2}\right)\left\lfloor\frac{n}{m}\right\rfloor-\frac{m}{2}\left\lfloor\frac{n}{m}\right\rfloor^2+n+1$

 

Từ đó ta có ĐPCM