Đến nội dung

Hình ảnh

một bài tổ hợp hay

- - - - -

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

#1
hocgiot

hocgiot

    Binh nhì

  • Thành viên
  • 14 Bài viết
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

#2
vuhongthai

vuhongthai

    Lính mới

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

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
hocgiot

hocgiot

    Binh nhì

  • Thành viên
  • 14 Bài viết
Bạn có thể giải chi tiết dc không
Mình cảm ơn bạn nhiều

#4
THC

THC

    Binh nhất

  • Thành viên
  • 23 Bài viết
Mì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ô. 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
THC

THC

    Binh nhất

  • Thành viên
  • 23 Bài viết
Mình cũng có 1 bài tóan khác rất hay về tô màu đa giác đều. Mình dịch bài này từ tạp chí Kvant của Nga số 3 năm 2000. Nhưng bài này mang tính chất hình học nhiều hơn là tổ hợp. Thôi xin phép cứ post ở đây tặng các bạn. Chú ý là có thể giải bằng nhiều cách khác hẳn nhau:

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
H.Quân- ĐHV

H.Quân- ĐHV

    An-tôn Páp-lô-vích Sê-Khốp

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

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 ,...
I hope for the best

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
H.Quân- ĐHV

H.Quân- ĐHV

    An-tôn Páp-lô-vích Sê-Khốp

  • Thành viên
  • 530 Bài viết
kết Quả của mình

$s_{n+1} = s_{n} + s_{n-1}.$
I hope for the best

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
THC

THC

    Binh nhất

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

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
H.Quân- ĐHV

H.Quân- ĐHV

    An-tôn Páp-lô-vích Sê-Khốp

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

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 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 đề )
I hope for the best

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
H.Quân- ĐHV

H.Quân- ĐHV

    An-tôn Páp-lô-vích Sê-Khốp

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

Mì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ô

đ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 đều
I hope for the best

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
THC

THC

    Binh nhất

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

đoạn này tiếp tục sai .

Ko phải mình tiếp tục sai mà là bác sai vì bác đọc đề ko kỹ.

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

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.
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
THC

THC

    Binh nhất

  • Thành viên
  • 23 Bài viết
Nếu kiểm tra bằng cách tô màu thủ công cho các trường hợp n=2,3,4 rồi so với công thức ở trên thì thấy khớp nhau:
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
H.Quân- ĐHV

H.Quân- ĐHV

    An-tôn Páp-lô-vích Sê-Khốp

  • Thành viên
  • 530 Bài viết
ok ,you are right .

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
I hope for the best

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
hocgiot

hocgiot

    Binh nhì

  • Thành viên
  • 14 Bài viết
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

#15
H.Quân- ĐHV

H.Quân- ĐHV

    An-tôn Páp-lô-vích Sê-Khốp

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

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

bài này phải xét tơi $s_{n-2} $ :P
I hope for the best

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
hocgiot

hocgiot

    Binh nhì

  • Thành viên
  • 14 Bài viế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

#17
H.Quân- ĐHV

H.Quân- ĐHV

    An-tôn Páp-lô-vích Sê-Khốp

  • Thành viên
  • 530 Bài viế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

kết quả trên là của bài anh mới nhận xét đó .
I hope for the best

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
THC

THC

    Binh nhất

  • Thành viên
  • 23 Bài viết
Trường hợp bắt buộc phải sử dụng cả 4 màu có thể suy ra từ kết quả giải bài này của mình ở trên.

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





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

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