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

[Trần Đức Anh @@]

Bài toán: Tại một hội nghị, có 2013 đại biểu ngồi quanh một chiếc bàn tròn. Sau giờ giải lao, các đại biểu ngồi lại vào bàn ( nhưng chỗ ngồi có thể thay đổi). Chứng minh rằng có ít nhất hai đại biểu mà số người ngồi giữa hai đại biểu đó không thay đổi sau giờ giải lao

Bài viết đã được chỉnh sửa nội dung bởi Trần Đức Anh @@: 22-11-2012 - 21:56

[The Gunner]

Ta đánh số các vị trí trên bàn tròn lần lượt là $1,2,...,2013$
người ở vị trí thứ $i$ sau giờ giải lao sẽ ngồi vào vị trí $f(i)$ với $f(1),f(2),...,f(2013)$ là một hoán vị của $1,2,...,2013$
ta chứng minh tồn tại hai số $a$ và $b$ thỏa mãn $f(a)-a \equiv f(b)-b (\mod 2013)$
Thật vậy, giả sử phản chứng ko tồn tai thì $f(i)-i$ lập thành một hệ thặng dư đầy đủ modulo 2013
lấy xích ma lại suy $0 \equiv 0+1+2+...+2012 \equiv 0 (\mod 2013)$
Thấy chả vô lí nhỉ, hình như bài này thì đk phải là số chẵn tức 2013 là ko tồn tại còn nếu thay 2013 là số chẵn thì ok
ví dụ với 5 thì ta xếp đc 1,2,3,4,5->1,4,2,5,3 thỏa mãn số đại biểu sau h giải lao giữa 2 người bất kì có thay đổi