Chia Hình hộp

(Cho trường hợp 3 đống sỏi)

                Cho một lưới hình hộp chữ nhật kích thứơc N´M´H đơn vị nguyên. Hai bạn lần lượt thực hiện thao tác sau đây: Cắt hình theo một thiết diện đi qua một điểm nguyên trên một cạnh, không trùng với đỉnh và vuông góc với cạnh đó để thu được 2 hình hôp chữ nhật sau đó vất đi hình có thể tích nhỏ hơn, trao hình có thể tích lớn hơn cho người kia. Nếu hai hình có cùng thể tích thì vất đi một hình tùy ý. Bạn nào đến lượt mình không thể thực hiện được thao tác trên thì thua. Hãy cho biết bạn đi trước thắng hay thua. Giả thiết rằng hai bạn đều chơi rất  giỏi.

                Để giải bài 3 đống sỏi chúng ta cần một chút trợ giúp của toán học. Bạn xem ba mệnh đề dưới đây và giải thử một số thí dụ nhỏ, sau đó thử bắt tay chứng minh các mệnh đề đó. Bạn cũng có thể xem lại các chứng minh đã trình bày trong các bài giải nói trên.

Cơ sở toán học

Định nghĩa 1. Các số tự nhiên dạng 2^k-1, k = 0, 1, 2,… được gọi là số Mersenne.

Thí dụ, các số 0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023 là những số Mersenne ứng với các giá trị k = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 và 10.

Các số nằm giữa các số trên thí dụ, 2, 4, 5, 6, 8, 9, 10, 11, …  không phải là số Mersenne.

Mệnh đề 1. Cho số tự nhiên n. Nếu n không phải là số Mersenne thì ta luôn luôn tìm được số tự nhiên S, 1 £ S £ n/2 để n-S là một số Mersenne.

Thí dụ,

                1. n = 2, S = ?

                2. n = 10, S = ?     

                3. n = 1534, S = ?

Gợi ý. Xác định k để  2^k < n+1 < 2^k+1. Sau đó tính  S = n+1-2^k.

Đáp án: 1. S = 1; 2. S = 3; 3. S = 511.

Cho 2 số tự nhiên n và m. Xét hệ thức

n + 1 = 2^k (m + 1), k = 0, 1, 2, …                     (*)

Mệnh đề 2            

                a) Hai số Mersenne bất kì đều thỏa hệ thức (*).

                b) Có những cặp số tự nhiên thỏa hệ thức (*) nhưng không phải là số Mersenne.

                c) Nếu cặp số tự nhiên n và m thỏa hệ thức (*) và một trong hai số đó là số Mersenne thì số kia cũng phải là số Mersenne.

Gợi ý

                 a) n= 2^a-1, m = 2^b-1,a ³ b Þ n+1 = (m+1).2^a-b.

                b) Thí dụ, 5 và 11: (11+1) = (5+1).2¹, Với mọi a, b nguyên: 5 ¹ 2^a-1, 11 ¹ 2^b-1.

                c) n+1 = (m+1).2^k, n = 2^a-1 Þ  2^a = (m+1).2^k hay m = 2^a-k - 1.  

Mệnh đề 3. Cho 2 số tự nhiên n và m, n > m. Nếu n và m không thỏa hệ thức (*) thì ta luôn luôn tìm được số S, 1 £ S £ n/2 để n-S và m thỏa hệ thức (*).

Thí dụ,

                1. n = 12, m = 3 , S = ?

                2. n = 50, m = 5, S = ?        

                3. n = 54, m = 6, S = ?

Đáp án: 1. S = 5; 2. S = 3; 3. S = 27.

Gợi ý. Xác định k max để  2^k(m+1)< n+1.  Sau đó tính  S = n+1-2^k(m+1).

                Tiếp theo sẽ là bài toán bốc nhiều đống sỏi với luật bốc số quân không hạn chế trong một đống duy nhất đã chọn.

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH