Có một đống sỏi gồm n viên sỏi. Hai người thay phiên nhau bốc sỏi đến khi ai không thực hiện được thì thua, hỏi ai là người có chiến lược thắng (người đi trước hay đi sau) nếu như (a) Ở mỗi lượt được bốc 1, 3, 4 viên. (b) Ở mỗi lượt được bốc 1, 2, 12 viên. (c) Người đi trước chỉ được bốc {1, 3, 5,..., 99} viên và người đi sau chỉ được bốc {2, 4, 6,..., 100} viên.

Giải thích

Đáp án: Gọi f ( n ) : N → { 0 , 1 } với 0 là vị trí thua, 1 là vị trí thắng tương ứng với thời điểm hiện tại có n viên sỏi. (a) Ở trường hợp này, ta dễ dàng kiểm tra được f ( 0 ) = 0 , f ( 1 ) = 1 , f ( 2 ) = 0 , f ( 3 ) = 1 , f ( 4 ) = 1 , f ( 5 ) = 1 , f ( 6 ) = 1 , f ( 7 ) = 0 , f ( 8 ) = 1 , f ( 9 ) = 0 , f ( 10 ) = 1 , f ( 11 ) = 1 , f ( 12 ) = 1 , f ( 13 ) = 1. Từ đó, dự đoán rằng nếu n chia hết cho 7 hoặc chi dư 2 thì đó là vị trí thua; ngược lại có vị trí thắng. Trên cơ sở đó, ta thực hiện quy nạp như sau: đặt A là tập hợp các số tự nhiên chia 7 dư 0, 2; còn B là tập hợp các số tự nhiên còn lại. Bước cơ sở với 7 số đầu tiên đã được kiểm tra. Ta xét tiếp các số n ≥ 7 : • Mỗi số ở A và lớn hơn 6, bằng các thao tác trừ đi 1 hoặc 3 hoặc 4 sẽ đưa về một số thuộc B. • Mỗi số ở Bvà lớn hơn 6, luôn tồn tại cáchtrừ đi 1 hoặc 3 hoặc 4 đểđưa về một số thuộc A. Quy nạp hoàn tất và các giá trị cần tìm nằm trong tập B. (b) Tương tự Ví dụ 5.1, ta thấy với các số n từ 1 → 11 thì vẫn theo quy tắc: f ( n ) = 0 khi và chỉ khi 3 ∣ n . Tuy nhiên, đến f ( 12 ) = 1 , từ đó ta tìm tiếp quy luật như sau f ( 13 ) = 0 , f ( 14 ) = 1 , f ( 15 ) = 1 , f ( 16 ) = 0 , f ( 17 ) = 1 , f ( 18 ) = 1 , f ( 19 ) = 0 , ... Từ đó nhận ra quy tắc là f ( n ) = 0 nếu như 3 ∣ n − 1 và n ≥ 12 . (c) Nếu n ≤ 100 thì dễ thấy tính chẳn lẻ của số sỏi sẽ quyết định người thắng cuộc. Từ đó, ta thấy rằng số dư của n khi chia cho 101 là chẵn thì người thứ nhất thua vì nếu người đó bốc k viên thì người sau sẽ bốc 101 − k viên để đưa về số sỏi là số chẵn nhỏ hơn 101. Ngược lại thì người thứ nhất thắng.