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

[tanlsth]

Cho vòng tròn được đánh dấu điểm.Tìm số cách điền các kí tự vào các điểm trên sao cho giữa 2 kí tự bất kì giống nhau thì có một số chẵn các kí tự khác nó nằm giữa điểm đó

[tanlsth]

Mình làm ra trong phòng còn kết quả thì là

[tmbtw]

Giữa 2 kí tự bất kì luôn luôn có 1 số chẵn các kí tự khác nếu tính theo 1 chiều nào đó

[tmbtw]

Cậu xem lại đề bài 1 chút chứ nhỉ ?

[manutd]

bạn nào có lời giải thì post lên đi, bài này cũng bị bỏ quên khá lâu rồi.
@mod: dạo này xóa bài ác chiến thật, sợ quá, sợ quá

[tanlsth]

Chỉ cần tính theo một chiều thỏa mãn là được rồi

[duongqua]

bài này có phải làm theo hướng quy nạp không
nói chung mình thấy nó khá khó

[vnm]

bài này có thể chứng minh theo hướng sau
Nếu chỉ có 1 kí tự thì có 3 cách điền;không tồn tại cách điền với 2 kí tự.Xét 1 cách điền dùng cả 3 kí tự.Gọi A(v);B(v);C(v) là số điểm nằm giữa v và điểm A;B;C tương ứng gần nó nhất
ta chứng minh với 1 cách điền thỏa mãn đề bài thì A(v);B(v);C(v) không thể cùng chẵn
sau đó đặt f(v)=X nếu $B(v)\equiv C(v)(mod 2)$
Y nếu $A(v)\equiv C(v)(mod 2)$
Z nếu $A(v)\equiv B(v)(mod 2)$
Ta thay cách điền 2001 kí tự A;B;C bằng 1 cách điền 2001 kí tự X;Y;Z thỏa mãn điều kiên trên;sau đó chứng minh là trong cách điền X;Y;Z không có 2 kí tự liên tiếp bằng nhau và lập 1 song ánh giữa 1 cách điền X;Y;Z không có 2 kí tự liên tiếp bằng nhau và 1 cách điền A;B;C.Sau đó tính số cách điền X;Y;Z nhờ truy hồi ra kết quả là 2^2001-2
tổng cộng có 2^2001+1 cách
bài này nếu giải đầy đủ thì rất dài

Bài viết đã được chỉnh sửa nội dung bởi vnm: 26-01-2007 - 10:52

[tanlsth]

Hướng đi trên đúng là hướng đi của mình
Nhưng để ra thật thì còn rất dài và phức tạp vì vậy khó post lên diễn đàn được mong mọi người thông cảm

[manutd]

sau đó chứng minh là trong cách điền X;Y;Z không có 2 kí tự bằng nhau

đoạn này hiểu như thế nào đây ?

[vnm]

không có 2 kí tự liên tiếp bằng nhau;tớ đã sửa lại rồi đấy
mấy nhận xét này trừ đoạn thiết lập song ánh thì đều dễ chứng minh
nếu bạn nào vướng đoạn này hôm sau tớ sẽ post

[manutd]

không có 2 kí tự liên tiếp bằng nhau;tớ đã sửa lại rồi đấy
mấy nhận xét này trừ đoạn thiết lập song ánh thì đều dễ chứng minh
nếu bạn nào vướng đoạn này hôm sau tớ sẽ post

bạn post đi