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

[QUANVU]

Cho $p$ là một số nguyên tố lẻ. Xét $p-$ giác đều có cạnh đơn vị. Từ các cạnh của đa giác này, dựng ở miền ngoài đa giác các hình chữ nhật kích thước $1\times k$ ($k$ là số nguyên dương), mỗi hình chữ nhật được chia thành $k$ ô đơn vị. Gọi $P$ là hình sao được tạo thành, gồm $kp$ ô đơn vị và $p-$ giác đều (như vậy có $kp+1$ miền). Mỗi miền được tô bởi một trong ba màu, các miền kề nhau có màu khác nhau. Hơn nữa đòi hỏi phép tô màu đó không có trục đối xứng. Hỏi có bao nhiêu cách tô màu như vậy?

Bài viết đã được chỉnh sửa nội dung bởi PSW: 27-10-2012 - 20:29

[PSW]

Bài toán này thuộc Gameshow NHỮNG BÀI TOÁN TRONG TUẦN. Bài toán đã được công bố lại cách đấy 1 tuần nhưng chưa ai giải được. BTC đã đặt hoa hồng hi vọng cho bài toán này.

Hoa hồng hi vọng sẽ mang lại 50 điểm cho người đầu tiên giải đúng được bài toán này. Nếu hết ngày 31/10 mà vẫn không có ai giải được, BTC sẽ công bố bài toán khác, tuy nhiên hoa hồng hi vọng sẽ vẫn tồn tại cho đến khi có người giải được bài toán này.

[gogo123]

Đưa việc tô màu các miền phẳng về việc tô mầu cho các điểm, coi điểm O trong hình vẽ là đa giác đều đang xét đến, các đường thẳng xuất phát từ O chứa các điểm tượng trưng cho các hình vuông đơn vị.
 DĐTH.jpg.bmp   2.41MB   125 Số lần tải
Ta sẽ tính số cách tô màu hệ điểm bằng các số 1,2,3 sao cho:
- Hai điểm kề nhau khác số. (1)
- Cách tô màu không có trục đối xứng. (2)
Trước hết ta tính số cách tô màu có ít nhất một trục đối xứng và thõa mãn (1):
Ta có với cách tô có trục đối xứng thì trục đó cũng là trục đối xứng của đa giác (hiển nhiên). Mặt khác với đa giác đều có cạnh là số nguyên tố lẻ thì trục đối xứng chính là mỗi cạnh của nó. Như vậy trục đối xứng chính là các đường thẳng trong hình vẽ. Và có $p$ trục như vậy (tương ứng $p$ cạnh).
Ta xét 1 TH với $l$ là trục đối xứng (hình vẽ), điểm A có 3 cách tô, nên B có 2 cách tô (với mỗi A), C có 2 cách tô (với mỗi B),...,O có 2 cách tô.( chú ý trên cạnh có $k$ điểm không kể $O$)
Với mỗi cách tô $O$ ta sẽ tô đối xứng các điểm còn lại, hay chỉ cần tô các điểm thuôc nửa mặt phẳng bờ $l$.Có $\frac{p-1}{2}$ cạnh như vậy, mỗi cạnh có $k$ điểm, mỗi điểm có 2 cách tô.
Như vậy chung quy lại có tất cả $p.3.2^{k}.2^{k.\frac{p-1}{2}}=p.3.2^{k.\frac{p+1}{2}}$ cách tô có ít nhất một trục đối xứng .Mặt khác mỗi cách tô được nhắc lại một lần ở mỗi trục đối xứng nên thực chất chỉ có $3.2^{k.\frac{p+1}{2}}$ cách tô như vậy.
Bây giờ ta tính số cách tô màu thõa mãn ĐK (1):
Ta có O có 3 cách tô, $p$ cạnh còn lại, mỗi cạnh có $k$ điểm, mỗi điểm có 2 cách tô nên có tất cả $3.2^{kp}$ cách tô thõa mãn (1).
Vậy số cách tô thõa mãn cả (1) và (2) là $3.2^{kp}-3.2^{k.\frac{p+1}{2}}$.
 DĐTH.jpg.bmp   2.41MB   407 Số lần tải

Bài viết đã được chỉnh sửa nội dung bởi PSW: 02-12-2012 - 15:59

[PSW]

Chấm điểm
gogo123: 50 điểm