Lời giải chi tiết đề thi chọn Đội tuyển quốc gia Việt Nam dự thi IMO năm 1990

1

LỜI GIẢI ĐỀ THI CHỌN ĐỘI TUYỂN QUỐC GIA DỰ THI IMO NĂM 1990

************

Bài 1. Trong mặt phẳng cho đa giác lồi M M M_{0 1 2}...M_2n(n1) mà 2n1cùng nằm trên một đường tròn ( )C có bán kính R. Giả sử điểm A nằm trong đa giác lồi đó sao cho các

góc    

0 1, 1 2, 2 3,..., 2_n 0

M AM M AM M AM M AM đều bằng nhau và bằng ² 2n 1



 , điểm A không trùng với tâm của ( )C và B là điểm nằm trong ( )C sao cho AB vuông góc với đường kính của ( )C đi qua A. Chứng minh rằng:

0 1 2 2

0 1 2 2 1

...

2 1

1 1 1 ... 1 2 1

n

n

AM AM AM AM

n AB R

n

AM AM AM AM _

   

   

    

Lời giải.

Do các góc   

0 1, 1 2,..., 2_n 0

M AM M AM M AM đều bằng nhau và bằng ² 2n 1



 nên nếu xét các vector đơn vị AM₀,AM AM₁, ₂,...,AM₂_n lần lượt đặt trên các đoạn tương ứng là

0, 1, 2,..., 2_n

AM AM AM AM thì đa giác M M M₀ ₁ ₂...M₂_n là đều và có A là trọng tâm.

Do đó:   AM0AM1AM2... AM2_n 0

hay ^{0 1 2 2}

0 1 2 2

... ⁿ 0

n

AM AM AM AM

AM  AM  AM  AM 

   

.

Ta có:

B

O A M0

M2

M3

M4

M5

M2n-1

M2n M1

2

0 1 2 2

0 1 2 2 0 1 2 2

0 1 2 2

0 0 1 1 2 2 2 2

0 1 2 2

0 0

... . . . ... .

. . . .

...

( )

n

n n

n

n n

n

AM AM AM AM

OM OM OM OM OM OM OM OM

AM AM AM AM

OM AM OM AM OM AM OM AM

AM AM AM AM

OA AM AM

         

     

 

       

  

2 2

1 1 2 2

0 1 2 2

2 2 2

0 1 2 2 0 1 2

0 1 2 2 0 1

( ).

( ) ( ).

...

. ...

n n

n n

n

OA AM AM OA AM AM OA AM AM

AM AM AM AM

AM AM AM AM AM AM AM

OA AM AM AM AM AM AM AM



 

    

 

        

 

  

     

   

 ²

2

2 2

0 1 2 2

...

...

n n n

AM AM

AM AM AM AM

 

  

 

 

    

Suy ra (2 1) _{0 1 2} ... ₂ ^{0 1 2 ... 2}

2 1

n n

AM AM AM AM

n R AM AM AM AM R

n

   

       

 .

Tiếp theo, từ đẳng thức ^{0 1 2 2}

0 1 2 2

... ⁿ 0

n

AM AM AM AM

AM  AM  AM   AM 

   

, ta thấy rằng

2 2

0 1 2

0 0

0 1 2 0 1 2

1 1 1 1

... ...

n n

n i

i i

n n i i

OM OM OM OM

OA OA

AM AM AM AM AM AM  AM  AM

 

        

 

 

 

   

 

. Bình phương hai vế của đẳng thức này, ta được

2 2

2 2 2 2

2 2 2

2 2

0 0 0 0 2 0

2 2

2 2

2

0 2 0 0 2

1 1 1 1

2 .

. 1 .

2 ( ) 2

. .

      

      

 

 

   

      

     

       

    

    

  



    

n n n n

i

i i i i i i i j n i j i i

n

i j i j

i j n i j i i i j n i j

OA OM OA R

AM AM AM AM AM AM

OM OM OA OM OM

R OA

AM AM AM AM AM _{0 2}

2 2 2

2

0 0 2 0 2

. 1 .

2 (*)

. .

  

      

 

 

 

 

 

    

 

 



  



  ^{i j n i j}

n

i j

i i i j n i j i j n i j

AM AM OM OM

AB OA

AM AM AM AM AM

Ta sẽ rút gọn tổng

0 2

. .

i j

i j n i j

OM OM AM AM

  



 

. Ta vẫn sử dụng các tính chất của tích vô hướng:

2 2 2 2 2

0 2 0 2 0 2 0 2

2 2

2

0 2 0 2

2

0 2

. 2

2 . . . .

2 . .cos

2

. .

2 .

i j i j i j i j

i j n i j i j n i j i j n i j i j n i j

i j i j i j

i j n i j i j n i j

i

i j n i j j

OM OM OM OM M M R M M

AM AM AM AM AM AM AM AM

AM AM AM AM M AM

R

AM AM AM AM

AM R

AM AM AM

           

     

  

 

  

 

 

 

   

 



 

0 , 2 , 0 2

2 cos _{i j}

i j n i j i j n

M AM

     







Ta sẽ chứng minh rằng

0 2

2 1

cos ^{i j} 2

i j n

M AM n

  

  



(**). Thật vậy,

3 Ta thấy rằng C₂²_n1n n(2 1) góc M AM_{i j}, 0 i j2n có thể chia thành 2n1 bộ, trong đó, mỗi bộ gồm các góc ^{2 ,1}

2 1

k k n

n

  

 .

Hơn nữa

1 1

1 1

2 1 (2 1) (2 1) 1 (2 1)

cos sin sin sin sin sin

2 1 2 1 2 2 1 2 1 2 2 1 2 1

2 1 2 1

cos sin sin cos

2 1 2 1 2 2 1 2 1 2

n n

k k

n n

k k

k k k n

n n n n n n

k k

n n n n

     

   

 

 

         

        

            

     

   

 

 

Do đó, (**) được chứng minh. Do đó, tổng

0 2

. .

i j

i j n i j

OM OM AM AM

  



 

chính là

2

0 2 0 2 0 , 2 ,

2 2 2

0 2 0 0

. 2

2 (2 1)

. .

2 1

.

i j i

i j n i j i j n i j i j n i j j

n n

i

i j n i j i i i

OM OM R AM

AM AM AM AM AM n

R AM

AM AM AM

        

    

   

   

     

 

 

  

  

 

Thay vào đẳng thức (*), ta được

2 2

2 2 2

2

2

0 0 2 0 2 0 0

2 2 2 2

2

2

0 0 2 0 0

2 2 2 2

2

0 0 0

1 2 1

2 . .

1 1

2 .

1 1

n n n

i

i i i j n i j i j n i j i i i

n n n

i

i i i j n i j i i i

n n

i

i i i i i

OA R

AB AM

AM AM AM AM AM AM

AB AB AM

AM AM AM AM

AB AM

AM AM

        

     

  

   

      

 

 

   

      

 

 

   

    

   

    

   

 

2

2 0

2

0

1

n n i

i n

i i

AM AB

AM





 

 

 

 

 



Đến đây, ta thấy hai bất đẳng thức cần chứng minh khá hiển nhiên vì:

2 2 2 2 2 2 2

2 0 0 0

2 2 2

0 0 0

2 2

2

0 0

2 1 2 1

1 2 1 1 1 2 1

1 (2 1)

n n n

i i i

i i i

n n n

i i i i i i

n n

i

i i i

AM AM AM

n n

AB n n

AM AM AM

AM n

AM

  

  

 

       

         

         

 

       

   

   

   

   

 

 

   

   

  

  

 

Bất đẳng thức này đúng theo bất đẳng thức Cauchy.

Vậy ta có đpcm.

4 Bài 2. Cho bốn số thực dương A B a b, , , . Xét dãy số thực (x_n) thỏa mãn:

1 2

2 2

3 3

1 1

,

, 2

n n n

x a x b

x _ A x B x _ n

 



   



. Chứng minh rằng tồn tại giới hạn lim _n

n x

 và tìm giới hạn đó.

Lời giải.

Nếu dãy số này có giới hạn thì gọi đó là L. Do A B a b, , , 0 nên dãy số xác định như trên luôn dương và L0.

Chuyển công thức tổng quát đã cho: x_n1 A x³ _n² B x³ _n²_1 qua giới hạn, ta có:

3 2 3 2 3 2( ) ( )3

L A L B L L L A B L A B . Xét dãy số

 

un có ^u1min



^{a b A B, , (  ) ,3}



^{un1(A B )3u nn2, 1, 2,3,...}

Ta sẽ chứng minh rằng dãy này giảm và bị chặn dưới. Thật vậy,

Ta có ^{1 3 2}



³



^{3 2} 2 ³ 3 3 2

( )

.

( ) ( )

n

n n n n n

n n

A B u

u u u A B u u

A B A B u u



 

    

    .

Do u₁(AB)³ nên bằng quy nạp, ta có u_n (A B )³ với mọi n1. Từ đó suy ra u_n1u_n 0,n hay đây là dãy tăng.

Dãy (u_n) tăng và bị chặn trên bởi (A B )³ nên có giới hạn. Trong công thức xây dựng dãy, chuyển qua giới hạn, ta được limu_n (AB)³.

Hoàn toàn tương tự, ta chứng minh được dãy

 

vn xác định như sau



³



^{3 2}

1 max , , ( ) , _n 1 ( ) _n, 1, 2,3,...

v  a b A B v _  A B v n

là dãy giảm và bị chặn dưới bởi (A B )³ nên có giới hạn, giới hạn đó cũng là (A B )³. Do đó, ^limun ^limvn ⁽AB^{) .3}

Tiếp theo, ta sẽ chứng minh rằng u_n min



x2_n1,x2_n



max



x2_n1,x2_n



v n_n, 1, 2, 3,... (*) bằng quy nạp theo n.

5 - Với n1, ta thấy u1min



x x1, 2



max



x x1, 2



v1 là đúng.

- Giả sử (*) đúng với nk1, tức là u_k min



x2_k1,x2_k



max



x2_k1,x2_k



v_k. Khi đó, ta có u_k1 (A B )³u_k²  A u³ _k² B u^{3 2}_k A x³ 2²_k B x³ 2²_k1 x2_k1. Suy ra u_k1 A u^{3 2}_k1 B u³ _k²  A x³ ₂²_k1 B x³ ₂²_k x_2k2.

Do đó, ta được u_k1 min



x2_k1,x2_k2



.

Hoàn toàn tương tự, ta cũng có max



x2_k1,x2_k



v_k1 hay (*) cũng đúng với nk1.

Theo nguyên lí quy nạp, (*) được chứng minh.

Từ đó suy ra hai dãy con



x2_k1

  

, x2_k bị kẹp bởi hai dãy

   

un ^, vn ; đồng thời, ta đã chứng minh được rằng limu_n limv_n (AB)³ nên limx_2n1limx_2n (AB)³.

Vậy dãy

 

xn có giới hạn hữu hạn và ^limxn ⁽AB^).

6 Bài 3. Chứng minh rằng không tồn tại hàm số f x( ) xác định với mọi số thực x và thỏa mãn f f x( ( ))x²2 với mọi x.

Lời giải.

Trước hết, ta chứng minh bổ đề sau.

Gọi Sn là tập hợp các điểm bất động của hàm số f^{( )n} ( )x . Khi đó f x( ) đơn ánh trên

, 1

Sn  n .

Chứng minh. Thật vậy,

Giả sử xS_n, khi đó f^{( )n} ( )x x. Suy ra f^{( )n} ( ( ))f x  f^(n1)( )x  f f( ^{( )n} ( ))x  f x( ), tức là ( )

f x cũng là một điểm bất động của f^{( )n} ( )x hay f x( )S_n. Do đó f x( ) ánh xạ Sn vào chính nó.

Xét a b, S_n và f a( ) f b( ), khi đó a f^{( )n} ( )a  f^(n1)( ( ))f a  f^(n1)( ( ))f b  f^{( )n} ( )b b nên ( )

f x là đơn ánh trên Sn.

Từ đó, ta suy ra rằng nếu S_n là tập hữu hạn thì f S( _n) là phép hoán vị trong S_n. Bổ đề được chứng minh.

Hơn nữa, nếu x là điểm bất động của f x( ) thì: f x( )x f f x( ( )) f x( )x nên x cũng là điểm bất động của f⁽²⁾( )x hay S1S2.

Bằng lập luận tương tự, ta có: S₁S₂ S₄ S₈...

*Trở lại bài toán.

Giả sử tồn tại hàm số f x( ) thỏa mãn đề bài, ta sẽ xác định các tập hợp S S₂, ₄.

Những điểm bất động của f⁽²⁾( )x chính là nghiệm của phương trình:

2 2 1, 2

xx  x  x . Do đó: S₂  { 1, 2}.

Những điểm bất động của f⁽⁴⁾( )x chính là nghiệm của phương trình:

2 2 4 2 1 5

( 2) 2 4 2 0 1, 2,

x x x x x x x x  2

             .

Do đó: ₂ 1 5

{ 1, 2, }

S  2

  . Đặt 1 5 1 5

2 , 2

c   d  

  .

Do c d, S4 \S2 nên theo bổ đề trên thì f c( )c hoặc f c( )d. Ta xét hai trường hợp:

-Nếu f c( )c thì f⁽²⁾( )c  f c( )c nên cS2, mâu thuẫn.

-Nếu f c( )d thì f d( )c, do đó: c f d( ) f f c( ( )) f⁽²⁾( )c nên cS2, mâu thuẫn.

Vậy không tồn tại hàm số nào thỏa mãn đề bài.

7 Bài 4. Xét tập T gồm hữu hạn các số nguyên dương thỏa mãn hai điều kiện sau:

(1)Với hai phần tử bất kì của T thì ước chung lớn nhất và bội chung lớn nhất của chúng cũng thuộc T.

(2)Với mỗi phần tử x của T, tồn tại phần tử x’ cũng thuộc T sao cho x và x’ nguyên tố cùng nhau và bội chung lớn nhất của chúng là số lớn nhất thuộc T.

Với mỗi tập T như thế, gọi T là số phần tử của nó. Tìm số T lớn nhất, biết rằng 1990



T .

Lời giải.

Gọi N là phần tử lớn nhất của T. Nếu T không chứa 1 thì theo điều kiện (2), nó phải chứa một số X 1 nguyên tố cùng nhau với N, nhưng khi đó bội chung nhỏ nhất của chính là tích của N và X, do NX  N nên điều này mâu thuẫn với cách chọn N, suy ra 1T. Cũng theo điều kiện (2), ta thấy rằng mỗi phần tử d của T là ước của N và ^N

d nguyên tố cùng nhau với d.

Giả sử N có n ước nguyên tố phân biệt là p p p₁, ₂, ₃,...,p_n. Ta thấy chỉ cần xét lũy thừa của các số này trong phân tích N thành thừa số nguyên tố bằng 1 vì nếu có một lũy thừa nào đó lớn hơn 1 thì theo điều kiện (2), ta thấy khi xét các phần tử của tập hợp này, vẫn phải giữ nguyên lũy thừa đó ở mỗi phần tử thuộc T chứ không thể tách ra được và vì thế mà số lượng phần tử không đổi. Do đó, không mất tính tổng quát, ta có thể giả sử rằng N  p p1 2p3 ... p_n. (N ở đây là số square – free).

Ta gán cho mỗi phần tử xT, một bộ gồm n phần tử ( ,d d1 2,...,d_n),d_i

 

0,1 trong đó

1, 2,..., _n

d d d lần lượt là lũy thừa của p p p1, 2, 3,...,p_n trong phân tích thành thừa số nguyên tố của x.

Dễ thấy rằng mỗi bộ như thế có dạng một xâu nhị phân có độ dài n. Ta đặt (0,0,0,...,0), (1,1,1,...,1)

 

0 1 .

Ta định nghĩa hai phép toán AND và OR như sau:

(1,1) 1, (1,0) (0,1) (0,0) 0

(1,1) (1,0) (0,1) 1, (0,0) 0 (1) 0, (0) 1

AND AND AND AND

OR OR OR OR

NOT NOT

   

   

 

8 Xét hai phần tử x y T,  với các xâu nhị phân đại diện cho chúng lần lượt là

1 2 3

( ,x x x, ,...,x_n) và ( ,y y y_{1 2}, ₃,...,y_n) với ^{x y}_i^, _i^

 

^{0,1 ,i1,n.}

Khi đó, ước chung lớn nhất và bội chung nhỏ nhất của chúng sẽ vẫn thuộc T và được đại diện bằng các xâu nhị phân tương ứng là

1 2 3

( , , ,..., )a a a a_n và ( , , ,..., )b b b_{1 2 3} b_n với ^{a b}_i^, _i^

 

^{0,1 ,i1,n,}

trong đó a_i AND x y b( , ),_{i i i} OR x y i( , ),_{i i} 1, .n

Ta định nghĩa phép cộng module 2 của xy bằng phép toán XOR x y như sau: ( , )

(0,0) (1,1) 0, (0,1) (1,0) 1

XOR XOR  XOR XOR  .

Bằng cách lập bảng xét giá trị của biểu thức, ta chứng minh được rằng



^{( , ), ( ( , ))}



^{( , )}

AND OR x y NOT AND x y XOR x y .

Như thế, với hai phần tử x y T,  , bằng cách thực hiện các phép AND OR NOT một , , cách thích hợp, ta thu được giá trị của phép cộng module 2 của x y, và như thế thì theo định nghĩa của tập hợp T thì XOR x y( , )  x y T.

Để đơn giản, ta kí hiệu  x NOT x( ) và ta gọi một tập hợp S mà nếu x y S,  thì cũng có xy,  x, y S là tập hợp đóng (nếu gọi đầy đủ là đóng dưới phép toán  , ). Rõ ràng, tập hợp T đã cho là một tập hợp đóng như thế.

Xét x T    x x 0 T,  0 1 T nên nếu xét T1 

 

0,1 thì T₁ T và T₁ đóng.

Nếu T T\ ₁ , xét x T T \ ₁ thì ^T₂ ^



^{0 1, , ,x x1}



^{T là đóng.}

Dễ thấy T₁ 2 ,¹ T₂ 2², ta sẽ chứng minh rằng T 2^k với k^. Thật vậy, giả sử rằng T₁ T₂T₃ ...T_m T T, _i 2ⁱ là các tập đóng.

Xét x T T \ _m và ^S



^{xy y T| } _m



^{ S 2m và ST}_m ^{ } (do tính đóng của tập T_m).

9 Đặt T_m1  S T_m thì T_m1 2^m1 và rõ ràng T_m1 cũng là tập đóng. Thật vậy, nếu

, _m

zx y y T  thì    z 1 z x(y1)T_m1.

Điều này có nghĩa là ta có thể mở rộng dãy

 

^T_m ở trên ra thêm nữa và vẫn thỏa mãn số phần tử của tập cuối cùng là lũy thừa của 2 và tất cả các tập đó đều đóng. Quá trình này không thể kéo dài vô hạn được nên phải tồn tại số nguyên dương k sao cho

1 2 ... _{m m} 1 ... _k , _i 2ⁱ

T T  T T _  T T T  hay T 2 .^k

Do đó, ta đã chứng minh được số phần tử của tập hợp ban đầu phải là một lũy thừa của 2, tuy nhiên, theo giả thiết thì T 1990 nên

2 1990

max max 2 1024

k

T k



  .

Ta xét Np p p₁ ₂ ₃...p₁₀ với p p p₁, ₂, ₃,...,p₁₀ là các số nguyên tố phân biệt nào đó. Tập hợp tất cả các ước của số này có 1024 phần tử và thỏa mãn các điều kiện đề bài.

Vậy số phần tử lớn nhất của tập T có thể đạt được là 1024.

10 Bài 5. Cho tứ diện mà mỗi cặp cạnh đối đều có tích độ dài là . Gọi góc giữa các cặp cạnh đó là   , , và các bán kính của các cặp đường tròn ngoại tiếp các mặt của tứ diện là R R R R₁, ₂, ₃, ₄. Chứng minh rằng: ^{2 2 2}

1 2 3 4

sin sin sin

R R R R

    ^ .

Lời giải.

Xét tứ diện A A A A_{1 2 3 4} và kí hiệu a_ij  A_ij ,1i j, 4,i j.

Gọi   , , lần lượt là góc tạo bởi các cặp cạnh chéo nhau

1 2, 3 4; 1 3, 2 4; 1 3, 2 4

A A A A A A A A A A A A ;

1, 2, 3, 4

S S S S và R R R R₁, ₂, ₃, ₄ lần lượt là diện tích và bán kính đường tròn ngoại tiếp của các tam giác A A A A A A A A A A A A_{2 3 4}, _{3 4 1}, _{4 1 2}, _{1 2 3}.

Trước hết, ta sẽ chứng minh đẳng thức sau:

2 2 2 2 2 2 2

1 2 3 4 12 34 13 24 13 24

4(S S S S )(a a. .sin ) (a a. .sin ) (a a. .sin ) . Thật vậy:

Trong không gian Oxyz, xét tứ diện A A A A_{1 2 3 4} có tọa độ các đỉnh là

1( , 0, 0),1 2(0, 2, 0), 3(0, 0, 3), 4( , , ) A a A a A a A x y z . Khi đó:

1 2 ( 1, 2, 0), 1 3 ( 1, 0, 3) A A  a a A A  a a

 

, suy ra

1 2 3

2 2 2 2 2 2 2 2

4 1 2 1 3 1 2 2 3 3 1

4S S_{A A A}   A A A A a a a a a a . Ta cũng có A A1 4 (x a y z A A 1, , ),2 4 ( ,x ya z2, )

, suy ra

1 4 2 4 2 1

1 2 2 1 1 2 1 2

( ( ), ( ) ,

( )( ) ) ( , , )

A A A A yz z y a x a z zx x a y a xy za za a y a x a a

     

       

 

1 2 4

2 2 2

3 1 4 2 4

2 2 2 2

1 2 2 1 1 2

4

( ) ( )

A A A

S S A A A A

z a a xa ya a a

   

    

 

Tương tự, ta có

1 3 4

2 2 2 2 2 2 2

2 2 4 3 4 3 1 3 1 1 3

4S S_{A A A} A A A A y a( a ) (xa za a a )

         

1 2 4

2 2 2 2 2 2 2

1 1 4 2 4 2 3 3 2 2 3

4S S_{A A A} A A A A x a( a ) (ya za a a )

         

. Từ a a a a1 2. 3 4 a a a a1 3. 2 4 a a a a1 4. 2 3 , ta có:

A

B

C

D

11

2 2 2 2 2 2 2 2

1 2 3 4

2

2 2 2

1 2 2 3 3 1 2 3 3 4 4 2 3 4 4 1 1 3 4 1 1 2 2 4

4 1 2 3

2 2

1 2 2 3 3 1 2 3 3 4 4 2

4 1

(sin sin sin ) 4( )

. . . .

4 4 4 4 4

. . . .

4 4

S S S S

a a a a a a a a a a a a a a a a a a a a a a a a

R R R R

a a a a a a a a a a a a

R R

       

        

 

         

        

 

   

    

   



2 2

3 4 4 1 1 3 4 1 1 2 2 4

4

2 3

4 3

4

1 2 2 3 3 4 4 1 1 3 2 4

1 2 3 4 1 2 3 4

. . . .

4 4

( )

a a a a a a a a a a a a

R R

a a a a a a a a a a a a

R R R R R R R R

 

 

    

   

    

  

Do đó: ^{2 2 2}

1 2 3 4

sin sin sin

R R R R

      ^ .

Đây chính là điều phải chứng minh.

12 Bài 6.

Cho n học sinh (n3) đứng thành một vòng tròn và quay mặt vào cô giáo ở tâm đường tròn. Mỗi lần cô giáo thổi còi thì hai em nào đó đứng cạnh nhau đổi chỗ cho nhau, các em còn lại đứng im. Tìm số M nhỏ nhất sao cho sau M lần thổi còi, bằng cách đổi chỗ như trên một cách thích hợp thì các em học sinh đứng được thành một vòng tròn mới sao cho: Hai em lúc đầu đứng cạnh nhau, nhưng hai em đó, tạm gọi là A và B, thì nếu lúc đầu A đứng bên tay trái của B thì lúc kết thúc, A đứng bên tay phải của B.

Lời giải.

Ta thấy rằng yêu cầu của bài toán có thể phát biểu thành:

Giả sử ban đầu n bạn học sinh đứng theo một thứ tự nhất định nào đó trên vòng tròn theo cùng kim đồng hồ. Tìm số lần đổi chỗ nhỏ nhất sao cho các học sinh vẫn đứng theo thứ tự đó trên vòng tròn nhưng ngược chiều kim đồng hồ.

Đánh số các học sinh này là 1, 2,3,...,n2,n1 theo chiều kim đồng hồ và ở trạng thái cuối, các học sinh cũng được đánh số như thế nhưng ngược chiều kim đồng hồ.

Ta thấy rằng với ba học sinh A B C đứng theo thứ tự đó thì khi đổi chỗ B và C, ta nhận , , được thứ tự mới là A C B . Ta có thể coi trong việc đổi chỗ đó, B đứng yên và C chuyển , , qua vị trí xen giữa A và B. Như thế, với bất kì dãy các cách đổi chỗ nào, ta luôn có thể chọn ra được ít nhất 1 học sinh đứng yên trong suốt quá trình đó, giả sử là học sinh được đánh số 1. Rõ ràng cũng không thể có trường hợp có ba học sinh A B C nào đó , , (không nhất thiết đứng cạnh nhau) đứng yên vì khi đó, các học sinh này sẽ xác định một chiều không đổi trong suốt quá trình đổi chỗ và như thế thì không thỏa mãn đề bài.

Ta sẽ chứng minh hai nhận xét sau:

Nhận xét 1.

Với n3, ta luôn có thể chọn hai học sinh đứng yên trong quá trình đổi chỗ và việc chọn này không ảnh hưởng đến số lần đổi chỗ nhỏ nhất. Điều này có nghĩa là nếu trong cách chọn hai học sinh này, có một cách đổi chỗ thỏa mãn đề bài cần x lần thì trong một cách chọn hai học sinh khác, cũng tồn tại một cách đổi chỗ với x lần như thế.

Thật vậy,

13 Ta cố định một học sinh A tại mọi thời điểm. Xét một cách chọn cặp học sinh với hai học sinh được chọn là A và B. Giả sử đoạn thẳng AB chia n2 học sinh còn lại thành 2 phần X Y₁, ₁, trong đó X₁ nằm trên cung tròn hướng từ B đến A, X₂ nằm trên cung còn lại. Giả sử X₁ a Y, ₁ b với a b n   2 1.

A

b

1

b

2

C B

a

1

a

2

Dễ thấy rằng các học sinh trong tập hợp X₁ phải di chuyển vượt qua dây AB để đi về phía đối diện với f₁ lần đổi chỗ và các học sinh X₂ phải di chuyển vượt qua dây AB về phía đối diện với f₂ lần đổi chỗ, tổng số lần đổi chỗ là f₁ f₂ lần.

Giả sử trong một cách di chuyển nào đó, ở tập hợp X₁, có a₁ học sinh di chuyển về phía A và b₁ học sinh di chuyển về phía B. Tương tự, trong tập hợp X₂, số học sinh di chuyển về phía A B lần lượt là , a b₂, .₂

Do n2 0 nên tồn tại học sinh thuộc một trong hai tập hợp X X₁, ₂; ta giả sử C nằm kề với B và thuộc về X₂.Khi đó, nếu chuyển hai học sinh cố định từ A B thành ,, A C thì hai tập hợp X Y₁, ₁ sẽ trở thành X Y₂, ₂ với X₂  X₁ 1,Y₂  Y₁ 1.

Ta sẽ chỉ ra một cách di chuyển tương ứng bằng với số cách di chuyển cần f₁ f₂ lần đổi chỗ như trên.

Ta sẽ giữ nguyên các học sinh di chuyển về phía A ở hai bên. Số học sinh di chuyển về phía ngược lại ở tập X₂ lúc này có thêm B hay b₂ b₂1, số học sinh di chuyển về phía ngược lại ở tập Y₂ lúc này mất đi C hay c₂ c₂1.

14 Ta vẫn cho các học sinh của tập X₂ di chuyển vượt qua C (thay vì chỉ vượt qua B như trước), mỗi học sinh tốn thêm một lần đổi chỗ nên tổng cộng mất thêm b₂1 lần. Tiếp theo, cho các học sinh của tập Y₂ di chuyển vượt qua C về phía bên kia. Các học sinh cũ cũng tốn các lần đổi chỗ giống như cũ (đều phải vượt qua tất cả học sinh từ tập X₂ mới chuyển qua), tuy nhiên, do chỉ còn c₂1 học sinh nên sẽ không bị tốn thêm b₂1 số lần đổi chỗ tương ứng.

Do đó, số lần đổi chỗ tăng lên và giảm đi một lượng như nhau nên chúng bằng nhau. Vì hai cách chọn học sinh B C kề nhau như thế đều có các số lần đổi chỗ tương ứng giống , nhau nên với hai cách chọn học sinh bất kì, các số lần đổi chỗ của chúng cũng sẽ tương ứng giống nhau. Nhận xét được chứng minh.

Nhận xét 2.

Nếu gọi f n là số lần chuyển chỗ nhỏ nhất trong trường hợp có ( ) n học sinh, ta có (3) 1, (4) 2, ( ) ( 2) 2, 5

f  f  f n  f n  n n . Thật vậy,

Nếu có 3 học sinh thì ta chỉ cần đổi chỗ một cặp học sinh và trong trường hợp có 4 học sinh thì đổi chỗ hai cặp kề nhau thì có cách sắp xếp thỏa mãn đề bài. Dễ dàng suy ra

(3) 1, (4) 2.

f  f 

Xét n5 tùy ý, với n2 học sinh, ta có số lần chuyển chỗ ít nhất là f n( 2). Ta thêm hai học sinh thứ n1 và n vào vòng tròn và theo nhận xét 1, ta có thể chọn hai học sinh này cố định. Các học sinh còn lại phải di chuyển vào giữa hai học sinh cố định này. Rõ ràng trong cách đổi chỗ nhỏ nhất đã thực hiện với n2 học sinh còn lại, nếu muốn chuyển chỗ cho n học sinh này thì các học sinh trước đó đều phải vượt qua thêm một trong hai học sinh cố định đã nêu và đòi hỏi cần thêm n2 lần đổi chỗ nữa bắt buộc nữa. Theo nhận xét 1 thì cách chuyển này vẫn là nhỏ nhất và đúng bằng f n , suy ra ( )

( ) ( 2) 2

f n  f n  n với n5.

Từ đó suy ra

(2 ) 2 4 6 ... 2 2 ( 1)

f k      k k k và f(2k1) 1 3 5 ... 2     k 1 k².

15 Ta sẽ chỉ ra một cách đổi chỗ thỏa mãn đề bài.

- Với n chẵn, đặt n2 ,k ta cố định học sinh 1 và n . Xét các học sinh 1, 2,... 1

2

n n n di chuyển về phía học sinh n lần lượt theo thứ tự đó ; các học sinh còn lại là 2, 3, 4,...,

2

n di chuyển về phía học sinh 1 lần lượt theo thứ tự đó để vào khoảng giữa hai học sinh này. Dễ thấy rằng: học sinh thứ i và n 1 i với

2, 3, 4,..., 2

i n đều cần số lần đổi chỗ là i1. Do đó, tổng số lần đổi chỗ của các học

sinh này là 2 1 2 3 ... 1 1 ( 1)

2 2 2

n n n

    k k

        

   

    .

- Với n lẻ, đặt n2k1, tương tự, ta cũng cố định học sinh 1 và n . Xét các học sinh 1, 2,..., ³

2

n n n

  di chuyển về phía học sinh n lần lượt theo thứ tự đó; các học sinh còn lại là 2, 3, 4,..., ¹

2 n

di chuyển về phía học sinh 1 lần lượt theo thứ tự đó để vào khoảng giữa hai học sinh này. Học sinh còn lại là ¹

2 n

có thể di chuyển theo hướng túy ý đến đúng vị trí của nó. Dễ thấy rằng: học sinh thứ i và n 1 i với

2, 3, 4,..., 1 2

i n

 đều cần số lần đổi chỗ là i1. Do đó, tổng số lần đổi chỗ của các học

sinh này là 3 1 3 1 1 ²

2 1 2 3 ...

2 2 2 2 2

n n n n n

           k

       

     

      .

Từ đây ta có thể kết luận rằng số lần đổi chỗ nhỏ nhất cần sử dụng là ( 2) 4 n n

  

 

 

(biểu thức này tương ứng bằng với các giá trị đã nêu trong từng trường hợp chẵn lẻ của n ).

Bài toán được giải quyết hoàn toàn.