Định lý Dirac và ứng dụng

Định lý  (Dirac 1952)

Đơn đồ thị vô hướng G với n>2 đỉnh, mỗi đỉnh có bậc không nhỏ hơn n/2 là đồ thị Hamilton.

Chứng minh:

Ký hiệu n đỉnh của G là ${\displaystyle v_{1},v_{2},v_{3},...,v_{n}}$.

Không mất tính tổng quát giả sử đường đi H dài nhất của G là ${\displaystyle v_{1}v_{2}v_{3}...v_{l}}$. H có độ dài là l. Như vậy mọi đường đi đơn của G có độ dài nhỏ hơn l+1.

Nếu ${\displaystyle l=n}$ thì suy ra luôn điều phải chứng minh.

Xét trường hợp ${\displaystyle l<n}$.

Gọi tất cả các đỉnh liền kề với ${\displaystyle v_{l}}$ là ${\displaystyle v_{i_{1}},v_{i_{2}},...,v_{i_{t}}}$ (với ${\displaystyle 0<i_{1}<i_{2}<...<i_{t}<n+1}$ và ${\displaystyle t}$≥${\displaystyle {\frac {n}{2}}}$). Dễ thấy ${\displaystyle {i_{j}}<l}$ với mọi j chạy từ 1 tới t, vì nếu tồn tại ${\displaystyle {i_{j}}>l}$, thì suy ra tồn tại đường đi có độ dài l+1:

${\displaystyle v_{1}v_{2}v_{3}...v_{l}v_{i_{j}}}$.

Nếu đỉnh ${\displaystyle v_{l+1}}$ mà liền kề với đỉnh ${\displaystyle v_{i_{j}+1}}$ thì ta sẽ tạo được đường đi có độ dài l+1:

${\displaystyle v_{1}v_{2}...v_{i_{j}-1}v_{i_{j}}v_{l}v_{l-1}...v_{i_{j}+1}v_{l+1}}$

(vô lý).

Vậy ${\displaystyle v_{l+1}}$ không liền kề với các đỉnh ${\displaystyle v_{i_{j}+1}}$, với j chạy từ 1 đến t. Mà ${\displaystyle t}$≥${\displaystyle {\frac {n}{2}}}$, nên suy ra bậc của ${\displaystyle v_{l+1}}$ nhỏ hơn ${\displaystyle {\frac {n}{2}}}$ (vô lý).

Vậy trường hợp l<n là không tồn tại.

Suy ra điều phải chứng minh.

Ứng dụng của nó là bài toán nổi tiếng sau:

Bài toán: Tại một hội nghị có 2n quan khách.trong đó mỗi quan khách có nhiều nhất n-1 kẻ thù.chứng minh rằng có thể xếp 2n nguời đó trên 1 vòng tròn sao cho không ai ngồi cạnh kẻ thù của mình 

Lời giải:

Ta xây dựng đồ thị G như sau:

-Đỉnh: là các điểm trong mặt phẳng hay trong không gian tương ứng với các quan khách, dùng mã số của các quan khách để ghi trên các đỉnh tương ứng.

-Cạnh: hai đỉnh được nối với nhau bằng cạnh khi và chỉnh khi hai quan khác tương ứng thuộc hai đỉnh đó không là kẻ thù của nhau.

Khi đó ta được một đồ thị G mô tả toàn bộ quan hệ giữa các quan khách. Vì đồ thị G có đúng 2n đỉnh, và mỗi đỉnh có bậc không nhỏ hơn n nên theo định lý Dirac ta có G có chu trình Halminton. Dựa vào chu trình này ta có thể xếp tất cả các quan khách thỏa mãn yêu cầu đề bài

Bài toán về sự phân bố số chính phương và số nguyên tố

Bài toán: Xét tất cả các số nguyên tố $p_1 < p_2 <..p_n<..$ Đặt $a_n=p_1+p_2+..+p_n$. Chứng minh rằng với mọi n nguyên dương, nằm giữa $a_n$ và $a_{n+1}$ có ít nhất một số chính phương.

Giải:
Bổ đề: Với $n \ge 4$ thì $p_{n+1} > 2\sqrt{p_1+p_2+..+p_n}+1$
Chứng minh:
Với n=4, đúng.

Giả sử đúng với n=k tức là:
$p_{k+1} > 2\sqrt{p_1+p_2+..+p_k}+1$

Hay là $(p_{k+1}-1)^2 >4 (p_1+p_2+..+p_k)$

Ta cần chứng minh: $(p_{k+2}-1)^2 >4 (p_1+p_2+..+p_{k+1})$

Hay chỉ cần chứng minh: $(p_{k+2}-1)^2 \ge (p_{k+1}-1)^2 +4p_{k+1}$

Điều này tương đương $(p_{k+2}-p_{k+1})(p_{k+2}+p_{k+1}-2) \ge 4p_{k+1}$

Điều này là hiển do khoảng cách 2 số nguyên tố liên tiếp bé nhất là 2. Vậy ta có đpcm

Quay lại bài toán
Với n=1, thì giữa 2 và 5 tồn tại 4 là số chính phương.
Tương tự cho n=2,3,4

Giả sử đúng với n=k tức là giữa $a_k$ và $a_{k-1}$ tồn tại ít nhất một số chính phương, ta gọi $a^2$ là số chính phương lớn nhất trong các số chính phương đó.

$(a+1)^2 > a_{k}$

Áp dụng bổ đề thì $p_{k+1}>2a+1$ nên $a_{k+1} >(a+1)^2$.

Dùng đơn biến và số dư để giải bài toán tổ hợp

Bài toán: Bắt đầu với dãy: S=(a,b,c,d) của các số nguyên không âm. Đặt $S_1=T(S)=(|a-b|,|b-c|,|c-d|,|d-a|)$. Tương tự $S_2=T(S_1)$. Hỏi có tồn tại $S_i$ sao cho $S_i=(0;0;0;0)$

Giải

Chúng ta thử vài trường hợp:

(0, 3, 10, 13) → (3, 7, 3, 13) → (4, 4, 10, 10) → (0, 6, 0, 6) → (6, 6, 6, 6) → (0, 0, 0, 0)

 (8, 17, 3, 107) → (9, 14, 104, 99) → (5, 90, 5, 90) → (85, 85, 85, 85) → (0, 0, 0, 0),

(91, 108, 95, 294) → (17, 13, 99, 203) → (4, 86, 104, 186) → (82, 18, 82, 182) → (64, 64, 100, 100) → (0, 36, 0, 36) → (36, 36, 36, 36) → (0, 0, 0, 0).

1) Đặt max S là phần tử lớn nhất của S. Khi đó $max S_{i+1} \le max S_i$ và $max S_{i+4}< max S_i$ ( Vì khi  $max S_{i+1} = max S_i$ Khi  $(S_i=(0, S_{i+1},a,b)$ tới $S_{i+3}$ nó sẽ giảm)

2)  Sau nhiều nhất 4 bước, tất cả 4 số sẽ trở thành số chẵn. Thật vậy ta sẽ xét đồng dư 2. Do tính đối xứng nên ta chỉ xét trường hợp này ( các trường hợp khác tương tự) :
0001 → 0011 → 0101 → 1111 → 0000 và 1110 → 0011. Vì thế sau nhiều nhất 4 bước tất cả các số sẽ chia hết cho 2, sau nhiều nhất 8 bước chia hết $2^2$,..sau nhiều nhất 4k bước thì các số sẽ chia hết $2^k$ cho k thật lỡn ta sẽ có tất cả cá số đều bằng 0

Dùng bất biến, đơn biến để giải bài toán tổ hợp - Phần 1

1) Cho n là số tự nhiên lẻ. Đầu tiên bạn A viết các số 1,2,..2n lên bảng. Sau đó bạn ấy chọn hai số a, b bất kì, xoá nó và viết lại số |a-b|, Chứng minh rằng chữ số cuối cùng còn lại là một số lẻ.

Lời giải:

Đặt $S=1+2+..2n=n(2n+1)$ lẻ. Mỗi bước thực hiện ta có $S'=S+|a-b|-a-b=S-2min(a,b)$. Vì vậy tính chẵn lẻ của S là bất biến. Số cuối cùng phải đồng dư 1 mod 2.

2) Một vòng tròn được chia thành sáu phần. Sau đó, các con số 1, 0, 1, 0, 0, 0 được viết
vào các phần (ngược chiều kim đồng hồ). Bạn có thể làm tăng hai số kề nhau một số bằng 1.Có thể cân bằng các số sau hữu hạn bước hay không ?

Lời giải:

Giả sử $a_1, a_2,..a_6$ là các số trên các phần đó. Ta có: $I=a_1 −a_2 +a_3 −a_4 +a_5 −a_6$ là một đại lượng bất biến. Ban đầu $I=2$ nên không thể cho $I=0$ được

3) Trong Quốc hội Sikinia, mỗi thành viên có ít nhất ba kẻ thù. Chứng minh
rằng ngôi nhà có thể được chia thành hai ngôi nhà, để mỗi thành viên có ít nhất
một kẻ thù trong chính ngôi nhà của mình.

Lời giải:

Ban đầu cho bất kì các thành viên vào hai ngôi nhà.

Đặt H là tổng số của tất cả các kẻ thù của mỗi thành viên đều có trong chính ngôi nhà của mình.

Bây giờ giả sử A có ít nhất hai ( có thể 3)  kẻ thù trong nhà của mình. Khi đó, A sẽ có ít nhất 1 kẻ thù trong nhà khác. Nếu A chuyển nhà, số H sẽ giảm (Tăng 1 giảm 2). Điều này giảm không thể mãi mãi. Tại một số thời gian, H đạt tối thiểu tuyệt đối của nó.
Sau đó, chúng ta đã đạt đến phân phối yêu cầu.

4) Giả sử các số a,b,c,d không đồng thời bằng nhau.Bắt đầu với (a, b, c, d) và
nhiều lần thay thế (a, b, c, d) bằng cách (a - b, b - c, c - d, d - a). Sau đó ít nhất một trong 4
số sẽ lớn vô cùng

Lời giải:
Đặt $P_n=(a_n, b_n, c_n, d_n)$ là 4 số sau khi đổi n lần. Khi đó ta có: $a_n+b_n+c_n+d_n=0$ (với $n \ge 1$)
Chúng ta không nhìn thấy cách nào để sử dụng bất biến... Nhưng nếu nhìn theo hướng hình học thì thật hữu ích. Chức năng rất quan trọng cho các điểm $P_n$ trong không gian 4 chiều là khoảng cách tử điểm đó đến điểm gốc là $(0;0;0;0)$ là: $a_n^2+b_n^2+c_n^2+d_n^2$. Nếu ta chứng minh nó không có giới hạn trên ta có điều phải chứng minh.

Ta sẽ cố gắng tìm mối liên hệ giữa $P_n$ và $P_{n+1}$:

$\sum a_{n+1}^2=\sum (a_n-b_n)^2=2\sum a_n^2-2\sum a_nbn$

Mặt khác:

$0=(\sum a_n)^2=(a_n+c_n)^2+(b_n+c_n)^2+2\sum a_nb_n$

Cộng hai vế lại suy ra: $ \sum a_{n+1}^2\ge\sum a_n^2$

Như vậy ta kết luận rằng với $n \ge 2$

$\sum a_n^2\ge2^{n-1}\sum a_1^2$

Như vậy khoảng cách từ điểm $P_n$ đến điểm gốc tăng không có giới hạn trên. Tức là phải có một số đạt đến vô cùng.

5) Có 2n  đại sứ được mời đến một bữa tiệc. Mỗi đại sứ có nhiều nhất n-1
kẻ thù. Chứng minh rằng các đại sứ có thể được ngồi quanh một chiếc bàn tròn, để
không ai ngồi cạnh một kẻ thù.

Giải

Đầu tiên chúng ta xếp chỗ ngồi các đại sứ bất kì. Gọi H là số cặp đôi thù địch ở gần nhau. Chúng ta phải tìm ra một thuật toán làm giảm số này bất cứ khi nào H> 0. Đặt (A, B) là một cặp thù địch với B ngồi bên trái của A (Như trong hình Fig 1.3). Chúng ta phải tách chúng ra để gây ra ít xáo trộn càng tốt. Điều này sẽ đạt được nếu chúng ta đảo ngược cung BA' nhận được hình Fig 1.4, H sẽ được giảm nếu (A,A') và (B, B') trên hình Fig 1.4 là cặp đôi thân thiện. Mà với A ta lại có ít nhất n bạn. Mà họ không thể là kẻ thù của B được nên có bạn A' của A lại là bạn của B, bên phải B'- bạn của B.

Dùng tính liên tục của tổ hợp để giải bài toán.

Ví dụ: Cho bảng vuông nxn gồm$n^2$ ô vuông đơn vị. Điền vào các ô đơn vị các số nguyên sao cho hai ô cạnh nhau (có cạnh chung) được điền vào hai số chênh lệch nhau không quá 
$1$ đơn vị. Chứng minh rằng có một số xuất hiện ít nhất $n$ lần.

Ta sẽ giải bằng nguyên lí cực hạn kết hợp với tính liên tục của nó:

Trên mỗi hàng chọn ra số lớn nhất. Gọi số bé nhất trong các số đó là $a$

Trên mỗi hàng chọn ra số bé nhất. Gọi số lớn nhất trong các số đó là $b$

Trên mỗi cột chọn ra số lớn nhất. Gọi số bé nhất trong các số đó là $c$

Trên mỗi cột chọn ra số bé nhất. Gọi số lớn nhất trong các số đó là $d$

Trước hết ta chứng minh $c\ge b$

Thật vậy gọi $e$ là số nằm trên cột chứa $c$ và hàng chứa $b$

Khi đó theo cách gọi $c\ge e,e\ge b$ suy ra $c\ge b$

Tương tự $a\ge d$ 

TH1 : $a>b$

Gọi $x$ là một số bất kỳ nằm giữa $a$ và $b$

Khi đó dễ thấy hàng nào cũng phải chứa $x$ (Vì trên mỗi hàng $x$ đều không nhỏ hơn số bé nhất của hàng đó và không lớn hơn số lớn nhất của hàng đó) 

Khi đó $x$ lặp lại $n$ lần

TH2 :$a\le b$

-Nếu $c>d$ thì xét tương tự TH1

-Nếu $c\le d$ 

Theo trên ta có: $c\ge b\ge a\ge d$

Từ đây dễ suy ra $a=b=c=d$ suy ra cả $n^2$ số trên bảng đều bằng nhau

 Vậy tồn tại một số xuất hiện ít nhất $n$ lần 

Nhận xét : cách giải ở trường hợp ta $a>b$ đã dùng tính liên đó là từ a đến b chắc chắn phải đi qua x. Xét trên một hàng bất kì. Thì  số nhỏ nhất $\ge b \ge x  \ge a \ge$ số lớn nhất nên từ số nhỏ nhất đến số lớn nhất thì luôn tăng hoặc giảm 1 đơn vị nên chắc chắn phải đi qua x.

link nguồn: http://diendantoanhoc.net/topic/158120-ch%E1%BB%A9ng-minh-r%E1%BA%B1ng-c%C3%B3-m%E1%BB%99t-s%E1%BB%91-xu%E1%BA%A5t-hi%E1%BB%87n-%C3%ADt-nh%E1%BA%A5t-n-l%E1%BA%A7n/#entry632412