ĐẠI HỌC THÁI NGUYÊN
ĐẠI HỌC KHOA HỌC
PHẠM XUÂN ĐẠO TOÁN TRÒ CHƠI : PHÂN LOẠI, CÔNG CỤ VÀ
PHƯƠNG PHÁP GIẢI
CHUYÊN NGÀNH: PHƯƠNG PHÁP TOÁN SƠ CẤP

2013 1
MỤC LỤC
MỞ ĐẦU 2
Chương 1 Trò chơi một người 4

trình bày nội dung lí thuyết, các ví dụ và bài tập về trò chơi gần với và có thể áp
dụng được trong giảng dạy toán ở trường phổ thông.
Toán trò chơi liên quan mật thiết với nhiều dạng toán khác (toán tập hợp, toán
tổ hợp, đồ thị, lôgic toán, giải trí toán học và đố vui,…). Nhiều bài toán có thể
phát biểu lại dưới ngôn ngữ trò chơi. Ngược lại, một số bài toán trò chơi cũng có
thể được phát biểu dưới dạng khác.
Luận văn cố gắng trình bày một cách có hệ thống những nội dung cơ bản nhất
về Toán trò chơi. Các công cụ và phương pháp giải toán được trình bày ở đây là:
Phương pháp đại lượng bất biến hoặc đơn biến, nguyên lý cực hạn, lý thuyết đồ
thị và công cụ hệ đếm cơ số 2, Việc phân loại Toán trò chơi cũng như trình bày
các công cụ và phương pháp giải toán trò chơi dựa vào nội dung bài giảng [5] của
Thầy hướng dẫn. Chúng tôi cố gắng bổ sung thêm một số công cụ và phương
pháp giải so với [5].
Một công cụ, một phương pháp có thể sử dụng để giải nhiều bài toán. Ngược
lại, một bài toán có thể được giải bằng các công cụ và phương pháp khác nhau. 3
Vì vậy, việc phân loại các dạng toán trò chơi cũng như phương pháp giải chúng
chỉ mang tính ước lệ, nhằm phần nào hệ thống hóa và phân loại các bài toán trò
chơi, giúp học sinh dễ hiểu, dễ học hơn. Chúng tôi cũng đã cố gắng sưu tầm
nhiều bài tập toán trò chơi trong các kì thi Olympic toán Quốc gia và Quốc tế, với
hi vọng luận văn có thể được sử dụng như một tài liệu tham khảo tốt trong giảng
dạy toán ở trường phổ thông.
Ngoài phần mở đầu, kết luận và tài liệu tham khảo, luận văn gồm ba chương.
Chương 1 Trò chơi một người
Chương 2 Trò chơi nhiều người và Trò chơi với hệ động lực
Chương 3 Các bài toán thi Olympic toán trò chơi
Luận văn được hoàn thành tại Khoa Toán - Tin, Đại học Khoa học, Đại học
Thái Nguyên dưới sự hướng dẫn của PGS.TS. Tạ Duy Phượng. Nhân dịp này, tôi

lớp các bài toán giải trí toán học, các bài toán lôgic,
1.1 Phương pháp đại lượng bất biến hoặc đơn biến
Bất biến có mặt trong hầu hết các lĩnh vực của Toán học. Bất biến là một khái
niệm thường gặp trong toán phổ thông. Thí dụ, bất biến là tính chẵn lẻ, tính chia
hết cho 3, tính đối xứng, sự bảo toàn góc,… tức là những điều thường gặp trong
toán phổ thông và khá dễ hiểu. Tuy nhiên, bất biến cũng vẫn còn là khái niệm
mới đối với học sinh phổ thông. Bởi vậy, việc trang bị khái niệm và hướng dẫn
học sinh sử dụng bất biến trong giải toán, theo chúng tôi, là việc làm có ý nghĩa
và cần thiết giúp phát triển tư duy toán học, nhìn thấy cái tĩnh trong cái động, mở
rộng kiến thức và kĩ thuật giải toán cho học sinh. 5
Bất biến là những đại lượng (hay tính chất) không thay đổi trong quá trình
chúng ta thực hiện các phép biến đổi. Đại lượng bất biến nhiều khi còn phụ thuộc
vào nội dung của bài toán cụ thể. Thí dụ, khoảng cách giữa hai điểm là một đại
lượng bất biến trong phép tịnh tiến, nhưng là đại lượng thay đổi trong phép vị tự;
tỷ lệ giữa độ dài hai đoạn thẳng vừa là đại lượng bất biến trong phép tịnh tiến,
vừa là một đại lượng bất biến trong phép vị tự.
Giả sử trò chơi ở một trạng thái ban đầu. Do tính bất biến, nên không thể thay
đổi trạng thái (từ chẵn thành lẻ, từ trắng thành đen,…) được. Từ đó ta có kết luận
về trạng thái cuối cùng của trò chơi.
Đơn biến là một đại lượng luôn thay đổi, nhưng chỉ theo một chiều tức là tăng
lên hay giảm xuống (đơn điệu).
Bất biến và đơn biến được sử dụng để giải quyết nhiều bài toán, dạng toán
khác nhau (Dĩ bất biến ứng vạn biến!).
Trong mục này, chúng ta sẽ tìm hiểu về bất biến, đơn biến và ứng dụng của
chúng trong việc giải các bài toán trò chơi toán học, chủ yếu là qua các ví dụ.
Có hai mẫu bài toán thường được giải quyết bằng bất biến và đơn biến.
Bài toán 1 Có một tập hợp các trạng thái


bất kỳ, sau một số
hữu hạn các phép biến đổi T, ta sẽ đi đến trạng thái kết thúc

(trong nhiều
trường hợp, đó là trạng thái ổn định, bất động, tức là sẽ không tiếp tục thay đổi
khi tiếp tục tác động các phép biến đổi từ
T
). Tương tự, trong một số bài toán, ta 6
phải chứng minh không tồn tại dãy biến đổi (liên tiếp) từ T để thực hiện được
mục đích chuyển trạng thái α sang trạng thái
.


Bất biến hoặc đơn biến nhiều khi ẩn tàng, khó nhận biết. Vì vậy sử dụng bất
biến hoặc đơn biến trong giải toán thực chất là quá trình phân tích và phát hiện
qui luật bất biến hoặc đơn biến.
1.1.1 Sử dụng bất biến trong giải toán trò chơi
Bài 1.1 Một bảng vuông
44
ô. Tại mỗi ô của bảng vuông (Hình
1.1
) có chứa
dấu
“”
hoặc dấu
“ ”.

+
+
+
+
+


+
+
+
+


Thí dụ, hàng (cột) đang có
0, 2, 4
dấu trừ, thì sau đó sẽ có
4, 2, 0
dấu trừ (số
dấu trừ là chẵn), nếu hàng (cột) đang có
1
(hoặc
3
) dấu trừ thì sau đó sẽ có
3

(hoặc
1
) dấu trừ. Vì vậy, cho dù ta thực hiện bao nhiêu lần, tính chẵn lẻ của số
dấu trừ trong một hàng (một cột) là một đại lượng không thay đổi (bất biến). Kéo
theo tích tất cả các số trong hình vuông luôn không đổi (luôn bằng

quân trắng và
32
quân đen, mỗi quân chiếm một
ô vuông. Tại mỗi bước đi người chơi thay tất cả các quân trắng thành quân đen và
tất cả các quân đen thành quân trắng trên một hàng hoặc một cột nào đó. Hỏi sau
hữu hạn bước, có thể còn lại chính xác một quân đen trên bàn cờ không?
Giải Nếu trước khi chuyển có chính xác
k
quân đen trên hàng (cột) định chuyển
thì số quân trắng trên hàng (cột) ấy là
8.k
Sau khi chuyển,
8 k
quân trắng này
trở thành
8 k
quân đen và
k
quân đen lại trở thành
k
quân trắng. Như vậy, số
quân đen trên bàn cờ sau khi chuyển sẽ thêm vào
8 k
và mất đi
k
quân, tức là
số quân đen thay đổi trên bàn cờ là
 
8 8 2 .k k k   
Số này là số chẵn dương

tách.
Giải Nếu có
1999
chiếc tách (số tách là số lẻ), tất cả đều được đặt ngửa (trạng
thái ngửa) thì ta không thể quay úp xuống tất cả (trạng thái úp) được. Thật vậy,
theo qui tắc chơi, tại mỗi thời điểm, giả sử có
k
tách đặt ngửa được làm úp
xuống thì
100 k
tách đang úp được lật ngửa lên. Khi ấy số các tách úp đã tăng 8
lên
k
chiếc và giảm đi
100 ,k
vậy số tách úp bị thay đổi đi một số chẵn là
 
100 100 2k k k   
(nếu
50k 
thì số tách úp giảm đi, nếu
50k 
thì số
tách úp tăng lên,
50k 
thì số tách úp không thay đổi). Nghĩa là tính chẵn lẻ của
số các tách úp không thay đổi (bất biến!). Nhưng lúc đầu số tách úp ở trạng thái

lần này, thực chất chỉ có tách số
1
và số
2
bị úp, các tách khác không thay đổi
(vẫn đặt ngửa sau khi lật úp rồi lại lật ngửa). Tiếp tục như vậy, sau
18 198 216
lần, tất cả các tách đều bị lật úp.
Bài 1.4 Một học sinh viết lên bảng
ab
số gồm
a
số 0 và
b
số
1
và thực hiện
phép biến đổi sau: xóa hai số bất kì trên bảng. Nếu chúng bằng nhau thì viết số
0

lên bảng, nếu chúng khác nhau thì viết số
1.
Hỏi khi nào số còn lại trên bảng là số
1
và khi nào số còn lại trên bảng là số
0?

Giải Sau một lần thực hiện biến đổi, tính chẵn lẻ của tổng các số trên bảng là
không đổi (bất biến!). Thật vậy, nếu hai số bị xóa cùng bằng
0

Nhận xét Nhiều bài toán phát biểu có thể khá gần hoặc rất khác nhau, nhưng
thực chất lời giải chỉ là một. Điều quan trọng là ta phải tìm ra tính bất biến trong
các bài toán đó.
Qui luật bất biến nhiều khi ẩn sâu trong bài toán đến mức khó nhận ra. Ví dụ thú
vị dưới đây minh họa điều đó.
Bài 1.5 (Thi Olympic
30.4
lần thứ
8, 2007,
lớp
10,
Trường Trung học Phổ thông
Chuyên Lê Hồng Phong Thành phố Hồ Chí Minh đề nghị) Với một tam thức bậc
hai, cho phép thực hiện một trong hai phép toán sau:
1) Hoán vị hệ số của
2
x
và số hạng tự do.
2) Thay
x
bằng
xm
với
m
là số thực tùy ý.
Hỏi có thể nhận được tam thức bậc hai
2
30 4 1975xx
từ tam thức
2

Như vậy, sau cả hai phép biến đổi,
2
4
P
b ac  
là một đại lượng bất biến.
Suy ra, nếu có một qui trình thực hiện liên tiếp hai phép toán đã cho, để có thể
nhận được tam thức
2
( ): 30 4 1975Q x x x  
từ tam thức
2
( ): 5 2007R x x x  

thì
.
QR
  

Nhưng ta có
2
5 4.( 2007) 8053,
Q
    
còn
2
4 4.30( 1975) 237016.
R
    


hạn phần tử nhưng tồn tại một phần tử lớn nhất hoặc nhỏ nhất (Nguyên lí 2).
Bài 1.6 (Vô địch Kiev,
1974
) Các số
1,2, ,1974
được viết trên bảng. Người chơi
được phép thay hai số bất kì bởi một số khác bằng tổng hoặc bằng hiệu của các
số đó. Hãy chỉ ra rằng, sau
1973
lần thực hiện phép toán đó, số còn lại trên bảng
không thể bằng
0.

Giải Lúc đầu trên bảng có tất cả
1974:2 987
số lẻ. Mỗi lần thay đổi, số các số
lẻ hoặc giữ nguyên (khi hai số được chọn cùng chẵn thì tổng và hiệu của chúng 11
cũng là số chẵn; khi hai số được chọn có một số chẵn và một số lẻ thì tổng và
hiệu của chúng là lẻ) hoặc số các số lẻ giảm đi
2
(khi chọn cả hai số cùng lẻ thì
tổng hoặc hiệu của chúng là chẵn). Do đó số các số lẻ còn lại trên bảng sau mỗi
lần thực hiện vẫn luôn luôn là lẻ (bất biến!). Vì mỗi lần chơi ta thay hai số bằng
một số nên sau mỗi lần chơi số lượng các số giảm đi một đơn vị (đơn biến!). Vậy
sau
1973
lần thực hiện phép chơi, ta được số cuối cùng còn lại phải là số lẻ, tức

12
hạn giá trị. Phương pháp tụt vô hạn cũng được dùng để giải quyết nhiều dạng
toán khác (thí dụ, trong giải phương trình nghiệm nguyên, ).
Bài 1.8 Trên một đường tròn ta đặt
n
số. Nếu thứ tự các số
, , , a b c d
thỏa mãn
  
0,a d b c  
thì hai số
b
và
c
đổi chỗ cho nhau. Chứng minh rằng sau một
số các bước thì trên đường tròn không còn bộ tứ nào sắp xếp như vậy.
Giải Thực chất là ta chỉ đổi chỗ hai số trên đường tròn, còn các số khác vẫn giữ
nguyên. Ta phải tìm đại lượng bất biến có liên quan đến sự thay đổi hai số này.
Giả sử bốn số
, , , a b c d
được sắp xếp theo thứ tự sao cho
  
0,a d b c  

nghĩa là
.ab cd ac bd  
Nếu thực hiện phép biến đổi đã cho thì bộ tứ
, , , a b c d
chuyển thành bộ tứ
a, c, b, d

()
trên bảng là bất biến. Ban đầu số
dấu
()
là số lẻ nên cuối cùng còn lại trên bảng là dấu
()
. 13
Cách giải 2 Thay mỗi dấu
 

bởi số
1
, thay mỗi dấu
()
bởi số
( 1)
. Khi đó mỗi
lần thực hiện cách làm theo đề bài có thể mô tả dưới dạng khác như sau: Hai số
bất kì được xóa đi và thay bằng tích của chúng. Vì vậy tại mọi thời đểm thực hiện
các phép toán thì tích của tất cả các số trên bảng là bất biến. Ban đầu tích của các
số trên bảng là
( 1)
nên cuối cùng tích của các số trên bảng cũng là
( 1)
. Vậy dấu
còn lại trên bảng là dấu
()

Ta chỉ ra rằng
S
tăng với mỗi người được chuyển đi.
Thật vậy, giả sử có một người đi từ phòng có
n
người tới phòng có
m
người, mà
mn
. Khi đó bình phương của số người trong các phòng biến đổi từ
2
n
và
2
m

thành
 
2
1n 
và
 
2
1m 
tương ứng, và các phòng khác thì không đổi. Như vậy,
S
thay đổi như sau:
   
 
     

mọi người đều trong một phòng.
Bài 1.11 (Vô địch toàn liên bang Nga lần thứ nhất,
1961
) Các số thực được viết
vào các ô trong một bảng chữ nhật
mn
. Mỗi lần chơi ta có thể đổi dấu tất cả
các phần tử trong một hàng hoặc một cột. Hãy chứng minh rằng sau một số lần,
ta có thể làm cho tổng của các số trong mỗi hàng và mỗi cột là không âm.
Giải Giả sử
S
là tổng của tất cả
mn
số trong bảng. Nhận xét rằng sau một lần
thực hiện, mỗi số được giữ nguyên hoặc đổi dấu. Như vậy có tất cả tối đa
2
mn

bảng và
S
chỉ có thể nhận hữu hạn
2
mn
giá trị (thực ra số khả năng có thể thực
hiện đổi dấu một lần tất cả các số trong một hàng hoặc một cột còn nhỏ hơn, số
này chỉ là
1
2
mn
).

dấu (hàng và cột) để được bảng có tất cả các hàng và các cột có tổng không âm.
1.2 Kĩ thuật đồng dư
Trò chơi thường gắn với tập số nguyên. Do vậy khá nhiều bài toán trò chơi có
thể giải được nhờ kĩ thuật lấy đồng dư (lấy môđulô). Kĩ thuật lấy đồng dư cũng
thường gặp trong nhiều dạng bài toán khác (toán trên tập số nguyên, giải phương
trình nghiệm nguyên). Kĩ thuật đồng dư trong Toán trò chơi thường là: Một đại
lượng nào đó thay đổi nhưng luôn đồng dư với một đại lượng khác. Tức là có qui
luật bất biến.
Bài 1.12 Ba đống bi tương ứng có
19, 8
và
9
viên. Được phép chọn hai đống bi
bất kì và chuyển một viên bi từ mỗi đống bi đã chọn vào đống thứ ba. Sau một số
lần làm như vậy, có thể đạt được mỗi đống bi có
12
viên không?
Giải Gọi trạng thái (số bi) tại bước thứ
k
trong ba đống tương ứng là
, , .
k k k
a b c

Xét môđulô các số này theo
3.
Lúc đầu
 
0
19 1 mod3a 

9 1 9 2 2 mod3   

nên số bi trong ba đống khi chia cho 3 sẽ là
 
1
0 mod3a 
,
 
1
1 mod3b 
và
 
1
2 mod3 ,c 
không phụ thuộc vào việc thêm (hai) hay bớt (một) viên bi vào
đống nào. Sau lần chuyển thứ hai ta lại có số dư theo
 
mod3
trong ba đống bi là
1
2,r 

2
0,r 

3
1r 
vì
     
11

 
0,0,0
làm
cho mỗi đống bi có
12
viên được.
Bài 1.13 (Vô địch Bungaria,
1999,
lớp
8
) Ba đống sỏi có
51, 49
và
5
viên. Ta thực
hiện một trong hai nước đi như sau. Một nước đi là dồn hai đống tùy ý thành một
đống. Nước đi khác là chọn đống có số chẵn viên sỏi để chia làm hai đống bằng
nhau. Hỏi có thể thực hiện một dãy các nước đi như thế để chia ba đống sỏi thành
105
đống mà mỗi đống chỉ có một viên sỏi hay không?
Giải Ban đầu số sỏi trong ba đống là
51, 49
và
5
viên đều là số lẻ nên cách duy
nhất thực hiện bước đi đầu tiên là phải dồn hai đống lại.
Trường hợp 1 Bước đầu tiên dồn hai đống có
5
và
51

       
   
   
 
15
5,49,51 56,49 28,28,49 14,14,14,14,49
7,7,7,7,7,7,7,7,49 56,7,7,7,7,7,7,7
28,28,7,7,7,7,7,7,7 14,14,14,14,7,7,7,7,7,7,7
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7 .
  



17
Trường hợp 2 Dồn hai đống có
5
và
49
viên, ta được hai đống có
51
và
54
viên,
mỗi đống đều là bội của
3.
Do đó bước thứ hai ta phải chia đống có
54

sỏi cùng chia hết cho
3.
Tức là, khi thực hiện các nước đi luân phiên, số sỏi trong
mỗi đống luôn là bội của
3
(bất biến!). Thật vậy, khi gộp hai đống sỏi cùng chia
hết cho 3 thì được một đống có số sỏi chia hết cho
3
và nếu chia một đống sỏi (là
gộp của hai đống có số sỏi lẻ cùng chia hết cho
3
) có số chẵn viên sỏi chia hết
cho
3
thành hai phần bằng nhau thì số sỏi trong mỗi phần vẫn chia hết cho
3.
Do
đó số sỏi trong mỗi đống luôn chia hết cho
3
và nhiều nhất có thể được là
35

đống, mỗi đống
3
viên.
Dưới đây là qui trình minh họa thuật toán trong Trường hợp 2:
         
         
     
     

.

Trường hợp 3 Bước đầu tiên dồn hai đống có
49
và
51
viên, ta được hai đống là
5
và
100
viên, số sỏi trong mỗi đống đều là bội của
5.
Khi thực hiện một trong
hai nước đi, số sỏi trong mỗi đống nhận được luôn là bội của
5.
Do đó số đống 18
với số sỏi nhỏ nhất là
21
đống, mỗi đống
5
viên. Chiến lược dưới đây minh họa
Trường hợp
3:

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

1.3 Công cụ hệ đếm cơ số 2
Cho
p
là một số tự nhiên bất kì. Theo thuật toán chia Euclid, mọi số tự nhiên
a
đều có thể biểu diễn duy nhất dưới dạng
1 1 0
1 1 0

nn
nn
a a p a p a p a p


    

với các hệ số nguyên
0 1, 1, , ; 0.
in
a p i n a    

Nếu chọn
p
làm cơ số của hệ đếm, thì mọi số tự nhiên
a
có thể biểu diễn
dưới dạng
 
1 2 0


) ở vị trí khác nhau có giá trị khác nhau (hàng
“đơn vị”, “hàng chục”, “hàng trăm”, ).
Hệ đếm cơ số
2
có ứng dụng to lớn trong công nghệ thông tin, được sử dụng
rộng rãi trong các ngành khoa học an ninh, quốc phòng. Bằng cách chia cho
2,

một số tự nhiên bất kì đều có thể biểu diễn dưới dạng tổng các lũy thừa của
2
với
các hệ số bằng
1
hoặc bằng
0.

Thí dụ, 2013 = 2
10
+ 2
9
+ 2
8
+ 2
7
+ 2
6
+ 2
4
+ 2
3

đến
2013.
Tôi sẽ hỏi
bạn
11
câu hỏi, bạn có quyền trả lời “đúng” hoặc “sai”. Dựa trên
11
câu trả lời
của bạn, tôi sẽ khẳng định được bạn đã chọn số nào. Tại sao?
Giải Các câu hỏi lần lượt như sau.
Câu thứ nhất: Lấy số đã chọn chia cho
2.
Hỏi phép chia có dư hay không?
Nếu bạn trả lời là “không” thì tôi viết số
0,
còn nếu câu trả lời là “có” thì tôi viết
chữ số
1.

Câu thứ hai: Lấy thương của phép chia vừa rồi chia cho 2. Hỏi phép chia có dư
hay không? 20
Nếu câu trả lời là “không” thì tôi viết số
0,
còn nếu câu trả lời là “có” thì tôi viết
chữ số 1 vào phía trước (về bên trái) số đã viết (chữ số
0
hoặc chữ số

cơ số
2.
Hơn nữa,
11
câu hỏi là đủ, bởi vì mọi số từ
0
đến
2013
đều có thể viết
được dưới dạng một số trong hệ đếm cơ số
2
với không quá
11
chữ
số
11
2
(2 2048 100000000000 ).
Mặt khác,
10
câu hỏi là không đủ, vì
10
2 1024 2013.
Vì số ban đầu chưa biết nên bây giờ chỉ cần chuyển số nhận
được trong hệ đếm cơ số 2 sang hệ đếm cơ số 10, ta khôi phục được số ban đầu.
Thí dụ, sau
11
lần trả lời, ta nhận được số
 
2



20 2 1 2 1 2 2 1 2 1 2 1           
21
 
 
 
 




 
 
 
 




 
 
 
 
 






       

Bài 1.15 Bạn muốn biết số điện thoại của tôi nên hỏi tôi một số câu hỏi, nhưng
với mỗi câu hỏi của bạn, tôi sẽ chỉ trả lời „„đúng‟‟ hoặc „„sai‟‟. Bạn hãy tìm ra
phương pháp để sau một số nhỏ nhất các câu hỏi bạn sẽ đạt kết quả. Biết rằng, số
điện thoại của tôi là một số có
11
chữ số. Giả sử rằng một trong các câu hỏi của
bạn tôi sẽ trả lời sai sự thật. Khi đó bạn sẽ hỏi thế nào và số các câu hỏi nhỏ nhất
là bao nhiêu để tìm ra số điện thoại của tôi.
Giải Người hỏi cần đặt các câu hỏi sao cho mỗi câu hỏi giảm đi một nửa số
lượng các khả năng xảy ra còn lại. Với hệ thống câu hỏi như vậy, để phỏng đoán
một trong
2
n
khả năng cần có
n
câu hỏi. Vì theo điều kiện bài toán có tất cả
11 37
10 2

số điện thoại khác nhau nên ta chỉ cần hỏi 37 câu hỏi. Tuy nhiên, tất cả
các câu hỏi đưa ra có thể rất khác nhau. Ví dụ có thể hỏi: „„số điện thoại của anh
lớn hơn
5000000000
phải không?” Nếu trả lời “đúng‟‟, thì câu hỏi thứ hai sẽ là
“nó có lớn hơn

2
và
36
10000000000 2
nên
2
số điện thoại khác nhau dẫn 22
đến một dãy như nhau các câu trả lời và người bạn sẽ không thể khẳng định được
số câu trả lời của tôi.
1.4 Kĩ thuật tô màu
Tô màu được dùng phổ biến trong lí thuyết đồ thị. Kĩ thuật tô màu thường cho
phép chia các đối tượng thành hai màu đen trắng. Kết hợp với bất biến, ta có thể
dùng kĩ thuật tô màu để giải quyết một số bài toán trò chơi.
Bài 1.16a Một nhà triển lãm có
2
n
phòng hình tam giác đều. Hai phòng triển lãm
được gọi là hai phòng láng giềng nếu chúng có cạnh chung. Từ mỗi phòng đều
có cửa đi sang phòng láng giềng của nó. Một khách du lịch muốn đi xem càng
nhiều càng tốt số phòng triển lãm với điều kiện mỗi phòng chỉ đi qua đúng một
lần. Hỏi anh ta có thể đi tối đa bao nhiêu phòng?

Hình
.12
Hình
.13


22
n n n n
n

  
phòng. 23
Trong quá trình đi xem, khách du lịch luôn phải đi từ phòng ô trắng sang phòng ô
đen hoặc ngược lại. Giả sử có thể đi tham quan tất cả các phòng sao cho mỗi
phòng đi qua đúng một lần. Khi ấy số ô đen chỉ ít hơn số ô trắng đúng 1 ô. Mâu
thuẫn với tính toán trên. Như vậy không thể đi tham quan tất cả các phòng được.
Do mỗi phòng chỉ đi qua đúng một lần mà phải đi xen kẽ các phòng đen - trắng
liên tiếp nên số ô màu trắng đi qua chỉ hơn số ô màu đen một ô. Như vậy nếu đi
qua tất cả ô đen thì tối đa tổng số phòng có thể tham quan là:
   
2
11
11
22
n n n n
nn

    
phòng.
Có thể thực hiện được điều này theo đường đi như Hình
1.3.

Bài 1.16b (Vô địch Liên Xô lần thứ tư,

nhau (32 ô). Hai ô ở góc đối nhau cùng màu nên sau khi
bỏ chúng đi, số ô đen khác số ô trắng (thí dụ, 32 ô đen và
30 ô trắng). Như vậy, hiệu số ô đen và ô trắng là 2. Các ô
đen trắng đan xen nhau, nghĩa là cạnh ô đen phải là ô
trắng.
Hình
.14

Mỗi quân đômino phủ đúng một ô đen và một ô trắng liền kề, như thế sau khi đặt
một quân đôminô thì mất đi một ô đen và một ô trắng. Vì vậy, sau mỗi lần đặt
một quân đôminô, số ô đen và số ô trắng đều giảm đi 1, hay hiệu số giữa số ô
trắng và số ô đen trên bảng là một đại lượng bất biến (luôn bằng 2). Vì vậy
không thể phủ kín bàn cờ bởi các quân đôminô được.
Bài 1.18 Một hình tròn được chia làm 6 ô dẻ quạt bằng nhau và đặt một quân cờ
vào mỗi ô. Trong mỗi bước, cho phép chuyển một quân cờ bất kỳ sang một trong
hai hình quạt kề với nó. Hỏi sau khi thực hiện đúng 2013 lượt đi, có thể chuyển
tất cả quân cờ vào trong một hình quạt được không?
Giải Đánh số các hình quạt từ
1
đến
6

1 3 2013
, , ,a a a
là những số chẵn, còn
0 2 2012
, , ,a a a
là những số lẻ.
Sau
2013
lượt đi số quân cờ ở các hình quạt được tô màu là lẻ. Nhưng nếu các
quân cờ đều đứng ở một hình quạt thì số đó là số chẵn
(
bằng
0
hoặc bằng
6).

Mâu thuẫn, chứng tỏ không thể tập trung
2013
quân cờ vào
1
hình quạt được.
Kết luận Chương 1
6
5
4
3
2
1
Hình
.15