một bài tổ hợp hay
#1
Đã gửi 07-03-2008 - 00:44
bằng một trong 4 màu xanh đỏ tím vàng
Hỏi có bao nhiều cách tô màu sao cho không có hai tam giác nào kề nhau mà dc tô cùng màu
#2
Đã gửi 08-03-2008 - 12:27
Cho đa giác đều 2008 cạnh $A_1...A_{2008}$ và có tâm O ta tô màu các tam giác $A_i OA_{i+1}$
bằng một trong 4 màu xanh đỏ tím vàng
Hỏi có bao nhiều cách tô màu sao cho không có hai tam giác nào kề nhau mà dc tô cùng màu
bài này ko khó
ta cm cho trường hợp tổng quát
đặt S(n) la số cách tô màu cho đa giác n cạnh
tính được S(n) theo S(n-1) và S(n-2)
rồi dùng dãy để tính S(n)
.....
Tớ đang bận ! sẽ post lời giải chi tiết sau vậy
#3
Đã gửi 08-03-2008 - 16:39
Mình cảm ơn bạn nhiều
#4
Đã gửi 08-03-2008 - 19:33
Cách giải của mình như sau:
Tam giác (TG) thứ 1 có 4 cách tô màu. Ứng với mỗi màu của TG1 thì TG2 liền kề có thể tô bằng 1 trong 3 màu còn lại, như vậy có 4*3 cách tô TG1 và TG2. Tương tự, có thể tô TG3 bằng 1 trong 3 màu khác với TG2, vậy có 4*3*3 cách tô TG1,TG2 và TG3... Lý luận như thế đến TG thứ n ta có: 4*3**(n-1) cách tô. Nhưng phải trừ đi số x trường hợp mà TGn và TG1 trùng màu nhau. Hợp nhất TGn và TG1 có cùng màu với nhau thành TG mới, vẫn gọi là TG1, sẽ thấy con số cần trừ đi bằng x = S(n-1).
Như vậy :
S(n) = 4*3**(n-1) - S(n-1)
S(2) = 12
Bài viết đã được chỉnh sửa nội dung bởi THC: 09-03-2008 - 13:14
#5
Đã gửi 08-03-2008 - 21:47
Cho đa giác đều (2n+1) đỉnh, trong đó (n+1) đỉnh được tô màu đỏ. CMR luôn tìm được một tam giác cân có đỉnh là đỉnh của đa giác đã cho mà tất cả các đỉnh của tam giác cân đó đều có màu đỏ
#6
Đã gửi 08-03-2008 - 22:20
Cách giải của mình như sau:
Tam giác (TG) thứ 1 có 4 cách tô màu. Ứng với mỗi màu của TG1 thì TG2 liền kề có thể tô bằng 1 trong 3 màu còn lại, như vậy có 4*3 cách tô TG1 và TG2. Tương tự, có thể tô TG3 bằng 1 trong 3 màu khác với TG2, vậy có 4*3*3 cách tô TG1,TG2 và TG3... Lý luận như thế đến TG thứ n ta có: 4*3**(n-1) cách tô
đoạn này sai anh ạ
bởi vì bài toán bắt buộc phải có 4 màu cùng được tô .Do đó nếu như trên thì có TH chỉ có 3màu , 2màu
VD : TG1 tô X,TG2 tô D,TG3 tô X ,...
Chẳng có gì đáng giá bằng nụ cười và tình yêu thương của bạn bè
Trên bước đường thành công không có dấu chân của kẻ lười biếng
#7
Đã gửi 08-03-2008 - 22:22
$s_{n+1} = s_{n} + s_{n-1}.$
Chẳng có gì đáng giá bằng nụ cười và tình yêu thương của bạn bè
Trên bước đường thành công không có dấu chân của kẻ lười biếng
#8
Đã gửi 08-03-2008 - 22:45
bởi vì bài toán bắt buộc phải có 4 màu cùng được tô.
Nhưng trong đề bài có nói rõ là bắt buộc phải có 4 màu cùng được tô đâu ? Đầu bài chỉ nói phải dùng 1 trong 4 màu để tô mỗi TG thôi mà
Bài viết đã được chỉnh sửa nội dung bởi THC: 08-03-2008 - 22:47
#9
Đã gửi 08-03-2008 - 22:58
bởi 4 màu chứ nhỉ ! mình biết đề này là 'Báo BẢng ' trường chuyên ĐHV .(hay mình ghi sai đề )Cho đa giác đều 2008 cạnh $A_1...A_{2008}$ và có tâm O ta tô màu các tam giác $A_i OA_{i+1}$
bằng một trong 4 màu xanh đỏ tím vàng
Hỏi có bao nhiều cách tô màu sao cho không có hai tam giác nào kề nhau mà dc tô cùng màu
Chẳng có gì đáng giá bằng nụ cười và tình yêu thương của bạn bè
Trên bước đường thành công không có dấu chân của kẻ lười biếng
#10
Đã gửi 09-03-2008 - 11:00
đoạn này tiếp tục sai .VÌ có thể lặp X,D,X,D ,....,D với D,X,D,...X tức là quay một vòng đa giác đềuMình cũng có suy nghĩ giống như bạn vuhongthai, nhưng trong công thức tính S(n) của mình ko có S(n-2). Ko biết mình có nhầm ở đâu ko?
Cách giải của mình như sau:
Tam giác (TG) thứ 1 có 4 cách tô màu. Ứng với mỗi màu của TG1 thì TG2 liền kề có thể tô bằng 1 trong 3 màu còn lại, như vậy có 4*3 cách tô TG1 và TG2. Tương tự, có thể tô TG3 bằng 1 trong 3 màu khác với TG2, vậy có 4*3*3 cách tô TG1,TG2 và TG3... Lý luận như thế đến TG thứ n ta có: 4*3**(n-1) cách tô
Chẳng có gì đáng giá bằng nụ cười và tình yêu thương của bạn bè
Trên bước đường thành công không có dấu chân của kẻ lười biếng
#11
Đã gửi 09-03-2008 - 11:58
Ko phải mình tiếp tục sai mà là bác sai vì bác đọc đề ko kỹ.đoạn này tiếp tục sai .
Thì quay một vòng đa giác đều, đâu có sao. Nếu n chẵn thì cũng ko có 2 tam giác nào cùng màu cạnh nhau.VÌ có thể lặp X,D,X,D ,....,D với D,X,D,...X tức là quay một vòng đa giác đều
Còn với n lẻ thì lại phải đọc hết toàn bộ lời giải của mình ở trên, chứ ko phải chỉ có phần bạn trích dẫn.
Bài viết đã được chỉnh sửa nội dung bởi THC: 09-03-2008 - 12:09
#12
Đã gửi 09-03-2008 - 13:34
S(2)=12
S(3)=4*3**2-S(2)=24
S(4)=4*3**3-S(3)=84
Ví dụ với n=3 (liệt kê thủ công):
1/(X,Đ,V)
2/(X,Đ,T)
3/(X,V,Đ)
4/(X,V,T)
5/(X,T,Đ)
6/(X,T,V)
7/(Đ,X,V)
8/(Đ,X,T)
9/(Đ,V,X)
10/(Đ,V,T)
11/(Đ,T,V)
12/(Đ,T,X)
13/(T,X,Đ)
14/(T,X,V)
15/(T,Đ,X)
16/(T,Đ,V)
17/(T,V,X)
18/(T,V,Đ)
19/(V,X,Đ)
20/(V,X,T)
21/(V,Đ,X)
22/(V,Đ,T)
23/(V,T,X)
24/(V,T,Đ)
#13
Đã gửi 09-03-2008 - 14:51
mình đọc ko kĩ đề ,Vì nó cho các điểm cố định nên quay đi cũng chả đc gì .Câu hỏi đặt ra
nếu cho một đa giác đều nội tiếp 1 đường tròn tâm O , với cách tô bởi 4 màu như trên thi ko biết THC giải như thế nào
Chẳng có gì đáng giá bằng nụ cười và tình yêu thương của bạn bè
Trên bước đường thành công không có dấu chân của kẻ lười biếng
#14
Đã gửi 09-03-2008 - 16:00
#15
Đã gửi 09-03-2008 - 17:16
bài này phải xét tơi $s_{n-2} $với đề bài toán như trên thì bác thc giải đúng rùi còn với đề toán như pác yiruma thì bác định giải quyết tell hướng nào
Chẳng có gì đáng giá bằng nụ cười và tình yêu thương của bạn bè
Trên bước đường thành công không có dấu chân của kẻ lười biếng
#16
Đã gửi 09-03-2008 - 19:41
thử với giá trì S(4),S(5),S(6) thì thấy công thức đó không đúng
#17
Đã gửi 09-03-2008 - 20:38
kết quả trên là của bài anh mới nhận xét đó .tell em thì kết quả $S(n)=S(n-1)+S(n-2)$ là sai
thử với giá trì S(4),S(5),S(6) thì thấy công thức đó không đúng
Chẳng có gì đáng giá bằng nụ cười và tình yêu thương của bạn bè
Trên bước đường thành công không có dấu chân của kẻ lười biếng
#18
Đã gửi 10-03-2008 - 12:31
1) Cho trường hợp KHÔNG bắt buộc dùng cả 4 màu ta đã có:
$S(n) = 4*3 ^{(n-1)} - S(n-1) $
$S(2)=12 $
Nhưng vì: $ 4*3 ^{(n-1)} = 3 ^{n} + 3 ^{(n-1)} $
Nên nếu khai triển biểu thức của S(n) theo n, các số hạng sẽ triệt tiêu cho nhau và cuối cùng ta sẽ nhận được:
$S(n) = 3 ^{n} + 3 $ nếu n chẵn
$S(n) = 3 ^{n} - 3 $ nếu n lẻ
2) Bây giờ xét trường hợp bắt buộc phải sử dụng cả 4 màu khi tô màu.
Ta sẽ loại bỏ đi các từ công thức tính S(n) ở phần trước các trường hợp chỉ sử dụng 2 hay 3 màu khi tô màu.
Đầu tiên, cũng lý luận như trước thấy rằng nếu với mỗi bộ 3 màu cho trước, số cách tô P(n) sao cho không có 2 tam giác cùng màu kề nhau (KHÔNG bắt buộc phải đủ 3 màu) là:
$P(n) = 3*2 ^{(n-1)} - P(n-1) $
$P(2)=6 $
Hay là:
$P(n) = 2 ^{n} + 2 $ nếu n chẵn
$P(n) = 2 ^{n} - 2 $ nếu n lẻ
a) Trường hợp n lẻ:
Nếu n lẻ thì không thể tô chỉ bằng 2 màu được. Do đó chỉ cần cần loại bớt số lần tô chỉ dùng 3 màu
Ngoài ra với mỗi bộ 4 màu (X,Đ,T,V) cho trước, luôn lấy ra đươc 4 tập hợp con là các bộ 3 màu: (X,Đ,T), (X,Đ,V), (Đ,T,V) và (X,T,V) nên số cách tô chỉ dùng 3 màu đ/v 4 màu (X,Đ,T,V) là 4*P(n)
Và cuối cùng số cách tô R(n) bắt buộc phải có dùng cả 4 màu cho đa giác n đỉnh với n lẻ là:
$R(n) = S(n) - 4*P(n) = 3 ^{n} - 4*2 ^{n} + 5 $
b) Trường hợp n chẵn:
Trường hợp n chẵn sẽ phải trừ đi số cách tô chỉ dùng 3 màu và số cách chỉ dùng 2 màu.
Số cách tô chỉ dùng 2 màu trong số 4 màu là C(2/4)*2=4!/(2!*2!)*2=12. Phải *2 vì là, chẳng hạn, (X,Đ) và (Đ,X) là được coi là 2 cách tô màu khác nhau.
Ngoài ra trong công thức tính P(n) cũng phải loại ra C(2/3)*2=6 là số trường hợp tô 2 màu khi ta tính P(n) (bao gồm cả tô bằng 2 và 3 màu).
Tóm lại:
$R(n) = S(n) - 12 - 4*(P(n) - 6) = 3 ^{n} - 4*2 ^{n} + 7 $
Thử lại kết quả với n=4 theo công thức này: R(4)=24, khớp với trường hợp phải dùng đủ 4 màu để tô đa giác 4 đỉnh sẽ có tất cả 4!=24 cách tô sao cho không có 2 tam giác cùng màu nằm kề nhau.
Xong! Xin các bác cho ý kiến đóng góp! Thank you!
Bài viết đã được chỉnh sửa nội dung bởi THC: 10-03-2008 - 14:13
2 người đang xem chủ đề
0 thành viên, 2 khách, 0 thành viên ẩn danh