Trong một cuộc thi có các thí sinh thuộc 6 trường khác nhau. Danh sách các thí sinh gồm 2010 người đánh số thứ tự từ 1,2,..,2010. Chứng minh có ít nhất 1 thí sinh mà số thứ tự bằng tổng các số thứ tự của 2 thí sinh cùng trường với thí sinh đó hoặc gấp 2 lần số thứ tự của 1 thí sinh cùng trường với thí sinh đó.
Số thứ tự của thí sinh
#2
Đã gửi 29-11-2013 - 22:44
Trong một cuộc thi có các thí sinh thuộc 6 trường khác nhau. Danh sách các thí sinh gồm 2010 người đánh số thứ tự từ 1,2,..,2010. Chứng minh có ít nhất 1 thí sinh mà số thứ tự bằng tổng các số thứ tự của 2 thí sinh cùng trường với thí sinh đó hoặc gấp 2 lần số thứ tự của 1 thí sinh cùng trường với thí sinh đó.
Sau đây là cách giải của anh quocbaolqd11
Xét đồ thị biểu diễn các số thuộc tập $\left \{ 0,1,2,3,4,5,...,2010 \right \}$ thành các điểm của 1 đồ thị đầy đủ 2010 đỉnh và cạch nối giữa 2 điểm x,y bất kì tô màu của tập chứa $\left | x-y \right |$ (tức là có 6 tập thì ta sẽ tô màu mỗi tập đó bởi 6 màu khác nhau và các màu đó cũng dùng để tô các cạnh)
Dễ dàng CM được đồ thị đầy đủ 2011 đỉnh có các cạnh được tô bởi 6 màu thì tồn tại 1 tam giác có 3 cạnh tô bởi 1 màu.
Gọi 3 đỉnh của tam giác là $x<y<z$ khi đó ta có $y-x,z-y,z-x$ cũng được tô bởi 1 màu nên 3 số đó thuộc cùng một tập hợp.
Lại có $z-x=\left ( z-y \right )+\left ( y-x \right )$
Suy ra đpcm
- nhatquangsin, quocbaolqd11 và SSA thích
#4
Đã gửi 30-11-2013 - 13:50
bạn đưa xem thử, mình không biết về bài đó.
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh