Đến nội dung

Hình ảnh

Vẻ đẹp của Tổ Hợp

- - - - -

  • Please log in to reply
Chủ đề này có 1 trả lời

#1
caubeyeutoan2302

caubeyeutoan2302

    Nhà dược sĩ mê toán

  • Thành viên
  • 305 Bài viết
Mình vừa được tham khảo vài bài Tổ hợp rất hay của thầy Trần Nam Dũng , những bài này phát biểu khá cồng kềnh tuy nhiên cách giải lại rất ấn tượng và tự nhiên , mọi người cùng bàn luận nhé, dạo này mình thấy Phần toán rời rạc và Tổ hợp của diễn đàn khá ít nên lập ra topic này để các member VMF cùng học hỏi và thấy được vẻ đẹp của nó. Mở đầu là 3 bài sau đây .
Bài 1:
Trong 1 bảng hình vuông gồm 10 nhân 10 ô vuông ( 10 hàng, 10 cột), người ta viết vào các ô vuông các số tự nhiên từ 1 đến 100 theo cách như sau:ở hàng thứ nhất , từ trái sang phải , viết các số từ 1 đến 10; ở hàng thứ 2 theo thứ tự từ trái sang phải, viết các số từ 11 đến 20, cứ như vậy cho đến hết hàng số 10. Sau đó cắt bảng vuông thành những hình chữ nhật cỡ 1 nhân 2 hoặc 2 nhân 1. Tính tích số của 2 số trong mỗi hình chữ nhật và cộng 50 tích lại . Cần phải cắt bảng vuông thế nào để tổng tìm được là lớn nhất , nhỏ nhất .
Bài 2:
Cho n là số nguyên dương lớn hơn hay bằng 2. Kí hiệu A={1,2,3,......,n}. Tập con B của tập A được gọi là 1 tập tốt nếu B khác rỗng và trung bình cộng của các phần tử của B là 1 số nguyên . Gọi T(n) là số các tập tốt của tập A . Chứng minh rằng T(n)-n là một số chẵn.
Bài 3:
Một điểm trên mặt phẳng tọa độ Oxy được gọi là điểm nguyên nếu hoành độ và tung độ của điểm đó là những số nguyên . Hãy tìm ra 5 điểm nguyên là 5 đỉnh của 1 ngũ giác đều sao cho diện tích của ngũ giác này đạt diện tích nhỏ nhất.

Bài viết đã được chỉnh sửa nội dung bởi caubeyeutoan2302: 12-07-2011 - 20:46

CỐ GẮNG THÀNH SINH VIÊN ĐẠI HỌC Y DƯỢC THÀNH PHỐ HỒ CHÍ MINH

#2
BurakkuYokuro11

BurakkuYokuro11

    Thượng sĩ

  • Thành viên
  • 230 Bài viết

Bài 2:
Cho n là số nguyên dương lớn hơn hay bằng 2. Kí hiệu A={1,2,3,......,n}. Tập con B của tập A được gọi là 1 tập tốt nếu B khác rỗng và trung bình cộng của các phần tử của B là 1 số nguyên . Gọi T(n) là số các tập tốt của tập A . Chứng minh rằng T(n)-n là một số chẵn.

 

Bài toán quen thuộc sử dụng phương pháp song ánh

Ta bỏ đi $n$ tập con có $1$ phần tử của $T_n$

$T_n-n$ tập "tốt" còn lại chia vào $2$ loại: Tập đó chứa trung bình cộng các phần tử của nó hoặc Tập đó không chứa trung bình cộng các phần tử của nó

Giờ xét tập con của $S=\{a_1,a_2,...,a_k\}$ trong đó trung bình cộng của các phần tử của nó là $a_k$. Khi đó $S \setminus \{a_k\}$ cũng là một tập "tốt" và nó không chứa trung bình cộng các phần tử của nó. Dễ thấy phép biến đổi này là một đơn ánh

Tương tự nếu $S=\{a_1,...,a_k\}$ có trung bình cộng các phần tử của $S$ là $b$ và $b \neq a_i$. Dễ thấy $k<n$ vì $\dfrac{1+2+...+n}{n}$ nếu là số nguyên thì nó cũng nằm trong $X$. Do đó nếu xét $S'$ là hợp của $S$ với $b$ thì $S'$ là một tập con của $X$ và dễ thấy đây cũng là một đơn ánh

Vậy tồn tại một song ánh đi từ $2$ loại tập tốt này vào nhau. Do đó số lượng tập tốt ở mỗi loại này bằng nhau

Do đó $T_n -n  \vdots 2$


WangtaX

 





0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh