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.