Cho thất giác đều, người ta dùng 4 màu tô tất cả các đỉnh sao cho mỗi đỉnh một màu không có 2 đỉnh nào kề nhau tô cùng 1 màu ( một cách tô màu không nhất thiết đủ cả 4 màu). 2 cách tô màu được coi là giống nhau nếu cách này nhận cách kia nhờ phép quay. Có bao nhiêu cách tô màu khác nhau
Cho thất giác đều, người ta dùng 4 màu tô tất cả các đỉnh
#2
Đã gửi 07-08-2016 - 02:48
Cho thất giác đều, người ta dùng 4 màu tô tất cả các đỉnh sao cho mỗi đỉnh một màu không có 2 đỉnh nào kề nhau tô cùng 1 màu ( một cách tô màu không nhất thiết đủ cả 4 màu). 2 cách tô màu được coi là giống nhau nếu cách này nhận cách kia nhờ phép quay. Có bao nhiêu cách tô màu khác nhau
Từ các chữ số $\{1,2,3,4\}$ lập số có 7 chữ số sao cho các chữ số cạnh nhau thì khác nhau và chữ số cuối cùng khác chữ số đầu tiên. Lấy số cách lập được như vậy chia cho $7$ ta có kết quả của bài toán.
Dùng phương pháp đếm bao gồm-loại trừ ta đếm được
$S=4\times 3^6-4\times 3^5+4\times 3^4-4\times 3^3+4\times 3^2-4\times 3=2184$ số
Cụ thể như sau:
Gọi số cần lập là $a_1a_2a_3a_4a_5a_6a_7$
Chọn $a_1$ có $4$ cách
Chọn $a_2\neq a_1$ có $3$ cách
Chọn $a_3\neq a_2$ có $3$ cách
...
Chọn $a_7\neq a_6$ có $3$ cách
Tạo ra $S=4\times 3^6$ số
Nhưng ta đã tính thừa những trường hợp $a_7=a_1$
Chọn $a_1=a_7$ có $4$ cách
Chọn $a_2\neq a_1$ có $3$ cách
...
Chọn $a_6\neq a_5$ có $3$ cách
Loại đi $S=4\times 3^6-4\times 3^5$
Nhưng như vậy ta đã loại đi hai lần những trường hợp $a_6=a_7$
...
Tóm lại: Kết quả của bài toán là $\frac{2184}{7}=312$ cách tô màu.
- L Lawliet, Element hero Neos, Zx NTL xZ và 1 người khác yêu thích
#3
Đã gửi 07-08-2016 - 03:20
Từ các chữ số $\{1,2,3,4\}$ lập số có 7 chữ số sao cho các chữ số cạnh nhau thì khác nhau và chữ số cuối cùng khác chữ số đầu tiên. Lấy số cách lập được như vậy chia cho $7$ ta có kết quả của bài toán.
Dùng phương pháp đếm bao gồm-loại trừ ta đếm được
$S=4\times 3^6-4\times 3^5+4\times 3^4-4\times 3^3+4\times 3^2-4\times 3=2184$ số
Cụ thể như sau:
Gọi số cần lập là $a_1a_2a_3a_4a_5a_6a_7$
Chọn $a_1$ có $4$ cách
Chọn $a_2\neq a_1$ có $3$ cách
Chọn $a_3\neq a_2$ có $3$ cách
...
Chọn $a_7\neq a_6$ có $3$ cách
Tạo ra $S=4\times 3^6$ số
Nhưng ta đã tính thừa những trường hợp $a_7=a_1$
Chọn $a_1=a_7$ có $4$ cách
Chọn $a_2\neq a_1$ có $3$ cách
...
Chọn $a_6\neq a_5$ có $3$ cách
Loại đi $S=4\times 3^6-4\times 3^5$
Nhưng như vậy ta đã loại đi hai lần những trường hợp $a_6=a_7$
...
Tóm lại: Kết quả của bài toán là $\frac{2184}{7}=312$ cách tô màu.
em thì không giỏi dạng này, nhưng sao thầy lại đưa đáp án cho bọn em là 384 ạ
#4
Đã gửi 07-08-2016 - 03:22
và anh có thể chứng minh hộ em công thức với m màu, n đỉnh thì số cách tô là (m-1)n+(m-1)(-1)n được không ạ
#5
Đã gửi 07-08-2016 - 04:18
Bằng lập luận tương tự ta lập được tổng:
$\sum_{k=1}^{n-1} m(m-1)^{n-k}(-1)^{k-1}=\sum_{k=1}^{n-1}\big[(m-1)-(-1)\big](m-1)^{n-k}(-1)^{k-1}$
$=\sum_{k=1}^{n-1}\Big[(-1)^{k-1}(m-1)^{n+1-k}-(-1)^{k}(m-1)^{n-k}\Big]$
$=(m-1)^{n}-(-1)^{n-1}(m-1)=(m-1)^n+(m-1)(-1)^n$
Tuy nhiên kết quả vẫn phải chia cho $n$ do đồng dạng phép quay
#6
Đã gửi 07-08-2016 - 14:31
Ví dụ thực tế cho bài toán này, tôi lại thấy có vấn đề?
Kết quả: $\frac{(m-1)^n+(m-1)(-1)^n}{?}$
phát sinh ở chỗ: Vì các kết quả giống nhau qua phép quay nên cần phải chia cho bao nhiêu? (chia cho m hay n?)
VD1: $m=4, n=3$ (Tối đa 4 màu tô cho 3 đỉnh)
Kết quả:
123 213 312 412
124 214 314 413
132 231 321 421
134 234 324 413
142 241 341 431
143 243 342 432
Những số bị gạch là những trường hợp trùng nhau bởi phép quay, chẳng hạn $213\equiv 132$
Như vậy có thể thấy kết quả là $8$
Còn $(m-1)^n+(m-1)(-1)^n=3^3+3(-1)^3=24$
Vậy là phải chia cho $3\quad(=n)$
VD2: $m=3, n=4$ (Tối đa 3 màu tô cho 4 đỉnh)
Kết quả:
1212 2121 3121
1213 2123 3131
1232 2131 3132
1312 2313 3212
1313 2321 3231
1323 2323 3232
Kết quả có 6 cách
$(m-1)^n+(m-1)(-1)^n=2^4+2(-1)^4=18$
Vậy là phải chia cho $3\quad(=m)$
????????????????????????????????????
Các bạn giúp tôi giải thích xem vì sao lại thế?
- NTL2k1 yêu thích
#7
Đã gửi 08-08-2016 - 21:01
Ví dụ thực tế cho bài toán này, tôi lại thấy có vấn đề?
Kết quả: $\frac{(m-1)^n+(m-1)(-1)^n}{?}$
phát sinh ở chỗ: Vì các kết quả giống nhau qua phép quay nên cần phải chia cho bao nhiêu? (chia cho m hay n?)
VD1: $m=4, n=3$ (Tối đa 4 màu tô cho 3 đỉnh)
Kết quả:
123
213312412124
214314413132
231321421134 234
324413142
241341431143 243
342432Những số bị gạch là những trường hợp trùng nhau bởi phép quay, chẳng hạn $213\equiv 132$
Như vậy có thể thấy kết quả là $8$
Còn $(m-1)^n+(m-1)(-1)^n=3^3+3(-1)^3=24$
Vậy là phải chia cho $3\quad(=n)$
VD2: $m=3, n=4$ (Tối đa 3 màu tô cho 4 đỉnh)
Kết quả:
1212
212131211213
212331311232
21313132
1312231332121313
232132311323 2323
3232Kết quả có 6 cách
$(m-1)^n+(m-1)(-1)^n=2^4+2(-1)^4=18$
Vậy là phải chia cho $3\quad(=m)$
????????????????????????????????????
Các bạn giúp tôi giải thích xem vì sao lại thế?
Dưới đây là kết quả mình tìm được trong trường hợp tổng quát ($m$ màu, $n$ đỉnh).
Gọi $D_n$ là tập hợp các ước khác $1$ và $n$ của $n$ : $D_n=\left \{ d_1,d_2,...,d_t \right \}$
Số cách tô màu $P$ thỏa mãn điều kiện đề bài là :
$P=\frac{(m-1)^n+(-1)^n(m-1)-\sum_{k=1}^{t}\left ( C_m^{d_k}d_k! \right )}{n}+\sum_{k=1}^{t}\left ( C_m^{d_k}\left ( d_k-1 \right )! \right )$
Ví dụ :
+ $m=3;n=4\Rightarrow P=\frac{2^4+2-C_3^2.2!}{4}+C_3^2.1!=6$
+ $m=3;n=6\Rightarrow P=\frac{2^6+2-C_3^2.2!-C_3^3.3!}{6}+C_3^2.1!+C_3^3.2!=14$
+ $m=5;n=8\Rightarrow P=\frac{4^8+4-C_5^2.2!-C_5^4.4!}{8}+C_5^2.1!+C_5^4.3!=8215$
Đặc biệt, nếu $n$ là số nguyên tố thì $P=\frac{(m-1)^n+(-1)^n(m-1)}{n}$ (như thầy Thanh đã tìm được)
...
Ðêm nay tiễn đưa
Giây phút cuối vẫn còn tay ấm tay
Mai sẽ thấm cơn lạnh khi gió lay
Và những lúc mưa gọi thương nhớ đầy ...
#8
Đã gửi 09-08-2016 - 08:47
Dưới đây là kết quả mình tìm được trong trường hợp tổng quát ($m$ màu, $n$ đỉnh).
Gọi $D_n$ là tập hợp các ước khác $1$ và $n$ của $n$ : $D_n=\left \{ d_1,d_2,...,d_t \right \}$
Số cách tô màu $P$ thỏa mãn điều kiện đề bài là :
$P=\frac{(m-1)^n+(-1)^n(m-1)-\sum_{k=1}^{t}\left ( C_m^{d_k}d_k! \right )}{n}+\sum_{k=1}^{t}\left ( C_m^{d_k}\left ( d_k-1 \right )! \right )$
Ví dụ :
+ $m=3;n=4\Rightarrow P=\frac{2^4+2-C_3^2.2!}{4}+C_3^2.1!=6$
+ $m=3;n=6\Rightarrow P=\frac{2^6+2-C_3^2.2!-C_3^3.3!}{6}+C_3^2.1!+C_3^3.2!=14$
+ $m=5;n=8\Rightarrow P=\frac{4^8+4-C_5^2.2!-C_5^4.4!}{8}+C_5^2.1!+C_5^4.3!=8215$
Đặc biệt, nếu $n$ là số nguyên tố thì $P=\frac{(m-1)^n+(-1)^n(m-1)}{n}$ (như thầy Thanh đã tìm được)
Kết quả tìm được nhìn có vẻ chóng mặt nhỉ bạn chanhquocnghiem
Ước thực sự của $n$ (ước khác $1$ và $n$) đóng vai trò như thế nào vậy?
Có vẻ như $n$ được chia thành một số phần bằng nhau, mỗi phần ít nhất $2$ thành viên?
Tại sao lại có thêm thành phần này $\sum_{k=1}^{t}\left ( C_m^{d_k}\left ( d_k-1 \right )! \right)\quad $?
Mong bạn chanhquocnghiem chỉ bảo thêm. Cảm ơn!
#9
Đã gửi 09-08-2016 - 11:23
Kết quả tìm được nhìn có vẻ chóng mặt nhỉ bạn chanhquocnghiem
Ước thực sự của $n$ (ước khác $1$ và $n$) đóng vai trò như thế nào vậy?
Có vẻ như $n$ được chia thành một số phần bằng nhau, mỗi phần ít nhất $2$ thành viên?
Tại sao lại có thêm thành phần này $\sum_{k=1}^{t}\left ( C_m^{d_k}\left ( d_k-1 \right )! \right)\quad $?
Mong bạn chanhquocnghiem chỉ bảo thêm. Cảm ơn!
Đặt $T=\frac{(m-1)^n+(-1)^n(m-1)}{n}$
$T$ chính là tổng số cách tô, kể cả những cách bị trùng bởi phép quay.
Nhận xét rằng có những cách chỉ dùng đúng $d_k$ màu (gồm $\frac{n}{d_k}$ chu kỳ, trong mỗi chu kỳ các màu xuất hiện đúng $1$ lần).Những cách như vậy tạm gọi là những cách "tuần hoàn với chu kỳ $d_k$".
+ Số cách tuần hoàn với chu kỳ $d_k$ trong $T$ là $M=C_m^{d_k}.d_k!$
+ Số cách "không tuần hoàn" trong $T$ là $T-\sum_{k=1}^{t}\left ( C_m^{d_k}.d_k! \right )$
+ Số cách "không tuần hoàn" trong $P$ là $N=\frac{T-\sum_{k=1}^{t}\left ( C_m^{d_k}.d_k! \right )}{n}$
+ Vì mỗi cách tuần hoàn với chu kỳ $d_k$ trong $P$ "tạo ra" $d_k$ cách (trùng nhau) trong $T$
nên số cách tuần hoàn với chu kỳ $d_k$ trong $P$ là $\frac{M}{d_k}=C_m^{d_k}.(d_k-1)!$
$\Rightarrow$ số cách tuần hoàn trong $P$ là $Q=\sum_{k=1}^{t}\left ( C_m^{d_k}.(d_k-1)! \right )$
$\Rightarrow$ số cách tô thỏa mãn điều kiện đề bài là :
$P=N+Q=\frac{T-\sum_{k=1}^{t}\left ( C_m^{d_k}.d_k! \right )}{n}+\sum_{k=1}^{t}\left ( C_m^{d_k}.(d_k-1)! \right )$
---------------------------------------------------------------------------
@ hxthanh :
Không dám nhận mấy từ "chỉ bảo" ! Thực ra phải cảm ơn thầy Thanh.Trên diễn đàn này, mình đã học hỏi được từ thầy rất nhiều.Chúc thầy nhiều sức khỏe !
- E. Galois, hxthanh, Thuat ngu và 1 người khác yêu thích
...
Ðêm nay tiễn đưa
Giây phút cuối vẫn còn tay ấm tay
Mai sẽ thấm cơn lạnh khi gió lay
Và những lúc mưa gọi thương nhớ đầy ...
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh