Đến nội dung

Hình ảnh

Vietnam TST 2009


  • Please log in to reply
Chủ đề này có 1 trả lời

#1
duca1pbc

duca1pbc

    Trung sĩ

  • Thành viên
  • 190 Bài viết
Có $6n+4$ nhà toán học tham dự 1 hội nghị,trong đó có $2n+1$ buổi thảo luận.Mỗi buổi thảo luận đều có 1 bàn tròn cho 4 người ngồi và n bàn tròn cho 6 người ngồi.Biết rằng 2 người bất kỳ ko ngồi cạnh nhau hoặc đối diện nhau quá 1 lần.
a.Hỏi có thể thực hiện được ko với $n=1$?
b.Hỏi có thể thực hiện được ko với $n>1$?

#2
Hatucdao

Hatucdao

    Sĩ quan

  • Founder
  • 397 Bài viết

Có $6n+4$ nhà toán học tham dự 1 hội nghị,trong đó có $2n+1$ buổi thảo luận.Mỗi buổi thảo luận đều có 1 bàn tròn cho 4 người ngồi và n bàn tròn cho 6 người ngồi.Biết rằng 2 người bất kỳ ko ngồi cạnh nhau hoặc đối diện nhau quá 1 lần.
a.Hỏi có thể thực hiện được ko với $n=1$?
b.Hỏi có thể thực hiện được ko với $n>1$?

Có thể suy nghĩ đơn giản như sau: Minh chia 6n+4 người thành 1 Sếp và 2n+1 nhóm, mỗi nhóm 3 người. Sếp sẽ luôn ngồi ở bàn 4 người, còn mỗi nhóm sẽ luôn ngồi chung (dù là trong bàn 4 người hoặc trong bàn 6 người). Chú ý là với bàn 6 người, mình có thể xếp 2 nhóm sao cho ko có thành viên nào trong cùng 1 nhóm ngồi cạnh nhau hoặc ngồi đối diện nhau (gọi 2 nhóm là a,b,c và x,y,z thì mình có thể xếp xen kẽ là a x b y c z).

Như vậy, mình có thể tìm 1 cách xếp thỏa mãn đề bài nếu mình sắp được các nhóm sao cho: mỗi nhóm sẽ ngồi với Sếp 1 lần (ở bàn 4 người), và 2 nhóm bất kỳ ngồi chung với nhau (trong bàn 6 người) tối đa 1 lần.

Với n=1, mình có cách xếp đơn giản cho 1 sếp và 3 nhóm A1,A2,A3 như sau:
ngày 1: sếp+A1 (bàn 4 người), A2+A3 (bàn 6 người).
ngày 2: sếp+A2, A1+A3
ngày 3: sếp+A3, A1+A2

Với n=2, mình có 1 Sếp và 5 nhóm A1,...,A5. Có thể xếp như sau:
ngày 1: sếp+A1 (bàn 4 người), A2+A3 (bàn 6 người), A4+A5 (bàn 6 người) .
ngày 2: sếp+A2, A1+A4, A3+A5
ngày 3: sếp+A3, A1+A5, A2+A4,
ngày 3: sếp+A4, A1+A3, A2+A5,
ngày 3: sếp+A5, A1+A2, A3+A4.

Như vậy bài toán sẽ được giải cho n>1 bất kỳ nếu mình có thể tìm ra n cách chia 2n+1 nhóm (mỗi lần chia có 1 nhóm lẻ và n cặp) sao cho không có 2 nhóm nào ở chung 1 cặp quá 1 lần chia. Điều này có lẽ đúng (với n=1,n=2) và có lẽ có thể chứng minh dễ dàng dựa vào các đường chéo của đa giác 2n+1. Any one can help this step?
Hoa đào năm ngoái đừng cười
Vì chưng xa cách nên người nhớ nhau




1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh