Chủ đề này có 8 trả lời

[chachacha]

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 

[hxthanh]

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.

[chachacha]

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 ạ

[chachacha]

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)ⁿ+(m-1)(-1)ⁿ được không ạ

[hxthanh]

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

[hxthanh]

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ế?

[chanhquocnghiem]

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ế?

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)

[hxthanh]

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!

[chanhquocnghiem]

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 !