Một số bài toán về Điểm nguyên và Lưới điểm ôn thi HSG Quốc gia môn Toán

(1)

1 MỘT SỐ BÀI TOÁN VỀ LƯỚI VÀ ĐIỂM NGUYÊN

Giáo viên: Nguyễn Hiếu Thảo Trường THPT chuyên Nguyễn Du – Tỉnh Đaklak.

Bài viết này là một bài tổng hợp về một số bài toán phương trình hàm, trong đó có sử dụng tính chất số học để tìm các tính chất hàm số, từ đó có các lời giải đẹp. Bài viết này chỉ là sự tập hợp các bài toán để các em học sinh luyện tập, có cái nhìn tương đối về các dạng bài tập này.

Mở đầu.

Trên mặt phẳng ta xét một lưới tạo bởi hai họ các đường thẳng song song chia mặt phẳng thành các hình bình hành bằng nhau gọi là một lưới.Tập hợp tất cả các đỉnh các hình bình hành gọi là lưới tọa độ, bản thân các đỉnh gọi là các nút của lưới. Mọi hình bình hành tạo bởi 2 họ đường thẳng song song gọi là hình bình hành cơ sở của phân hoạch hay hình bình hành sinh ra lưới.

Một hệ thống các đường thẳng dọc và các đường thẳng ngang chia mặt phẳng thành các ô vuông bằng nhau là một lưới.

Một lưới có thể nhận được từ các họ đường thẳng khác nhau; Lưới tọa độ nguyên chính là lưới tạo bởi tất cả các đường thẳng song song với hai trục tọa độ (hình bình hành cơ sở là hình vuông cạnh 1).

Bảng ô vuông là một hình chữ nhật được chia thành nhiều ô vuông đơn vị. Bảng ô vuông là một phần của lưới ô vuông.

Trong những năm gần đây, ở các kì thi chọn học sinh giỏi Toán thường có các bài toán tổ hợp và rời rạc. Trong các bài toán tổ hợp và rời rạc này, có các bài toán liên quan đến đến lưới và điểm nguyên. Lớp bài toán này khá phong phú về nội dung và đa dạng về hình thức thể hiện.

Phương pháp tiếp cận cho lớp bài toán này cũng khá phông phú như: tô màu, số học, đồ thị, phản chứng…

Trong bài viết này tôi xin giới thiệu một số bài toán liên quan đến lưới và điểm nguyên.

Bài viết này chỉ là sự tập hợp các bài toán để các em học sinh luyện tập, có cái nhìn tương đối về các dạng bài tập này.

Một số bài toán.

Bài toán 1. Mỗi ô của bảng vuông kích thước n n được ghi 0 hoặc số 1, sao cho với mỗi ô ghi số 0 thì có ít nhất n ô cùng hàng hoặc cùng cột với nó được ghi số 1. Chứng minh rằng có ít nhất

2

 n

   số 1 được ghi.

Lời giải.

Cách 1:

(2)

2 Với mỗi i1,n, kí hiệu d H( _i) là số số 1 ở hàng i, d C( )_i là số số 1 ở cột j.

Theo giả thiết, ta luôn có:

( _i) ( _j) d H d C n Từ đó suy ra

3

1 1

( ) ( )

n n

i j

T d H d C n

 

 





   Gọi S là tổng các số một được ghi,

1 1

( ) ( )

n n

i j

d H d C S

 

 

Với mỗi số 1 được ghi, nó được tính trong d H( _i) và d C( )_i . Do mỗi d H( _i) và d C( )_i trong T xuất hiện n lần nên T 2nS

Do vậy,

2

2 3

2 nSn  S n

Hay

2

2 S  n

  

 

Cách 2: Ta có thể tiếp cận bài toán bằng đồ thị.

Xây dựng một đồ thị hai phía gồm 2n đỉnh, mà n đỉnh bên trái là n hàng và n đỉnh bên phải là n cột của bảng. Đỉnh H_i được nối với đỉnh C_j nếu ô ( , )i j được ghi số 1.

Theo giả thiết nếu đỉnh H_i không nối với đỉnh C_j thì ( _i) ( _j)

d H d C n trong đó d H( _i) là số số 1 ở hàng i, d C( )_i là số số 1 ở cột j.

Khi n4, ta có một cách xây dựng như sau

1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1

Ta chứng minh số cạnh của đồ thị là

2

2 S  n . Thật vậy, ta có

 

* 2

( _i) ( _j)

T 



d H d C  n S n (Lấy hàng i, cột jcó ghi chữ số 0).

Trong tổng trên với mỗi i, số hạng d H( _i) xuất hiện n d H ( _i) lần; với mỗi j, số hạng d C( )_i xuất hiện n d C ( _j) lần.

Suy ra

(3)

3

 

* 2 2

1 1 1 1

( ) ( ) ( ) ( ) 2 ( ) ( )

n n n n

i i j j i j

i j i j

T d H n d H d C n d C nS d H d C

   

 





 



   







^.

(Vì

1 1

( ) ( )

n n

i j

d H d C S

 

 

^).

Theo bất đẳng thức Schwarz

2 2

2

1 1

( ) 1 ( )

n n

i i

d H d H e

n n

 

 

   

 

^, ² ²

1

( )

n

j j

d C e

 n



 ^. Suy ra

2 2

2 2 2 4 2

( ) 2 2 2 3 0

2

S n

n S n nS S n S n S n

   n        (đpcm).

Bài toán trên có thể thay giả thiết, mỗi ô có thể ghi bởi một số nguyên không âm tùy ý, thì cách giải vẫn không thay đổi.

Bài toán 2. Tồn tại hay không một đường gấp khúc khép kín gồm một số lẻ các đoạn thẳng có độ dài bằng nhau và bằng một số nguyên dương mà các đỉnh là các nút của một lưới ô vuông.

Lời giải.

Câu trả lời là không.

Thật vậy,

Giả sử tồn tịa đường gấp khúc A A₁ ₂...A A_n ₁ thỏa mãn yêu cầu (n lẻ), gồm các đoạn thẳng

1 i i

A A_ có độ dài c (clà số nguyên dương).

Xây dựng hệ tọa độ Oxy sao cho Ox,Oylà các đường lưới.

Trường hợp A A₁ ₂ nằm vuông góc với một trong hai trục Oxhoặc Oy. Không mất tổng quát, giả sử A A₁ ₂ nằm vuông góc với trục Ox. Vì các đoạn thẳng của đường gấp khúc là các đoạn thẳng bằng nhau và cùng bằng một số nguyên, đỉnh là điểm nút của lưới nên ta có nhận xét: Đoạn A A_i _i_₁ bất kì đều vuông góc với một trong hai trục Oxhoặc Oy.

Mặt khác, vì A A₁ ₂...A A_n ₁ là khép kín nên trên đường đi từ A₁ rồi trở về A₁ nếu đi sang phải bao nhiêu lần thì cũng đi sang trái bấy nhiêu lần, đi lên trên bao nhiêu lần thì cũng đi xuống dưới bấy nhiêu lần. Do đó số đoạn thẳng của đường gấp khúc A A₁ ₂...A A_n ₁ phải chia hết cho 4.

Điều này mâu thuẫn với giả thiết n là số lẻ.

(4)

4 Trường hợp A A₁ ₂ không vuông góc với một trong hai trục Oxvà Oy.

Ta xây dựng một lưới ô vuông mới với hình vuông cơ sở có cạnh song song với A A₁ ₂, vì cnguyên nên trên lưới mới này thì đường gấp khúc A A₁ ₂...A A_n ₁ thỏa mãn các điều kiện của trường hợp ta đã xét ở trên. Do vậy , trong trường hợp này ta cũng có kết quả mâu thuẫn với giã thiết n là số lẻ.

Vậy ta có đpcm.

Bài toán 3. Tìm số đường đi dọc theo cạnh lưới ô vuông từ đỉnh (0, 0) đến đỉnh ( , )n n , sao cho không vượt qua đường chéo chính yx và mỗi bước đi là sang phải hoặc lên trên.

Lời giải.

Ta gọi một đường đi từ đỉnh (0, 0) đến đỉnh ( , )n n theo hướng sang phải hoặc đi lên là đường đi tiến.

(n,n)

(0,0)

y = x+1

A

(-1,1)

(n,n)

(0,0)

(5)

5 Mỗi đường đi tiến gồm 2n bước, với n bước sang phải và n bước lên trên. Như vậy mỗi đường đi tiến là một cách chọn n bước sang phải trong số 2n bước. Do đó số đường đi tiến là C₂ⁿ_n.

Ta lại gọi một đường đi tiến không vượt qua đường chéo chính là một đường đi tốt, ngược lại là một đường đi không tốt. Ta sẽ tìm số đường đi không tốt.

Cho P là một đường đi không tốt. Khi đó P sẽ gặp đường thẳng y x 1 lần đầu tiên tại một điểm A. Lấy đối xứng đoạn đường của P từ điểm O đến điểm A qua đường thẳng

1

y x ta được một đoạn đường đi từ điểm ( 1,1) đến điểm A. Đoạn đường này cũng là một đường đi tiến. Kết hợp đoạn đường này với phần còn lại của P từ điểm A đến điểm ( , )n n ta được một đường đi tiến từ điểm ( 1,1) ^{đến điểm}( , )n n .

Ngược lại, cho Q là một đường đi tiến từ điểm ( 1, 1) đến điểm ( , )n n . Khi đó Q sẽ gặp đường thẳng y x 1 lần đầu tiên tại một điểm A. Lấy đối xứng đoạn đường của Q từ điểm ( 1,1) đến điểm A qua đường thẳng y x 1 ta được một đoạn đường đi từ điểm O đến điểm A. Đoạn đường này cũng là một đường đi tiến. Kết hợp đoạn đường này với phần còn lại của Q từ điểm A đến điểm ( , )n n ta được một đường đi tiến từ điểm O đến điểm ( , )n n . Đường đi này là một đường đi không tốt.

Như vậy số đường đi không tốt từ điểm O đến điểm ( , )n n đúng bằng số đường đi tiến từ điểm ( 1,1) đến điểm ( , )n n . Số đường đi này bằng C₂ⁿ_n^¹.

Suy ra số đường đi tốt từ điểm O đến điểm ( , )n n là

1

2 2 2

1 1

n n n

C C C

n

  

 ^.

Bài toán 4. (VMO-1992). Một bảng hình chữ nhật kẻ ô vuông có 1991 hàng và 1992 cột (nghĩa là bảng gồm 1991 1992 ô vuông). Kí hiệu ô vuông ở giao của hàng thứ m(kể từ trên xuống dưới) và cột thứn (kể từ trái sang phải) là



^{m n}^;



. Tô màu các ô của bảng theo cách sau:

lần thứ nhất tô ba ô

  

^{r s}^; ^, ^r^^1;^s^^{1 ,}

 

^r^^2;^s^¹



^{, với ,}^{r s}là hai số tự nhiên cho trước thỏa mãn 1 r 1989và 1 s 1991; từ lần thứ hai, mỗi lần tô đúng ba ô chưa có màu nằm cạnh nhau hoặc trong cùng một hàng hoặc trong cùng một cột. Hỏi bằng cách đó có thể tô màu được tất cả các ô vuông của bảng đã cho hay không?.

Lời giải.

Cách 1:

Ta ghi vào mỗi ô vuông một số tự nhiên theo quy tắc: Ở mỗi hàng, lần lượt ghi các số tự nhiên từ 1 đến 1992.

Lần tô thứ nhất, ba số được ghi vào ba ô

  

^{r s}^; ^, ^r^^1;^s^^{1 ,}

 

^r^^2;^s^¹



^là^{s s}^, ^^1,^s^¹

và chúng có tổng bằng 3s2(chia 3 dư 2).

Ở lần tô thứ hai, ba ô liên tiếp trên mỗi hàng là ba số tự nhiên liên tiếp, ba ô liên tiếp trên mỗi cột là ba số tự nhiên bằng nhau; mỗi lần tô là xóa đi 3 số có tổng chia hết cho 3.

Suy ra, nếu tô màu được hết tất cả các ô vuông của bảng đã cho thì tổng T của tất cả các số được ghi vào bảng phải là một số chia cho 3 dư 2.

(6)

6 Mặt khác, tổng T ¹⁹⁹¹   



1 2 ... 1992



1991 1993 996  chia hết cho 3, do vậy không thể tô màu được tất cả các ô vuông của bảng.

Cách 2:

Chia tất các ô vuông của bảng thành ba loại:

- Loại I: Gồm tất cả các ô

 

^{r s}^; ^mà



^r^^s



^^{0 mod3}

 

^.

- Loại II: Gồm tất cả các ô

 

^{r s}^; ^mà



^r^^s

 

^^{1 mod 3}



^.

- Loại III: Gồm tất cả các ô

 

^{r s}^; ^mà



^r^^s



^^{2 mod3}

 

^.

Do 1992 3nên ở mỗi hàng ta đều có số ô mỗi loại là bằng nhau nên ở toàn bảng số ô mỗi loại bằng nhau.

Kể từ lần tô thứ hai, trong mỗi lần tô màu, ta tô đúng một ô loại I, một ô loại II và một loại III (vì ba ô ở cùng một hàng hoặc cùng một cột mà lại đứng cạnh nhau).

Do vậy, nếu tô màu được hết tất cả các ô của bảng, thì ở lần tô thứ nhất ta phải tô đúng một ô loại I, một ô loại II, một ô loại III.

Tuy nhiên do ở lần đầu, tô ba ô

  

^{r s}^; ^, ^r^^1;^s^^{1 ,}

 

^r^^2;^s^¹



^{và ta có}



^r^^s

 

^ ^r^{   }¹

 

^s ¹

 

^r^²

 

^{ }^s ¹



nên ba ô tô ở lần đầu đều cùng thuộc một loại, hay không thể tô màu được tất cả các ô vuông của bảng.

Bài toán 5. (VMO-2003). Xét số nguyên ^{n n}



^¹



. Người ta muốn tô tất cả các số tự nhiên bởi hai màu xanh, đỏ sao cho các điều kiện sau được đồng thời thỏa mãn:

i) Một số được tô bởi một màu, và mỗi màu đều được dùng tô vô số số;

ii) Tổng của n số đôi một khác nhau cùng màu là số có cùng màu đó.

Hỏi có thể thực hiện được phép tô màu nói trên hay không, nếu:

1) n2002? 2) n2003? Lời giải.

1) Với n2002.

Câu trả lời là “không”.

Thật vậy,

(7)

7 Giả sử ngược lại, ta có thề tô tất cả các số tự nhiên bởi hai màu xanh, đỏ sao cho:

- Mỗi số được tô bởi một màu, và mỗi màu đều được dùng tô vô số số;

- Tổng của 2002 số đôi một khác nhau cùng màu là số có cùng màu đó.

Khi đó, do có vô số số được tô màu xanh và vô số số được tô màu đỏ nên:

- Tồn tại số a₁ mà a₁ được tô bởi màu xanh và số b₁ a₁ 1 được tô bởi màu đỏ;

- Tồn tại số b₂ b₁ mà b₂ được tô bởi màu đỏ và số a₂  b₂ 1 được tô bởi màu xanh;

- Tồn tại số a₃ a₂ mà a₃ được tô bởi màu xanh và số b₃ a₃1 được tô bởi màu đỏ;

…

….a b₁, ....₁

….a b₁, ,...., ,₁ b a₂ ₂,....

….a b₁, ,...., ,₁ b a₂ ₂,....,a b₃, ,....₃

…..

….a b₁, ,.., ,₁ b a₂ ₂,..,a b₃, ,...,₃ a₂₀₀₁,b₂₀₀₁,...,b₂₀₀₂,a₂₀₀₂

- Tồn tại số a₂₀₀₁ a₂₀₀₀ mà a₂₀₀₁ được tô bởi màu xanh và số b₂₀₀₁a₂₀₀₁1 được tô bởi màu đỏ;

- Tồn tại số b₂₀₀₂ b₂₀₀₁ mà b₂₀₀₂ được tô bởi màu đỏ và số được tô bởi màu xanh;

Do vậy, tồn tại 2002 số a a₁, ₂,...,a₂₀₀₁,a₂₀₀₂ đôi một khác nhau được tô bởi màu xanh; và 2002 số b b₁, ,...,₂ b₂₀₀₁,b₂₀₀₂ đôi một khác nhau được tô bởi màu đỏ.

Hay a a₁ a₂ ... a₂₀₀₂ được tô màu xanh.

1 2 ... 2002

b   b b b được tô màu đỏ.

Mặt khác, b₂_k_₁a₂_k_₁1,b₂_k a₂_k 1(với mọi k1, 2,...,1001) nên abdẫn đến a và b được tô cùng màu (mâu thuẫn). Từ đó, ta có điều phải chứng minh.

2) Với n2003.

Câu trả lời là có. Ta xét cách tô màu sau:

Tô tất cả số chẵn bởi màu xanh, tất cả các số lẻ bởi màu đỏ. Dễ thấy cách tô màu như vậy thỏa mãn tất cả các yêu cầu của bài toán.

Bài toán 6. (VMO-2006). Cho m n, là các số nguyên lớn hơn 3 và bảng ô vuông kích thước m n (bảng gồm m hàng và ncột). Cho phép đặt bi vào các ô vuông của bảng theo cách sau:

Mỗi lần đặt 4 viên bi vào 4 ô vuông con (mỗi ô 1 viên) mà 4 ô đó tạo thành một trong các hình dưới đây

(8)

8 Lời giải.

1) Nhận thấy rằng, bằng cách thực hiện hai lần phép đặt bi, ta có thể đặt vào một ô vuông con của bảng kích thước 4 2 một viên bi.

Có thể phân chia bảng 2004 2006 thành các bảng 4 2 (gồm 501 1003 bảng 4 2 ). Từ đó, bằng cách thực hiện hữu hạn lần phép đặt bi thỏa mãn đề bài và ta có thể đặt bi vào tất cả các ô vuông con của bảng 2004 2006 (mỗi ô vuông con có số bi bằng nhau và bằng 1).

2) Câu trả lời là “không”.

Ta chứng minh bằng phản chứng.

Thật vậy, giả sử ngược lại, sau một số hữu hạn lần thục hiện phép đặt bi của đề bài, ta đã đặt vào mỗi ô vuông con của bảng 2005 2006 là k viên bi (k ^*).

Tô màu tất cả các ô vuông con ở hàng lẻ của bảng bởi màu đen (các ô không tô màu được xem là màu trắng).

Khi đó, số ô màu đen bằng 1003 2006 , số ô màu trắng 1002 2006 .

Nhận thấy, mỗi lần đặt bi có đúng 2 viên bi vào các ô màu đen và 2 viên bi vào các ô màu trắng. Do đó, sau mỗi lần đặt bi, số bi trong các ô màu đen và số bi trong các ô màu trắng luôn bằng nhau.

Suy ra 1003 2006  k 1002 2006   k k 0, điều này vô lí. Vậy ta có đpcm.

Bài toán 7. (30/4-2019). Trong mặt phẳng tọa độ Oxy, cho 2019 điểm phân biệt, mỗi điểm có hoành độ và tung độ đều là các số nguyên không âm không vượt quá 800. Chứng minh rằng có thể tìm được 4 điểm tạo thành 4 đỉnh của một hình thang cân (hình chữ nhật được coi là hình thang cân).

Lời giải.

Để chứng minh có thể tìm được 4 điểm tạo thành 4 đỉnh của một hình thang cân ta chứng tỏ có 4 điểm



^{x k}ⁱ^;



^,



^{x k}^j^;



^,



^{x k}ⁱ^'^{; ' ,}

 

^x^j^'^{; '}^k



^mà^xⁱ^^x^j ^^xⁱ^'^^{x k}^j^'^, ^^k^'^.

Với mỗi, gọi nk



⁰nk ⁸⁰⁰



là số các điểm có tung độ k, ta có

800

0

k 2019

k

n





 ^.

Ta chứng minh kết quả sau, cho n số thực phân biệt x x₁, ₂,...,x_n, lúc đó tập hợp



i j ^|1



S  x x   i j n có ít nhất 2n3phần tử.

Thật vậy, không mất tổng quát giả sử x₁x₂  ... x_n, lúc đó

1 2 1 3 ... 1 _n 2 _n 3 _n ... _n 1 _n

x x     x x x x x x  x x   x _ x và ta có bộ n số thực y

O xi xi’ xj’ xj x

k’

k

(9)

9 phân biệt



^{1, 2,...,}ⁿ



^có^S ^{có đúng}²ⁿ^³^{phần tử.}

Từ đó suy ra Sn 



n ¹

 

n²



²n³.

Với mỗi ^k



⁰^{ }^k ⁿ



^{, gọi}nklà số các điểm có tung độ bằng k. Ta có

800

0

k 2019

k

n





 ^.

Với mỗi ^k



⁰^{ }^k ⁿ



^{, gọi}Sklà tập các tổng x_i x_jphân biệt được tạo ra, trong đó

i j

x  x là các hoành độ của các điểm có tung độ k, theo kết quả trên, ta có S_k 2n_k 3. Từ đó suy ra,

 

800 800 800

0 0 0

2 3 2 3 801 2 2019 3 801 1625

k k k

S n n

  

 

          

 

  

^.

Mặt khác, do các hoành độ không vượt quá 800 nên x_i x_j không vượt quá 1600, hay



0;1;2,...,1600



Sk  với mọi ^k



⁰^{ }^k ⁿ



. Suy ra, tồn tại x_i x_j x_i_'x_j_' (với , ' '

i j i  j )

Hay tồn tại 4 điểm



^{x k}ⁱ^;



^,



^{x k}^j^;



^,



^{x k}ⁱ^'^{; ' ,}

 

^x^j^'^{; '}^k



^mà^xⁱ ^^x^j ^ ^xⁱ^'^^{x k}^j^'^, ^^k^'. Điều này cho ta kết luận 4 điểm đó tạo thành một hình thang cân, có cạnh đáy song song với trục hoành.

Bài toán 8. (Đề Preselection, September Camp). Các số tự nhiên 0, 1, 2, 3,… được điền vào bảng ô vuông kích thước 2015 2015 (mỗi ô một số), bắt đầu từ số 0 ở chính giữa bảng, đến các số tiếp theo được điền theo hình xoắn ốc ngược chiều kim đồng hồ như hình vẽ bên dưới:

20 19 18 17 16

21 6 5 4 15

22 7 0 3 14

23 8 1 2 13

24 9 10 11 12

1) Biết rằng các cột của bảng được đánh số từ 0 đến 2015 từ trái sang phải và các dòng của bảng được đánh số từ 1 đến 2015 theo thứ từ trên xuống dưới. Hỏi theo cách điền trên thì số 2015 nằm ở dòng nào, cột nào?

2) Người ta cho phép thao tác sau: Đầu tiên, thay số 0 giữa bảng bằng số 14. Mỗi lần sau đó, người ta sẽ chọn ra 12 ô vuông liên tiếp thuộc cùng hàng, hoặc 12 ô vuông liên tiếp thuộc cùng cột, hoặc 12 ô vuông thuộc một bảng hình chữ nhật 3 4 rồi cộng thêm 1 vào tất cả các ô được chọn (mỗi lần chir được chọn 1 trong 3 loại trên). Hỏi sau một số hữu hạn lần, có thể làm cho tất cả các ô vuông của bảng đã cho đều chia hết cho 2016 được không?

Lời giải.

1) Ta có nhận xét sau:

i) Trong một bảng ô vuông kích thước lẻ



²ⁿ^{ }¹

 

²ⁿ^¹



và có tâm là ô chứa số 0; tất cả các giá trị từ 0 đến



²ⁿ^¹



²^¹ đều được điền vào các ô còn lại;



²ⁿ^¹



số có giá trị lớn nhất được điền vào cột đầu tiên tính từ trái sang (số lớn nhất



²ⁿ^¹



²^¹ được điền vào ô



²ⁿ^^1,1



(10)

10 cuối cột đó).

ii) Số 0 nằm ở hàng 1008 và cột 1008 của bảng 2015 2015 .

Do vậy, từ 201545² 2025 suy ra số 2015 thuộc vào bảng ô vuông 45 45 . Xét bảng 45 45 ,

Số lớn nhất trong bảng này là 45² 1 2024. Số 2024 thuộc cột 1 của bảng 45 45 và nó tương ứng thuộc cột 1008 22 986 của bảng 2015 2015

và thuộc dòng 1008 22 1030 của bảng 2015 2015 .

Mặt khác, 20152024 9 nên sô 2015 sẽ nằm ở dòng 1030 9 1021  . Vậy số 2015 nằm ở dòng 1021 và cột 986 của bảng.

2) Sau bước thay 0 bởi số 14, ta thấy tổng các số của bảng là:



2



2015²



2015² 1



14 1 2 3 ... 2015 1 14

2

         , giá trị này chia 4 dư 2 Thao tác cộng các số trong 12 ô (bất kể dòng nào, cột nào) của bảng thì tổng các số tăng lên đúng 12 đơn vị. Suy ra số dư của tổng các số trên bảng khi chia cho 4 là bất biến trong suốt quá trình.

Để bảng có tất cả các số chia hết cho 2016 thì tổng của chúng phải chia hết cho 4, đây là điều không thể xảy ra. Vậy câu trả lời là không thể.

Bài toán 9. (VOM-2016). Có m học sinh nữ và n học sinh nam (m n, 2) tham gia một liên hoan song ca. Tại liên hoan song ca, mỗi buổi biểu diễn một chương trình văn nghệ. Mỗi chương trình văn nghệ bao gồm một số bài hát song ca nam- nữ mà trong đó, mỗi đôi nam- nữ chỉ hát với nhau không quá một bài và mỗi học sinh đều được hát ít nhất một bài. Hai chương trình được coi là khác nhau nếu có một cặp nam- nữ hát với nhau ở chương trình này nhưng không hát với nhau ở chương trình kia. Liên hoan song ca chỉ kết thúc khi tất cả các chương trình khác nhau có thể có đều được biểu diễn, mỗi chương trình biểu diễn đúng một lần.

a) Một chương trình được gọi là lệ thuộc vào học sinh X nếu như hủy bỏ tất cả các bài song ca mà X tham gia thì có ít nhất một học sinh khác không được hát bài nào trong chương trình đó.

Chứng minh rằng trong tất cả các chương trình lệ thuộc vào X thì số chương trình có số lẻ bài hát bằng số chương trình có số chẵn bài hát.

b) Chứng minh rằng ban tổ chức liên hoan có thể sắp xếp các buổi biểu diễn sao cho số các bài hát tại hai buổi biểu diễn liên tiếp bất kỳ không cùng tính chẵn lẻ.

cột 1008 cột 1008-22

dòng 1008

dòng1008+22 22 dòng

(11)

11 Lời giải.

a) Ứng với mỗi chương trình văn nghệ, ta ghép cặp nam nữ song ca thành một bảng m n ⁽m hàng, n cột, các học sinh nữ được đánh số từ 1 đến m, các học sinh nam được đánh số từ 1 đến

n) như sau: Mỗi ô

 

^{i j}^, của bảng được đánh số 1 hoặc 0.

+ Số 1 nếu học sinh nữ thứ i và học sinh nam thứ j hát với nhau;

+ Số 0 nếu học sinh nữ thứ i và học sinh nam thứ j không hát với nhau;

0 1 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0

Một bảng được gọi là “tốt” nếu trên mỗi hàng và mỗi cột có ít nhất mốt số 1. Theo đề bài, tất cả các bảng biểu diễn cho chương trình đều là tốt ví học sinh ào cũng biểu diễn.

Xét một học sinh X nào đó, giả sử đó là học sinh nữ (trường hợp là học sinh nam chứng minh tương tự). Một chương trình nào đó lệ thuộc vào X nếu như trên bảng ứng với chương trình đó, tồn tại ít nhất một cột có đúng một số 1 nằm trên hàng của X, ta gọi bảng này lệ thuộc X và cột như thế là cột lệ thuộc X (như bảng minh họa 5 5 trên, chương trình đó lệ thuộc bạn nữ thứ

3).

Ta cần chứng minh, trong tất cả các bảng lệ thuộc X, số bảng có các số 1 chẵn bằng số bảng có số các số 1 lẻ.

Thật vậy,

Xét trường hợp trong bảng có kcột lệ thuộc vào X, khi đó k n (vì nếu k n thì tất cả các ô còn lại của bảng là số 0, dẫn đến tồn tại một hàng toàn số 0, mâu thuẫn).

Khi kn, ta bỏ k cột đó ra khỏi bảng đó, thì trên bảng sẽ mất đi đúng ksố 1. Mỗi ô trong hàng của X sẽ được điền số 0 hoặc số 1 tùy ý vì mỗi cột còn lại vẫn còn ít nhất một chữ số 1 không thuộc hàng cảu X. Do vậy, khi ta bỏ đi hàng của X thì ta vẫn được một bảng



^m^{ }¹

 

ⁿ^^k



tốt.

Suy ra, số bảng lệ thuộc X trong trường hợp này là 2^{n k}^ nhân với số lượng bảng tốt có kích thước



^m^{ }¹

 

ⁿ^^k



còn lại. Trong mỗi bảng đó, ta chọn một ô bất kìa của hàng X và thay đổi số từ 01, 10 thì sẽ thay đổi tinh chẵn lẻ của các số 1 trên bảng.

Do đó, tồn tại một song ánh đi từ tập hợp các bảng lệ thuộc X có các số 1 chẵn đến tập hợp các bảng lệ thuộc X có các số 1 lẻ.

Vậy ta có kết luận, số lượng hai bảng này là bằng nhau.

Ứng với mỗi k 1,n1 và các cách chọn k cột phụ thuộc X thì số lượng bảng có số 1 lẻ và chẵn đều bằng nhau, nên tổng số bảng có số các số 1 lẻ bằng với bảng có số các số 1 chẵn.

b) Ta đặt ^{f m n}



^,



^và^{g m n}



^,



lần lượt là số các bảng tốt m n có chẵn và lẻ số 1.

Xét một học sinh X tùy ý, không mất tổng quát giả sử đó là học sinh nữ. Ta có các trường hợp sau:

+ Nếu tồn tại một cột nào đó phụ thuộc X, theo câu trên, số bảng có số các số 1 lẻ bằng với bảng có số các số 1 chẵn, ta đặt giá trị này là ^{h m n}



^,



^.

(12)

12 + Nếu không tồn tại cột nào phụ thuộc X, ta bỏ hàng tương ứng của X đi, ta có một bảng



^m^{ }¹



ⁿ^tôt.

Mặt khác, số trường hợp mà hàng X có số lẻ và có số chẵn ô điền số 1 lần lượt là

1(mod 2) a n a

L C







^và

0(mod 2), 0 a n

a a

C C

 





⁽^a là số số 1 trên hàng của X) Vì ^C_n⁰^^C¹_n^^C_n²^{  }^...

 

¹ ⁿ^C_nⁿ ^⁰^nênC  L 1 0.

Vì tính chẵn lẻ của số các số 1 thuộc dòng X quyết định tính chẵn lẻ của bảng còn lại nên ta có công thức truy hồi sau

       

, , 1, 1,

f m n h m n L g m n C f m n g m n h m n L f m n C g m n

       



      



Do đó,

           

   

, , 1, 1,

1, 1,

f m n g m n L C g m n f m n g m n f m n

     

   

Dẫn đến,



^,

 

^,

  

¹ ^{m n} ⁴

  

^{2, 2}

 

^{2, 2}



f m n g m n   ^{ } f g . Ta có, khi



^{m n}^,

  

^ ^{2, 2}

1 1

1 1 , 1 0

0 1 , 0 1

1 0

0 1

1 1 , 1 0

1 1 , 1 1

1 0 , 1 1 0 1

Hay ^f

 

^{2, 2} ^^3,^g

 

^{2, 2} ^⁴, suy ra ^{f m n}



^,



^^{g m n}



^,

  

^{ }¹ ^{m n}^{ }³. Từ đó ta thấy rằng số lượng của hai loại bảng không vượt quá 1 và có thể sắp xếp các bảng theo thứ tự chẵn, lẻ đan xen thỏa mãn yêu cầu đầu bài. Ta có đpcm.

Bài toán 10. (VOM-2018). Một nhà đầu tư có hai mảnh đất hình chữ nhật, các mãnh đất dều có kích thước là 120m100m.

a) Trên mãnh đất thứ nhất, nhà đầu tư muốn xây dựng một ngôi nhà có nền hình chữ nhật kích thước 25m35m và xây bên ngoài 9 bồn hoa hình tròn đường kính 5m. Chứng minh rằng dù

xây trước 9 bồn hoa ở đâu thì trên phần đất còn lại vẫn đủ xây ngôi nhà đó.

b) Trên mảnh đất thứ hai, nhà đầu tư muốn xây dựng một hồ cá hình đa giác lồi sao cho từ một điểm bất kỳ trên phần đất còn lại có thể đi không quá 5m thì đến bờ hồ. Chứng minh rằng chu vi của hồ không nhỏ hơn



⁴⁴⁰^^{20 2}



^m^.

Lời giải.

a) Xét mảnh đất hình chữ nhật ABCD, để tiện lợi, ta không viết đơn vị độ dài, mặc định là

(13)

13 mét.

120, 100

ABCD ADBC  . Chia hình chữ nhật ABCD thành 10 hình chữ nhật nhỏ kích thước 30 40 như hình vẽ.

Xét 9 điểm là tâm của các giếng nước, theo nguyên lý Dirichlet, tồn tại một hình chữ nhật nhỏ không chứa tâm nào trong 9 tâm trên, giả sử đó là hình chũ nhật XYZT , với

40, 30

XY ZT  XT YZ  .

Xét hình chữ nhật X Y Z T' ' ' ' nằm bên trong XYZT có các cạnh song song với các cạnh của XYZT và cách một khoảng bằng 2.5, lúc này X Y Z T' ' ' ' có kích thước 25m35m. Rõ ràng khi xây nhà trên hình chữ nhật X Y Z T' ' ' ' sẽ thỏa mãn các yêu cầu. Ta có điều phải chứng minh.

b) Xét mảnh đất hình chữ nhật ABCD, ABCD120, AD BC100. Gọi Llà chu vi của hồ. Theo đề bài tồn tại các điểm ', ', ', 'A B C D thuộc L sao cho

', ', ', ' 5

AA BB CC DD  .

Vì chu vi hồ là một đa giác lồi nên các đường gấp khúc ' ', ' ', ' ', ' 'A B B C C D D A không chườm lên nhau. Do đó

' ' ' ' ' ' ' '

L  A BB C C DD A . Hạ A A' ₁ AD A A, ' ₂ AB

1 2

' , '

B B BC B B  AB

1 2

' , '

C C  BC C C CD

1 2

' , '

D D  AD D D CD Ta có,

1 ' ' ' ' 1 1 1 120

A AA BB B  A B  AB Tương tự, ta cũng có

2 ' ' ' ' 2 100

B B B C C C  ,

1 ' ' ' ' 1 120

C C C D D D  ,

2 ' ' ' ' 2 100

D D D AA A  . Từ đó suy ra

1 2 1 2

' ' ' ' ' ' ' ' ( ' ' ' '

' ' ' ' ) 440

A B B C C D D A A A A A B B B B C C C C D D D D

      

    

2.5

(14)

14 Áp dụng bất đẳng thức Cauchy- Schwarz, ta có



² ²



²

1 2 1 2

' ' 2 ' ' 2 ' 5 2

A A A A  A A A A  A A  .

Tương tự, B B' ₁B B' ₂ 5 2;C C' ₁C C' ₂ 5 2; D D' ₁D D' ₂ 5 2 Từ đây ta có kết luận, L 44020 2 (đpcm).

Bài tập.

Bài toán 11. (IMO-1997) Trong mặt phẳng các điểm với tọa độ nguyên là các đỉnh của các hình vuông đơn vị. Các hình vuông được tô màu đen, trắng (như trên bàn cờ vua). Với mỗi cặp số nguyên dương



^{m n}^,



xét một tam giác vuông mà các đỉnh có tọa độ nguyên, các cạnh bên chiều dài m và n, nằm dọc theo cạnh hình vuông. Ký hiệu S₁ là tổng diện tích phần màu đen của tam giác và S₂ là tổng diện tích phần màu trắng của tam giác. Đặt f m n



,



 S1S2 .

 

^a ^Tính ^{f m n}



^,



^{với mọi}^m^vàⁿ, nguyên dương cùng chẵn hoặc cùng lẻ.

 

^b Chứng minh rằng



^,



¹ ^ax

 

^,

f m n  2m m n với mọi m và n.

Bài toán 12. (Thi vô địch Moscow, 1961) Cho một bảng ô vuông có kích thước 4 4 . Chứng minh rằng có thể đặt 7 dấu ∗ vào các ô của bảng sao cho nếu xóa 2 hàng hoặc 2 cột bất kỳ của bảng thì vẫn có ít nhất 1 dấu ∗ chưa bị xóa. Chứng minh rằng nếu số dấu ∗ nhỏ hơn 7 thì luôn có thể xóa 2 hàng và 2 cột để mọi dấu ∗ đều bị xóa.

Bài toán 13. (Thi vào lớp chuyên Toán-Tin Hà Nội, Amsterdam, 1998) Cho hình vuông cạnh n (n là số nguyên lớn hơn 1) được chia thành n n ô vuông nhỏ. Trong mỗi ô vuông nhỏ này chỉ ghi một trong 3 số 1, 0, -1. Hình vuông như thế được gọi là "bảng số ô vuông cạnh

n^".

a) Hãy lập một bảng số vuông cạnh 6 sao cho tổng các số ghi trong bảng theo mọi hàng, mọi cột đều khác nhau.

b) Có hay không một bảng số cạnh n nào đó mà tổng các số ghi trong bảng theo mọi hàng, mọi cột và theo hai đường chéo đều khác nhau.

Bài toán 14. (Thi vào lớp chuyên Toán-Tin- Đại học tổng hợp tp HCM,1994) Cho bảng kích thước 2n2n ô vuông. Người ta đánh dấu vào 3n ô bất kỳ của bảng. Chứng minh rằng có thể chọn ra n^{hàng và}n cột của bảng sao cho các ô được đánh dấu đều nằm trên n hàng hoặc

n^{cột này.}

Bài toán 15. (IMO-1999) Xét một bảng n n ô vuông, n là số tự nhiên cố định. bảng được chia thành n² ô vuông đơn vị. Ta nói rằng 2 ô vuông khác nhau trên bảng là "liền kề" nếu chúng có một cạnh chung. Biết rằng N ô vuông đơn vị trên bảng được đánh dấu theo cùng một cách sao cho mọi ô vuông (đánh dấu hay không đánh dấu) trên bảng đã "liền kề" thì ít nhất có một ô vuông được đánh dấu. Xác định giá trị nhỏ nhất có thể có của N.

Bài toán 16. (IMO-1996) Cho số dương r và một bảng hình chữ nhật ABCDvới 20, 12

AB BC , BC=12. Hình chữ nhật được chia thành 20 12 ô vuông. Xét phép dịch chuyển sau: Dịch chuyển từ ô vuông này sang ô vuông kia chỉ được thực hiện nếu khoảng cách giữa hai tâm ô vuông bằng r. Nhiệm vụ đặt ra là tìm một dãy các phép dịch chuyển đi từ ô vuông có A là đỉnh đến ô vuông có B là đỉnh.

a. Chứng minh rằng nhiệm vụ là bất khả thi nếu r chia hết cho 2 hoặc chia hết cho 3.

b. Chứng minh rằng nhiệm vụ là khả thi nếu r73. c. Nhiệm vụ có thực hiện được không nếu r 97?

(15)

15 Bài toán 17. (IMO-2002) Giả sử n là một số nguyên dương. Một điểm

 

^{x y}^, trong mặt phẳng với x y, là các số nguyên, không âm, x y n, được tô màu đỏ hoặc trắng thỏa mãn điều kiện:

Nếu một điểm

 

^{x y}^, có màu đỏ thì tất cả các điểm



^{x y}^{', '}



^mà^x^'^^{x y}^{, '}^ ^y cũng có màu đỏ.

Gọi A là số các cách chọn n điểm màu trắng với tọa độ thứ nhất phân biệt và B là số cách chọn n điểm màu trắng với tọa độ thứ hai phân biệt. Chứng minh rằng AB.

Bài toán 18. (VMO-2017) Cho số nguyên n 1. Bảng ô vuông ABCD kích thước n n gồm n2 ô vuông đơn vị, mỗi ô vuông đơn vị được tô bởi một trong ba màu: đen, trắng, xám. Một cách tô màu được gọi là đối xứng nếu mỗi ô có tâm trên đường chéo AC được tô màu xám và mỗi cặp ô đối xứng qua AC được tô cùng màu đen hoặc cùng màu trằng. Người ta điền vào mỗi ô xám số 0, mỗi ô trắng một số nguyên dương và mỗi ô đen một số nguyên âm. Một cách điền số như vậy gọi là k-cân đối (với k nguyên dương) nếu thỏa mãn điều kiện sau:

)

i Mỗi cặp ô đối xứng qua AC được điền cùng một số nguyên thuộc đoạn



^^{k k}^,



^.

)

ii Nếu một hàng và một cột giao nhau tại ô đen thì tập các số nguyên dương được điền trên hàng đó và tập các số nguyên dương được điền trên cột đó không giao nhau; nếu một hàng và một cột giao nhau tại ô trắng thì tập các số nguyên âm được điền trên hàng đó và tập các số nguyên âm được điền trên cột đó không giao nhau.

a) Với n5, tìm giá trị nhỏ nhất của kđể tồn tại cách điền số k - cân đối cho cách tô màu đối xứng ở hình bên dưới.

b) Với n2017, tìm giá trị nhỏ nhất của k để với mọi cách tô màu đối xứng, luôn tồn tại cách điền số k-cân đối.

Bài toán 19. Cho bảng vuông kích thước 2012 2012 . Người ta ghi vào mỗi ô ( , )i j (i j, 1, 2, , 2012) một số tự nhiên a_ij thỏa các điều kiện :

(1) a_i₁a_i₂ a_i₂₀₁₂ 2011, với i1, 2, , 2012; (2) nếu a a_ij _kl 0 thì (ki l)(  j)0.

Hỏi có bao nhiêu cách ghi như vậy ?

Bài toán 20. Cho bàn cờ kích thước 2011 2012 . Bỏ bớt hai ô khác màu tùy ý. Hãy xếp đầy bàn cờ còn lại bằng các đôminô kích thước 1 2 , sao cho các đôminô đó không chờm lên nhau (có thể xoay các đôminô).

Tài liệu tham khảo:

1. Hình học tổ hợp – Vũ Hữu Bình.

2. Các phương pháp giải toán qua các kỳ thi Olympic- Trần Nam Dũng.

3. Tạp chí Toán học và tuổi trẻ.

4. Các bài thi Olympic toán trung học phổ thông Việt Nam- Tủ sách Toán học và tuổi trẻ.

5. Graph và giải toán phổ thông- Hoàng Chúng.