Một số bài toán trò chơi có nội dung toán học

Một số bài toán trò chơi có nội dung toán học

Đoàn Văn Lới

Trường Đại học Khoa học Tự nhiên

Luận văn Thạc sĩ ngành: Phương pháp toán sơ cấp; Mã số: 60 46 40

Người hướng dẫn: PGS.TS Tạ Duy Phượng

Năm bảo vệ: 2011

Abstract: Trình bày lời giải một số bài toán trò chơi nhờ công cụ hệ đếm cơ số 2: hệ

đếm số 2; máy đọc ý nghĩ; trò chơi Nim; giải bài toán Tháp Hà Nội nhờ đếm cơ số 2.

Nghiên cứu lời giải một số bài toán trò chơi cơ học nhờ công cụ mã Gray cơ số 2: mã

Gray cơ số 2; mã Gray, trò chơi Tháp Hà Nội và trò chơi Hamilton trên đa diện đều;

Baguenaudier hay trò chơi tháo vòng Trung Hoa. Tập hợp một số ví dụ trong các dạng

toán trò chơi.

Keywords: Phương pháp toán sơ cấp; Toán ứng dụng; Bài toán trò chơi

Content

1.1 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 0

1 1 0 ...

k k

k k a a p a p a p a p



     

với các hệ số nguyên

0 1, i    a p i k  0,..., ; 0. k a 

Như vậy, 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

 k k 1 1 0  p

a a a a 

trong hệ đếm cơ số

p .

Nếu

p 10

thì ta có hệ đếm cơ số 10. Do thói quen, lịch sử, truyền thống và thuận tiện, hệ

đếm cơ số 10 được sử dụng rộng rãi trong cuộc sống hiện đại.

Hệ đếm được định nghĩa như trên là hệ đếm theo vị trí, tức là mỗi hệ số

i a

(được gọi là các

chữ số của

a

) ở vị trí khác nhau có giá trị khác nhau (hàng “đơn vị”, “hàng chục”, “hàng

trăm”,...).

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ụ,

10 9 8 7 6 4 3 1 0 2011 2 2 2 2 2 2 2 2 2          .