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

[thangde.]

Có n người http://dientuvietnam...x.cgi?N_1...N_n tô mầu bảng theo yêu cầu sau:
_trong vòng 1 phút mỗi người phải tô màu xong đúng 1 ô
_họ không được tô màu lại các ô đã tô màu
_với i=1,2,..n;người http://dientuvietnam...mimetex.cgi?N_i hai phút liên tiếp tô màu 2 ô thì hai ô ấy phải có cạnh chung
Giả sử ban đầu chưa có ô nào được tô màu và ở phút đầu tiên , n người được yêu cầu tô màu n ô mà không có 2 ô nào trong ô đó nằm trên cùng 1 hàng hay cùng 1 cột
Tìm số n để sau n phút họ có thể tô màu hết các ô của bảng

[tanlsth]

Nhưng nếu ban đầu có 2 người tô 2 ô (1,2) và (2,1) thì cái ô trong cùng ai sẽ tô đây
Vì 2 bước tô liên tiếp phải tô hai ô có cạnh chung mà

[thangde.]

bạn hiểu nhầm đề rồi n ô ban đầu được n người chọn tùy ý miễn là không có 2 ô nào cùng hàng hay cùng cột
Ta có thể dễ dàng chỉ ra thuật toán cho n chẵn,băng cách chọn n ô đầu thuộc đường chéo chính,sau đó chia các cặp 2 người...
Ta chứng minh n=4k+3 không thỏa mãn.Đánh số ô hàng i,cột j là ô (i;j)
Giả sử ban đầu người thứ i chọn n ô (a_i;b_i).
Do 2 ô liên tiếp có cạnh chung nên lần thứ 2 ô được tô sẽ có tổng 2 tọa độ đồng dư với http://dientuvietnam...?a_i b_i 1(mod2)...Vì vậy lí luận tương tự ta có n ô được người thứ i tô sẽ có tổng 2 tọa độ đồng dư với http://dientuvietnam... b_i (a_i b_i 1)+...+(a_i+b_i+n-1)(mod2)
Tổng 2 tọa độ của tất cả các ô trên bảng là http://dientuvietnam.net/cgi-bin/mimetex.cgi?a_1+...+a_n=b_1+...b_n=1+2+...n=\dfrac{n(n+1)}{2}
Từ ta có http://dientuvietnam...tex.cgi?n^2(n-1) chia hết cho 4->n=4k+3 không thỏa mãn
Còn phải chỉ ra thuật toán cho n=4k+1,làm thế nào nhỉ?

Bài viết đã được chỉnh sửa nội dung bởi thangde.: 11-10-2006 - 20:20

[longanimity]

(x,y) : x là cột, y là hàng

1. Với n = 2k: chia n người thành k cặp, mỗi cặp tô 2 cột liền nhau
- Cặp 1: tô cột 1 & 2, xuất phát (1,1) & (2,n)
- Cặp 2: tô cột 3 & 4, xuất phát (3,2) & (4,n-1)
- Cặp 3: tô cột 5 & 6, xuất phát (5,3) & (6,n-2)
....
- Cặp m: tô cột 2m-1 & 2m, xuất phát (2m-1,m) & (2m,n+1-m)
...

2. Với n = 2k+1, chứng minh được k là số chẳn (tương tự ý tưởng thangde đã nêu) Do đó n có dạng 4k+1.
Chia n thành 2k-1 cặp và một nhóm 3 người.
- Cặp m (tương tự ở trên): tô cột 2m-1 & 2m, xuất phát (2m-1,m) & (2m,n+1-m)
- Nhóm 3 người: tô 3 cột cuối cùng n-2 & n-1 & n. Để cho dễ trình bày, gọi là cột 1,2,3. Xuất phát tại A(1,2k+1) ; B(2,2k+2) ; C(3,2k). Cách tô của A,B,C được chỉ ra bên dưới.

Cách tô cột 1,2,3 của A,B,C:

A) tô lên phía trên theo cột 1 (2k+1 ô), sau đó tô zíc-zắc k hàng đầu tiên của cột 2 & 3 (2k ô) => tổng cộng 4k+1 ô

B) tô zíc-zắc bên dưới tất cả 2k hàng của cột 1,2 (tổng cộng 2 x 2k = 4k ô) và dừng tại ô (3,n) => tổng cộng 4k+1 ô

C) tô lên phía trên theo cột 3, chỉ tô k ô (để k ô còn lại cho A), sau đó sang cột 2 tô xuống dưới đến bên cạnh ô xuất phát của A thì dừng lại tại đó, nhảy trở lại cột 3 và tiếp tục tô xuống dưới => theo tính toán, C sẽ dừng lại trước khi tô ô (3,n)

Bài toán kết thúc

Bài viết đã được chỉnh sửa nội dung bởi longanimity: 13-10-2006 - 09:07

[tanlsth]

Bằng cách xét chu trình ta chứng minh được ban đầu nếu tô theo bàn cờ thì có ô đen và ô trắng
Sau đó xây dựng theo
Các ô trắng ta sắp xếp ra hàng chéo lệch đối xứng
Từ đó ta có cách đi cho các quân cờ

[DinhCuongTk14]

Cách của mình cũng tương tự như các bạn
n chẵn tô đối xứng qua tâm của các cặp người
nếu n lẻ
tô bảng như bàn cờ đen nhiều hơn trắng
mỗi bước đi chuyển màu
Sau đó giả sử n=2k+1
nếu cõ x ô đen y ô trắng ở vị trí đầu tiên
x ô trắng mỗi người tô ở x ô đố sẽ phải tô k+1 ô trắng và k ô đen
LÍ luận như trên => có k+1 ô đen và k ô trắng
SAu đó lí luận vị trí các ô sẽ đuợc kq như trên

[dhkhtn-tnt]

đây là cách tô cho http://dientuvietnam...imetex.cgi?4k 1 mình mới tìm ra!

Trước hết cho http://dientuvietnam...n/mimetex.cgi?n chẵn ta tô như sau:
Tô ô http://dientuvietnam...imetex.cgi?(1,1) và http://dientuvietnam...imetex.cgi?(2,n)
sau đó lấy 2 ô tiếp theo nhận được từ 2 ô này theo bước nhảy của 1 con mã,cụ thể là ô http://dientuvietnam...imetex.cgi?(3,2) và http://dientuvietnam...etex.cgi?(4,n-1)... cứ thế ta có thể đánh số thỏa mãn đề bài theo những HCN http://dientuvietnam...mimetex.cgi?2xn

CM n khác http://dientuvietnam...imetex.cgi?4k 3 như trên

Bây giờ ta chỉ ra cách tô cho http://dientuvietnam...etex.cgi?n=4k 1
Lấy http://dientuvietnam...imetex.cgi?4k-2 hàng trên cùng tô như t/h n chẵn,còn lại 3 hàg cuối cùng ta xét 3 cột chính giữa của HCN http://dientuvietnam.net/cgi-bin/mimetex.cgi?3xn còn lại và tô các ô:http://dientuvietnam.net/cgi-bin/mimetex.cgi?A(1,2);B(2.1);C(3,3).Sau đó đánh số từ http://dientuvietnam.net/cgi-bin/mimetex.cgi?C theo những ô vuông ở biên của HCN http://dientuvietnam.net/cgi-bin/mimetex.cgi?3xn đến ô kế cạnh với http://dientuvietnam.net/cgi-bin/mimetex.cgi?A.
Đánh số từ http://dientuvietnam.net/cgi-bin/mimetex.cgi?A cũng dọc theo đường cạnh HCN do http://dientuvietnam.net/cgi-bin/mimetex.cgi?n=4k+1 nên ta có thể lấp đầy các ô ở hàng 2.(cách này ko t/m cho http://dientuvietnam.net/cgi-bin/mimetex.cgi?n=4k+3)
Dễ thấy tất cả các ô được tô đều ko cùng hàng hay cùng cột
EDit:So bad!

[manutd]

- Nhóm 3 người: tô 3 cột cuối cùng n-2 & n-1 & n. Để cho dễ trình bày, gọi là cột 1,2,3. Xuất phát tại A(1,2k+1) ; B(2,2k+2) ; C(3,2k). Cách tô của A,B,C được chỉ ra bên dưới.

http://dientuvietnam...n/mimetex.cgi?k là thế nào đây?

[manutd]

Đọc thấy lời giải của 2 bạn đều có vấn đề thì tôi nêu cách của mình đã.
http://dientuvietnam.net/cgi-bin/mimetex.cgi?n=4k+1
Xét 3 người cuối cùng A,B,C.
A xuất phát từ http://dientuvietnam...x.cgi?(n-2,2k 1) đi lên trên cho đến ô trên cùng của cột http://dientuvietnam...mimetex.cgi?n-2, rồi ziczac theo http://dientuvietnam...n/mimetex.cgi?k hàng trên cùng của cột http://dientuvietnam...mimetex.cgi?n-1 và cột http://dientuvietnam.../mimetex.cgi?n.
C xuất phát từ http://dientuvietnam...metex.cgi?(n,2k) đi men theo đường biên để đến ô http://dientuvietnam...tex.cgi?(n-2,2k).
Phần còn lại là của B, dễ!

[longanimity]

- Nhóm 3 người: tô 3 cột cuối cùng n-2 & n-1 & n. Để cho dễ trình bày, gọi là cột 1,2,3. Xuất phát tại A(1,2k+1) ; B(2,2k+2) ; C(3,2k). Cách tô của A,B,C được chỉ ra bên dưới.

http://dientuvietnam.net/cgi-bin/mimetex.cgi?k là thế nào đây?

Bó tay luôn. Tui đã viết rõ:

Do đó n có dạng 4k+1.

Cách đi A,B,C của manutd có khác gì của tui đâu nhỉ ? Hoàn toàn tương tự nhau. Và ý tưởng quan trọng là gom 3 người cuối cùng vào chung 1 nhóm

Để chứng minh n ko thể là 4k+3, có một cách rất ngắn gọn. Nếu các em muốn khai thác thêm thì thử chứng minh lại cái này.

Bài viết đã được chỉnh sửa nội dung bởi longanimity: 19-10-2006 - 04:11

[dhkhtn-tnt]

Anh thử nói xem!Em cũng chỉ nghĩ ra cách lấy mod2 thối!

[longanimity]

Anh thử nói xem!Em cũng chỉ nghĩ ra cách lấy mod2 thối!

Yes em, tất nhiên phải xét tính chẳn lẻ. Chẳng qua mình nghiên cứu cách lập luận ngắn gọn và rõ ràng hơn thôi.
Em có thể xoáy vào các tính toán "trọng tâm" để thấy rõ n ko thể là n=4k+3. Hoặc bởi vì đây là 1 bài toán tô màu, em có thể sử dụng pp tô màu : tô đen các ô có có tổng hàng cột = số lẻ. Các ô này nằm xen kẽ nhau và số ô đen là chẳn nếu n=4k+3. Dựa theo 2 điều này để thấy điều vô lý khi n=4k+3.

Bài viết đã được chỉnh sửa nội dung bởi longanimity: 26-10-2006 - 08:54