Bài tổ hợp về các số trên đường tròn

[TrauBo]

Chia đường tròn thành $2n$ cung bằng nhau. Chọn $n$ cung bất kì và viết các số theo thứ tự từ $1 \to n$ theo chiều kim đồng hồ trên $n$ cung ấy. Trong $n$ cung còn lại cũng viết các số theo thứ tự từ $1 \to n$ ngược chiều kim đồng hồ. Chứng minh tồn tại 1 đường kính của đường tròn chia đường tròn thành 2 phần $n$ cung mà mỗi phần đều có đủ các số từ $1 \to n$.

Cảm ơn mọi người.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[thiendienduong]

Nguyên văn bởi TrauBo

Chia đường tròn thành $2n$ cung bằng nhau. Chọn $n$ cung bất kì và viết các số theo thứ tự từ $1 \to n$ theo chiều kim đồng hồ trên $n$ cung ấy. Trong $n$ cung còn lại cũng viết các số theo thứ tự từ $1 \to n$ ngược chiều kim đồng hồ. Chứng minh tồn tại 1 đường kính của đường tròn chia đường tròn thành 2 phần $n$ cung mà mỗi phần đều có đủ các số từ $1 \to n$.

Cảm ơn mọi người.

Để tự nhiên mình sẽ trình bày lại toàn bộ quá trình mình phát hiện và chứng minh bài này.
Trước tiên, để thống nhất mình có một số quy ước sau:
1. Không mất tính tổng quát, ta có thể giả sử các số từ $1\rightarrow n $ theo chiều kim đồng hồ được viết trước và $x_{1}=1. $

2. Chúng ta lấy trục màu xanh làm trục mốc.
3. So với trục mốc, $x_{i} $ là giá trị được viết ở lượt thứ nhất và ở cung thứ $i $. Tương tự, $y_{i} $ là giá trị được viết ở lượt viết sau và được viết ở cung thứ $i $ . (thứ tự cung có màu xanh)
4. $n $ số có màu đà từ $1 \rightarrow n $ là $n $ đường kính chia đường tròn thành $2n $ cung. (trục mốc là đường kính $1 $)

Phát hiện:

Mình đã thực hiện một ví dụ như hình trên và phát hiện ra cách tổng quát để xác định đường kính thỏa đề (gọi là $(*) $) như sau:
Sau khi ta viết xong $n $ số theo chiều kim đồng hồ như quy ước 1. sẽ còn $n $ cung trống. Từ trục mốc ta gọi tên $n $ cung trống đó theo chiều ngược chiều kim đồng hồ là "cung trống $k $", ($k\in \left \{ 1;2;...;n \right \} $)
Khi đó, nếu $n $ số từ $1 \rightarrow n $ theo ngược chiều kim đồng hồ được viết mà cung trống $k $ nhận giá trị $1 $ thì đường kính $k $ sẽ chia đường tròn thành $2 $ phần thỏa đề.
Chứng minh:
Xét một trường hợp bất kì mà $n $ số theo chiều kim đồng hồ đã được viết.
Ta chứng minh $(*) $ bằng quy nạp.
1./ Ta đi chứng minh nếu cung trống $1 $ nhận giá trị $1 $ thì (*) đúng, tức trục mốc là đường kính thỏa đề.
Để tiện, ta gọi theo hình vẽ: trục mốc chia đường tròn thành $2 $ phần: phần phải và phần trái.
Gọi số lớn nhất phần phải là $t $, mà do $n $ số đầu tiên được viết theo chiều kim đồng hồ nên $t $ số nhỏ nhất của lượt viết đầu tiên ở phần phải ($(1) $) và phần trái còn $t $ cung trống.
Vả lại giá trị $1 $ của lượt viết $2 $ nằm ở cung trống $1 $ nên $t $ số nhỏ nhất của lượt viết này nằm ở phần trái và hiển nhiên $n-t $ số lớn nhất còn lại của lượt viết $2 $ "ngoan ngoãn" nằm ở phần phải ($(2) $).
Từ $(1) $ và $(2) $, ta có điều cần phải chứng minh.
2./ Giả sử $(*) $ đúng đến $k $, ($1\leq k< n $), tức giá trị $1 $ lượt $2 $ nằm ở cung trống $k $ và đường kính $k $ là đường kính thỏa đề.
Ta cần chứng minh $(*) $ cũng đúng với $k+1 $.
Xét trường hợp đường kính $k $ thỏa đề. Khi đó dĩ nhiên $2n $ số đã được viết cố định lên $2n $ cung.
Ta xét phần đường tròn chứa giá trị $x_{1}=1 $, gọi đây là phần $1 $ và phần còn lại là phần $2 $.
I. Gọi giá trị lớn nhất của lượt viết $2 $ mà nằm ở phần $1 $ là $t. $
Bây giờ ta chứng minh hoặc $y_{2n-k+1}=t+1 $ hoặc $x_{2n-k+1}=t $.
Giả sử ngược lại thì $x_{2n-k+1}=p $ với $p\neq t. $
Nếu $p<t $
Do lượt $1 $ được viết theo cùng chiều kim đồng hồ với $x_{1}=1 $ nên giá trị $x_{2n-k+1}=t $ phải nằm ở phần $1 $: mâu thuẫn vì có $2 $ giá trị $t $ nằm ở phần $1 $
Nếu $p>t $
Do lượt $1 $ được viết theo cùng chiều kim đồng hồ với $x_{1}=1 $ nên giá trị $x_{2n-k+1}=t $ phải nằm ở phần $2 $.
Mà $t $ là giá trị lớn nhất của lượt viết $2 $ ở phần $1 $
nên $t $ cũng là giá trị lớn nhất của lượt viết $1 $ ở phần $2 $: mâu thuẫn với $p>t $
Do đó ta có điều cần chứng minh.
II. Tương tự, gọi giá trị nhỏ nhất của lượt viết $2 $ mà nằm ở phần $1 $ là $t. $,ta cũng chứng minh hoặc $x_{n-k+1}=t-1 $ hoặc $y_{n-k+1}=t $.
Kết hợp I và II, ta thấy khi cung trống $k+1 $ nhận giá trị $1 $ của lượt viết $2 $ thì nếu xoay đường kính $k $ lên vị trí của đường kính $k+1 $, các giá trị của mỗi phần đường tròn được bù đắp lại vừa đủ bộ số từ $1 \rightarrow n $.
Theo nguyên lý quy nạp, $(*) $ được chứng minh.
Vậy bài toán được giải quyết hoàn toàn.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[keodua123]

Nguyên văn bởi thiendienduong

2./ Giả sử $(*) $ đúng đến $k $, ($1\leq k< n $), tức giá trị $1 $ lượt $2 $ nằm ở cung trống $k $ và đường kính $k $ là đường kính thỏa đề.
Ta cần chứng minh $(*) $ cũng đúng với $k+1 $.
Xét trường hợp đường kính $k $ thỏa đề. Khi đó dĩ nhiên $2n $ số đã được viết cố định lên $2n $ cung.
Ta xét phần đường tròn chứa giá trị $x_{1}=1 $, gọi đây là phần $1 $ và phần còn lại là phần $2 $.
I. Gọi giá trị lớn nhất của lượt viết $2 $ mà nằm ở phần $1 $ là $t. $
Bây giờ ta chứng minh hoặc $y_{2n-k+1}=t+1 $ hoặc $x_{2n-k+1}=t $.
Giả sử ngược lại thì $x_{2n-k+1}=p $ với $p\neq t. $
Nếu $p<t $
Do lượt $1 $ được viết theo cùng chiều kim đồng hồ với $x_{1}=1 $ nên giá trị $x_{2n-k+1}=t $ phải nằm ở phần $1 $: mâu thuẫn vì có $2 $ giá trị $t $ nằm ở phần $1 $
Nếu $p>t $
Do lượt $1 $ được viết theo cùng chiều kim đồng hồ với $x_{1}=1 $ nên giá trị $x_{2n-k+1}=t $ phải nằm ở phần $2 $.
Mà $t $ là giá trị lớn nhất của lượt viết $2 $ ở phần $1 $
nên $t $ cũng là giá trị lớn nhất của lượt viết $1 $ ở phần $2 $: mâu thuẫn với $p>t $
Do đó ta có điều cần chứng minh.
II. Tương tự, gọi giá trị nhỏ nhất của lượt viết $2 $ mà nằm ở phần $1 $ là $t. $,ta cũng chứng minh hoặc $x_{n-k+1}=t-1 $ hoặc $y_{n-k+1}=t $.
Kết hợp I và II, ta thấy khi cung trống $k+1 $ nhận giá trị $1 $ của lượt viết $2 $ thì nếu xoay đường kính $k $ lên vị trí của đường kính $k+1 $, các giá trị của mỗi phần đường tròn được bù đắp lại vừa đủ bộ số từ $1 \rightarrow n $.
Theo nguyên lý quy nạp, $(*) $ được chứng minh.
Vậy bài toán được giải quyết hoàn toàn.

Mình không hiểu đoạn này lắm. Tại sao lại kết hợp I và II rồi suy ra được ... . Bạn giải thích rõ hơn không?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[thiendienduong]

Nguyên văn bởi keodua123

Mình không hiểu đoạn này lắm. Tại sao lại kết hợp I và II rồi suy ra được ... . Bạn giải thích rõ hơn không?

Trước tiên, bạn phải nhớ chúng ta đang xét đường tròn đã nhận các giá trị cố định mà có đường kính $k $ thỏa đề.
Để dễ hiểu bạn phải biết rằng mục đích của phần chứng minh này là: Nếu từ trường hợp trên, ta chuyển số $1 $ của lượt viết $2 $ lên cung trống $k+1 $ (tức các số của lượt $2 $ chuyển đổi vị trị cho nhau theo chiều ngược kim đồng hồ), thì số lớn nhất của phần $1 $ mất đi khi đường kính $k $ chia đường tròn nhưng vẫn nằm trong phần $1 $ khi đường kính $k+1 $ được chọn để chia đường tròn. Tương tự với số nhỏ nhất của phần $1. $ Để từ đó ta suy ra đường kính $k+1 $ thỏa đề.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]