Định lý Dirichle

(Định lí Dirichle) Cho $\alpha$ là một số vô tỉ. Chứng minh rằng, tồn tại vô hạn các số nguyên p,q với q>0 sao cho:

$|\alpha -\frac{p}{q}| <\frac{1}{q^2}$

Lời giải:

Trước hết ta chứng minh với mọi $ N \ge q$ luôn tồn tại p,q thỏa mãn:

$|\alpha -\frac{p}{q}| <\frac{1}{qN}$

Thật vậy ta chia các [0;1) thành các khoảng $[\frac{k-1}{N};\frac{k}{N})(k =\overline{1,N})$

Thì theo nguyên lý Dirichle sẽ tồn tại hai số { $\alpha q_i$ } và { $\alpha q_j$ } thuộc vào một đoạn (  q= 0,1,..N)

$\Rightarrow \left | \begin{Bmatrix}
\alpha q_i
\end{Bmatrix}- \begin{Bmatrix}
\alpha q_j
\end{Bmatrix} \right |<\frac{1}{N(q_i-q_j)}\\\Rightarrow \left | \alpha -\frac{\begin{bmatrix}
\alpha q_i
\end{bmatrix}-\begin{bmatrix}
\alpha q_j
\end{bmatrix}}{q_i-q_j} \right | <\frac{1}{N(q_i-q_j)}$ Điều phải chứng minh.

Ta giả sử chỉ có hữu hạn các số p,q thỏa mãn đề bài Kí hiệu tập này là X.

Khi đó sẽ tồn tại M sao cho $|\alpha -\frac{p}{q}| >M$

Chọn N sao cho $\frac{1}{M}<N$ Khi đó tồn tại các số nguyên dương $p_i, q_i$ sao cho
$|\alpha -\frac{p_i}{q_i}| <\frac{1}{q_iN} <\frac{1}{q_iN}<\frac{1}{q_i^2}$

Suy ra $p_i,q_i$ thuộc X, nhưng $M >\frac{1}{q_iN} $ (mâu thuẫn)

Vậy ta có điều phải chứng minh.

Dùng nguyên lí Dirichlet để giải bài toán tổ hợp - Phần 2

Bài toán: Tìm số tự nhiên n lớn nhát sao cho tồn tại n số nguyên không âm $x_1,x_2,..x_n$ không đồng thời bằng 0, sao cho với mọi $\varepsilon _1, \varepsilon _2,..\varepsilon _n$ $\in$ {-1;0;1} không đồng thời bằng 0 sao cho $n^3$ không chia hết cho $\varepsilon _1x_1+\varepsilon _2x_2+..\varepsilon _nx_n$

Lời giải.

Với n=9 ta chọn $1,2,2^2,..2^8$

Khi đó: $| \varepsilon _1+..+2^9\varepsilon _9|\le 1+2+..2^8<9^3$

Nếu $n\ge10$ không mất tính tổng quát, giả sử $n=10$ khi đó số tập con của S={$x_1,x_2,..z_10$} là $2^{10}$ và vì $2^{10}>10^3$ nên theo nguyên lí Dirichlet tồn tại hai tập A và B là tập con của S sao cho tổng các phần tử của A có cùng số dư với tổng các phần tử của B.

Khi đó đặt $\varepsilon _i=1$ nếu $x_i$ thuộc A nhưng không thuộc B, $\varepsilon _i=-1$ nếu $x_i$ thuôc B nhưng không thuộc A, bằng 0 trong trường hợp còn lại khi đó:

$\sum \varepsilon _ix_i \vdots n^3$

Dùng nguyên lí Dirichlet để giải bài toán tổ hợp-Phần 1

Bài toán: Gọi $n_1<n_2<..<n_{2000}<10^{100}$ là một số nguyên dương. Chứng minh rằng có thể tìm được hai tập A và B khác nhau không rỗng là tập con của {$n_1,n_2,..n_{2000}$} thỏa cấc điều kiện:

i) $|A|=|B|$

ii) $\sum_{x\in A}x=\sum_{x\in B}x$

iii) $\sum_{x\in A}x^2=\sum_{x\in B}x^2$

Lời giải

Lưu ý: $\binom{2000}{1000}$ là số hạng lớn nhất trong các số hạng $\binom{2000}{k}$.

Gọi S là tất cả tập con của tập {$n_1,n_2,..n_{2000}$} sao cho S có 1000 phần tử, ta có:

$0< \sum_{x\in S}x<1000.10^{100}$

$0< \sum_{x\in S}x^2<1000.10^{200}$

Vậy số các cặp $( \sum_{x\in S}x, \sum_{x\in S}x^2)$ ít hơn $10^{306}$

Mặt khác:

Số tập hợp chứa 1000 phần tử là: $\binom{2000}{1000}>\frac{\sum_{k=0}^{2000}\binom{2000}{k}}{2001}> \frac{2^{2000}}{2001}> \frac{10^{600}}{2001}>10^{306}$ 

Nên theo nguyên lí Dirichlet tồn tại hai tập hợp C và D chứa 1000 phần tử sao cho $( \sum_{x\in C}x, \sum_{x\in C}x^2)=( \sum_{x\in D}x, \sum_{x\in D}x^2)$

Loại bỏ các phần tử chung của C và D ta thu được hai tập A và B thỏa mãn điều kiện đề bài.

Nguyên lí Dirichlet và cách giải bằng tổng quát bài toán

Giải. Ta giải bài toán tổng quát sau

Cho hai dãy hữu hạn các số nguyên dương như sau:
$x_1 \le x_2 \le ..\le x_m\le n$; $y_1 \le y_2\ le...\le y_n \le m$ Khi đó tồn tại các chỉ số
$1 \le i_1 \le i_2 \le m; 1\le j_1 \le j_2 \le n$ sao cho:

$\sum_{i=i_1}^{i_2}x_i=\sum_{i=j_1}^{j_2}y_j$

Đặt: $a_p=\sum_{i=1}^{p}x_i (p \in Z, 1\le p \le m), b_q=\sum_{j=1}^{q}y_j(q \in Z, 1 \le q\le n)$

Vai trò của các số trên là như nhau nên ta có thể giả sử: $a_m \le b_n$

Lúc đó với mỗi p nhận giá trị từ 1 đến m tồn tại f(p) là chỉ số bé nhất mà $a_p \le b_{f(p)}$. Xét m hiệu:

$ b_{f(1)}-a_1; b_{f(2)}-a_2;.... b_{f(m)}-a_m. $

Ta chứng minh mọi hiệu đều bé hơn m. Thật vậy nếu có chỉ số p nào đó sao cho $m \le b_{f(p)}-a_p$ thì $m<b_{f(p)}$ suy ra f(p)>1 và
$m \le b_{f(p)-1}+y_{f(p)}-a_p$ nên $0 \le m-y_{f(p)} \le b_{f(p)-1}-a_p$ nên $a_p\le b_{f(p)-1}$ (mâu thuẫn)

Bây giờ nếu có 1 trong các $b_{f(i)}-a_i=0$ thì ta có cách chọn $i_1=j_1=1; i_2=i, j_2=f(i)$ thoả mãn đề bài

Nếu không có hiệu nào bằng không thì theo nguyên lí dirichlet tồn tại 2 hiệu bằng nhau tức là có r,s thoả mãn:

$b_{f(s)}-a_s=b_{f(r)}-a_r$ hay $b_{f(s)}-b_{f(r)}=a_s-a_r$

Chọn $i_1=r+1; i_2=s j_1=f(r)+1, j_2=f(s)$ ta cũng có đẳng thức đề bài.

Vậy ta có điều phải chứng minh.

Nhận xét: -Đôi khi tổng quát hoá bài toán lại là cách hữu hiệu để giải một bài toán rườm rà nào đó.
-Ta có thể thấy rằng mấu chốt của bài toán là giả sử $a_m \le b_n$ nếu như $b_n \le a_m$ thì sao ? do ta đã nói không mất tính tổng quát có nghĩa là nếu $b_n \le a_m$ thì chỉ việc thay x,z,m,i,p bởi y,b,n,j,q ta vẫn thu được lời giải chính xác.
- Chỉ số bé nhất f(p) chính là điều kiện chặt để giải bài toán ở đây ta đã dùng nguyên lí cực hạn
- Còn chứng minh mọi hiệu bé hơn m là để dùng dirichle