n quả cầu trắng , n quả cầu đen, CWMO 2007

[n.t.tuan]

n quả cầu trắng và n quả cầu đen sắp xếp ngẫu nhiên trên một đường tròn. Bắt đầu từ một quả cầu trắng nào đó, theo hướng kim đồng hồ, các quả cầu trắng được đánh số là 1,2,...,n. Tương tự, bắt đầu từ một quả cầu đen nào đó, theo hướng ngược chiều kim đồng hồ, các quả cầu đen được đánh số là 1,2,...,n. Chứng minh rằng tồn tại một xích n quả cầu mang số 1,2,...,n.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[psquang_pbc]

Để cho đơn giản đề bài ta thay $2n $ quả cầu bằng $2n $ cung Phản chứng rằng kô có chuỗi n cung nào thỏa mãn điều kiện trên .Lấy 1 cung bất kì trong 2n cung đã cho, và đánh số 0. Theo chiều kim đồng hồ đánh số từ $1, 2n-1 $. Ta xét hàm $f(x) $ là số ghi trên cung đánh dấu $x ,0\le x\le 2n-1 $ .Kí hiệu nửa đường tròn thứ $k $ là tập các cung $k+1,k+2,..,k+n $ ( chỉ số lấy theo modun $2n $ ) Ta chia các cung đấy thành $2 $ tập tô xanh và đỏ. Tập các cung chia đỏ là 1 dãy tăng theo thặng dư mod $n $ ( $f(a_{i+1})=f(a_i)+1 $).Tập các cung tô xanh lại giảm. Kí hiệu các chỉ số đầu tiên của 2 loại cung trên là $r(k) $ và $b(k) $, từ đó điều kiện để đường tròn thứ $k $ chứa các số từ $1,2,...,n $ là $b(k)=r(k)-1 $ ( mod $n $)


Xét với nửa đường tròn $k+1 $ ta dễ chứng minh được rằng

$r(k+1)=r(k)+1 $ và $b(k+1)=b(k) $ hoặc là $r(k+1)=r(k) $ và $b(k+1)=b(k)-1 $

Do vậy

$r(k+1)-b(k+1)=r(k)-b(k)+1 $ nên tồn tại $k $ sao cho $r(k)-b(k)=1 $ mod $n $ CM xong


[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[psquang_pbc]

Một cách khác post lên mọi người check xem sao :

Quy nạp theo n. Giả sử n=k đúng. Khi đó ta xếp lại các quả cầu thành 2n đỉnh 1 đa giác đều, vì k đúng lên tồn tại 1 đường thẳng ngăn cách 2 bên đường tròn mỗi bên k quả cầu có thứ tự 1,...k, lấy thêm 2 điểm và co khoảng cách các quả cầu cũ lại để cóa 2k+2 điểm nằm về 2 phía, lần này không nhất thiết phải cóa k+1 mỗi bên, ta sẽ thu được một bên cóa k+1 quả cầu roài có thứ tự từ 1 đến k+1 . Kết thúc cm, mình còn nghi ngờ quá nhưng gấp quá hok có thời gian kiểm tra
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]