Bất biến và ứng dụng
#1
Đã gửi 23-06-2007 - 23:28
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.
- reddevil1998 yêu thích
#2
Đã gửi 24-06-2007 - 10:08
Bài viết đã được chỉnh sửa nội dung bởi QUANVU: 24-06-2007 - 10:09
#3
Đã gửi 24-06-2007 - 16:16
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ó :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?
$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}$
- ducthinh26032011 yêu thích
#4
Đã gửi 24-06-2007 - 18:30
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Ở 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 HUYVAN: 24-06-2007 - 18:30
#5
Đã gửi 24-06-2007 - 23:53
#6
Đã gửi 25-06-2007 - 10:13
Topic này làm gì có thày em trong đây hả bác QVThì đã 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
Cái trang của Andrei có phải là trang này không? http://www.combinatorics.org/
#7
Đã gửi 26-06-2007 - 01:41
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
#8
Đã gửi 01-07-2007 - 21:14
Đá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.
#9
Đã gửi 03-07-2007 - 23:10
Các bạn tiếp tục đóng góp các ví dụ hay cho chủ đề nhé.
#10
Đã gửi 04-07-2007 - 08:16
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh