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

[namdung]

Bất biến là một công cụ quan trọng trong việc giải các bài toán Olympic, đặc biệt là các bài toán có nội dung tổ hợp.

Hiện nay tôi đang viết một bài giảng về bất biến. Vì vậy đang cần đến một số ví dụ hay (cũng như các vấn đề lý thuyết hay) về ứng dụng của bất biến.

Bài toán cơ bản sử dụng bất biến được phát biểu dưới dạng như sau:

Bài toán 1. Có một tập hợp các trạng thái S và tập hợp các phép biến đổi T từ S vào S. Có hai trạng thái s và t thuộc S. Hỏi có thể dùng hữu hạn các phép biến đổi thuộc T để đưa trạng thái s về trạng thái t được không?

Định nghĩa. Cho S là một tập hợp các trạng thái. T là tập hợp các phép biến đổi từ S vào S. Hàm số f: S --> R được gọi là bất biến trên tập các trạng thái  đối với tập các phép biến đổi T nếu
f(t(s)) = f(s) với mọi s thuộc S và t thuộc T.

Như vậy, bất biến f có thể giúp chúng ta giải quyết trọn vẹn câu hỏi ìBằng các phép biến đổi T, có thể đưa từ trạng thái s về trạng thái t?” trong trường hợp mà f(s) khác f(t). Cụ thể câu trả lời sẽ là ìkhông”. Tuy nhiên, nếu f(s) = f(t) thì ta lại chưa có thể kết luận gì. Chính vấn đề này dẫn đến một khái niệm mới: bất biến toàn năng.

Định nghĩa. Bất biến f đối với cặp (S, T) được gọi là bất biến toàn năng nếu:
Trạng thái s có thể đưa về từ trạng thái t bằng các phép biến đổi T khi và chỉ khi f(s) = f(t).

Bất biến toàn năng sẽ giúp chúng ta giải quyết trọn vẹn bài toán ìchuyển được”. Tuy nhiên, việc xây dựng một bất biến như vậy không đơn giản. Trong nhiều trường hợp, sẽ dễ dàng hơn khi chúng ta xét đến một hệ bất biến toàn năng.

Định nghĩa. Hệ các bất biến $(f_1, f_2, …, f_k)$ đối với cặp (S, T) được gọi là hệ bất biến toàn năng nếu: Trạng thái s có thể đưa về từ trạng thái t bằng các phép biến đổi T khi và chỉ khi $f_i(s) = f_i(t)$ với mọi i = 1, 2, …, k.

Sau đây là một số ví dụ về ứng dụng của bất biến:
1. Trên bảng có các số 1/96, 2/96, 3/96, …, 96/96. Mỗi một lần thực hiện, cho phép xoá đi hai số a, b bất kỳ trên bảng và thay bằng a + b – 2ab. Hỏi sau 95 lần thực hiện phép xoá, số còn lại trên bảng là số nào?

2. Vòng tròn được chia thành n hình cánh quạt bằng nhau. Tại mỗi một cánh quạt có sẵn một viên bi. Mỗi một lần thực hiện, cho phép di chuyển hai viên bi bất kỳ sang ô bên cạnh, một viên theo chiều kim đồng hồ, một viên ngược chiều kim đồng hồ. Hỏi với những giá trị nào của n, ta có thể dồn tất cả các viên bi vào một cánh quạt sau một số hữu hạn các bước chuyển?

3. Có 3 đống sỏi có 10, 9 viên và 7 viên. Hai người chơi trò bốc sỏi: Mỗi một lần bốc có thể bốc đi một số viên bất kỳ (ít nhất 1 viên) từ một đống sỏi bất kỳ. Ai không còn sỏi để bốc sẽ thua cuộc. Hỏi ai là người thắng cuộc nếu chơi đúng.

4. Alibaba cùng chia với 1 tên cướp 10 đống cát vàng. Alibaba có thể tại 1 thời điểm bất kỳ lấy 3 đống vàng và đi, hoặc anh ta có thể chọn 4 đống vàng bất kỳ và chia mỗi đống thành 2 phần: phần phải và phần trái. Sau đó tên cướp sẽ hoán đổi các phần phải (không được để yên) và sau đó các phần lại nhập lại làm một.

Hỏi Alibaba có thể lấy đi 49 kg vàng không, nếu ban đầu có 50kg vàng?

5. Người ta có thể cắt một hình 17 giác lồi thành 14 tam giác không?

Rất mong sự góp ý và giúp đỡ của các bạn.

[QUANVU]

Ở Vn mình cũng có Nguyễn Hữu Điển viết(nhưng tham khảo khá nhiều sách ) về cái này, sách nuớc ngoài thì nhiều nhưng cuốn mà ai cũng tìm được là cuốn của Engel (tên chắc đúng ) . Các bạn h/s phổ thông có thể tham khảo hai cuốn đó để tham gia topic này của Namdung.

Bài viết đã được chỉnh sửa nội dung bởi QUANVU: 24-06-2007 - 10:09

[tanpham90]

Em xin phép làm bài 1 ạ !

1. Trên bảng có các số 1/96, 2/96, 3/96, …, 96/96. Mỗi một lần thực hiện, cho phép xoá đi hai số a, b bất kỳ trên bảng và thay bằng a + b – 2ab. Hỏi sau 95 lần thực hiện phép xoá, số còn lại trên bảng là số nào?

Số ở giữa của dãy là $\dfrac{1}{2}$ Do vậy nếu ta xóa số a,b bất kỳ thì ra một số mới nào đó ( đặt số mới là t chẳng hạn ) , đến một lúc nào đó sẽ phải xóa tới số $\dfrac{1}{2}$ mà khi đó ta có :
$t+\dfrac{1}{2}-2\dfrac{1}{2}t=\dfrac{1}{2}$
Do vậy số cuối cùng còn lại bất kể mọi cách xóa là $\dfrac{1}{2}$

[HUYVAN]

Ở Vn mình cũng có Nguyễn Hữu Điển viết(nhưng tham khảo khá nhiều sách ) về cái này, sách nuớc ngoài thì nhiều nhưng cuốn mà ai cũng tìm được là cuốn của Engel (tên chắc đúng ) . Các bạn h/s phổ thông có thể tham khảo hai cuốn đó để tham gia topic này của Namdung.

Hình như cái chương đầu tiên ( bất biến) của Engel đã nằm phân nửa trong sách của thầy Hữu Điển rồi -> khỏi đọc phần Bất biến của Engel

Bài viết đã được chỉnh sửa nội dung bởi HUYVAN: 24-06-2007 - 18:30

[QUANVU]

Thì đã nói là thày em là tham khảo hơi bị nhiều mà lại Nếu muốn tìm các bài khác thì có thể vào trang của Andrei mà download, ở đó còn có vài bài giảng khác nữa

[HUYVAN]

Thì đã nói là thày em là tham khảo hơi bị nhiều mà lại Nếu muốn tìm các bài khác thì có thể vào trang của Andrei mà download, ở đó còn có vài bài giảng khác nữa

Topic này làm gì có thày em trong đây hả bác QV
Cái trang của Andrei có phải là trang này không? http://www.combinatorics.org/

[namdung]

Ngoài bất biến (invariant) còn có khái niệm đơn biến (monovariant) cũng có nhiều ứng dụng hiệu quả trong các bài toán tổ hợp. Chẳng hạn để chứng minh một quá trình là dừng (hoặc ổn định), ta thường dùng đến đơn biến. Do đó đơn biến cũng thường được sử dụng trong các thuật toán. Mấy vòng lệnh do while mà không có anh này là căng ngay. Phương pháp xuống thang (infinite descent) cũng dùng ý tưởng đơn biến.

Mọi người tìm được tài liệu nào hay, gửi lên đây cho tất cả cùng tham khảo luôn nhé.

Namdung

[hocsinhdown]

Mình xin giải bài 2 của thày Nam Dũng.

Đánh số n cánh quạt từ 1,2,3... n. Đặt giá trị của "cây quạt" bằng cách lấy số bi trong mỗi ô nhân với số của ô đó. Khi đó, sau mỗi fép di chuyển bi, giá trị của cây quạt ko đổi, và bằng n(n+1)/2. Như vậy, khi tất cả bi tập trung vào 1 cánh thì giá trị của cây quạt là t*n. Nên có thể đưa hết bi vào 1 cánh khi n(n+1)/2 = t*n hay (n+1)/2 = t, tức n+1 là số lẻ.
Khi n lẻ, dễ thấy có cách đưa bi vào 1 cánh quạt.

[namdung]

Các bạn tanpham va hocsinh đã giải đúng rồi.

Các bạn tiếp tục đóng góp các ví dụ hay cho chủ đề nhé.

[1001001]

bữa đó lên trang toán của Berkeley thấy có cái này về bất biến cũng hay http://mathsite.math...ityTheorem.html .