Jump to content

Photo

Xác định số ngày nhỏ nhất cần để kết thúc giải đấu.

- - - - -

  • Please log in to reply
3 replies to this topic

#1
Hieutran2000

Hieutran2000

    Hạ sĩ

  • Thành viên
  • 54 posts
Trong 1 giải đấu cờ vua có $2017$ người chơi tham gia. Mỗi người chơi phải đấu với $2016$ người chơi còn lại và không người nào chơi quá 1 trận trong cùng 1 ngày. Xác định số ngày nhỏ nhất cần để kết thúc giải đấu.

$\sum =\prod$


#2
boyanonymous

boyanonymous

    Binh nhì

  • Thành viên mới
  • 14 posts

Chỉ cần 2017 ngày thôi 


Plz like for me if it help you. Thank  you !


#3
boyanonymous

boyanonymous

    Binh nhì

  • Thành viên mới
  • 14 posts

Khi chi cặp thì mỗi ngày sẽ có số chẵn người bắt cặp , nếu là lẻ người thì sẽ chẵn cặp lẻ 1 người => bất biến chẵn lẻ 

số chẵn người ban đầu thì cần số đó trừ 1 số ngày 

số  lẻ số người ban đầu thì cần đúng số đó người 

Đây là ý kiến riêng thôi mình  chưa kiểm lại ^^


Plz like for me if it help you. Thank  you !


#4
Hieutran2000

Hieutran2000

    Hạ sĩ

  • Thành viên
  • 54 posts

Chỉ cần 2017 ngày thôi

Biểu diễn các người chơi bằng các đỉnh của đồ thị đầy đủ có 2017 đỉnh. Những người chơi trong 1 ngày ta biểu diễn bằng tập các cạnh không có điểm chung. Từ đó số ngày nhỏ nhất để kết thúc giải đấu chính là số màu nhỏ nhất để tô các cạnh của $K_{2017}$ thỏa mãn mỗi cặp cạnh có 1 đỉnh chung thì có màu khác nhau ( do có thể dùng các màu giống nhau để tô các cạnh tương ứng với các trận đấu được chơi trong cùng 1 ngày). Do đó theo định lí Vizing số ngày cần tìm là 2017.


Edited by Hieutran2000, 10-06-2017 - 22:12.

$\sum =\prod$





1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users