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

[manhhung2013]

Chia hình tròn thành 2n quạt bằng nhau. Tô n quạt màu xanh và n quạt màu đỏ. Bắt đầu từ quạt đỏ nào đó theo chiều kim đồng hồ lần lượt viết các số 1;2;3...;n. Lại bắt đầu từ quạt xanh nào đó theo chiều ngược kim đồng hồ viết lần lượt các số 1;2;3...;n. Chứng minh rằng tồn tại  nửa hình tròn chứa đủ các số 1;2;3...;n.

Bài viết đã được chỉnh sửa nội dung bởi halloffame: 06-07-2017 - 20:44

[redfox]

Bỏ qua TH hiển nhiên tồn tại nửa đường tròn chứa toàn quạt đỏ (hoặc quạt xanh).

Xét $2n$ nửa đường tròn $H_1,...H_{2n}$, $H_{k+1}$ được tạo bằng cách quay $H_k$ theo tâm đường tròn góc $\frac{\pi }{n}$ theo chiều kim đồng hồ. Gọi $Đ_k,X_k$ lần lượt là các số được ghi trên quạt đỏ và quạt xanh đầu tiên trên $H_k$ (thứ tự các quạt theo chiều kim đồng hồ).

Bổ đề: Nếu $d_k=Đ_k-X_k\equiv 1(mod\; n)$ thì quạt $H_k$ chứa đủ các số $1,...,n$

Giả sử $H_k$ chứa $x$ quạt đỏ, $n-x$ quạt xanh. Các số được ghi trên các quạt đỏ đồng dư theo mod $n$ với các số $Đ_k+i=X_k+i+1,0\leq i\leq x-1$, các số được ghi trên các quạt xanh đồng dư theo mod $n$ với các số $X_k-j,0\leq j\leq n-x-1$. Dễ thấy các số được ghi trên các quạt đỏ (quạt xanh) phân biệt. Giả sử tồn tại một số được ghi trên một quạt đỏ và một quạt xanh nào đó suy ra tồn tại $0\leq i\leq x-1,0\leq j\leq n-x-1$ sao cho $X_k+i+1\equiv X_k-j(mod\; n)\Rightarrow i+j+1\equiv 0(mod\; n)$ (vô lý vì $0<i+j+1<n$). Vậy các số ghi trên $H_k$ lập thành hệ thặng dư đầy đủ mod $n$ nên chứa đủ các số $1,...,n$.

Ta xét hai trường hợp: (coi $d_{2n+1}=d_1$)

TH1: Quạt đầu tiên trên $H_k$ màu đỏ, khi đó $Đ_{k+1}\equiv Đ_k+1(mod\; n),X_{k+1}=X_k\Rightarrow d_{k+1}\equiv d_k+1(mod\; n)$

TH2: Quạt đầu tiên trên $H_k$ màu xanh, khi đó $X_{k+1}\equiv X_k-1(mod\; n),Đ_{k+1}=Đ_k\Rightarrow d_{k+1}\equiv d_k+1(mod\; n)$

Vậy $d_{k+1}\equiv d_k+1,\forall 1\leq k\leq 2n$. Dễ thấy $d_1,...,d_n$ lập thành hệ thặng dư đầy đủ mod $n$ nên tồn tại $d_k\equiv 1(mod\; n)$, nửa đường tròn $H_k$ thỏa mãn đề bài.

(Q.E.D)

Có đúng $2$ nửa đường tròn thỏa mãn.

Bài viết đã được chỉnh sửa nội dung bởi halloffame: 06-07-2017 - 20:46