Bài tập Toán rời rạc - Bài 3

Toán rời rạc Bài tập 3 Bài 1: Chứng minh sai Tìm lỗi sai trong chứng minh dưới đây rằng an = 1 với mọi số nguyên không âm n và a là số thực không âm. Chứng minh. Ta sẽ chứng minh quy nạp theo n, với giả thiết P(n) := ∀k ≤ n. ak = 1, trong đó k là biến nhận giá trị nguyên không âm. Bước cơ sở: P(0) tương đương với a0 = 1 đúng theo định nghĩa của a0 (kể cả khi a = 0). Bước quy nạp: Giả sử ak = 1 với mọi k ∈ N thỏa mãn k ≤ n. Nhưng vậy thì an+1 = an · an an−1 = 1 · 1 1 = 1 kéo theo P(n+ 1) đúng. Vậy bởi quy nạp P(n) đúng với mọi n ∈ N, có nghĩa rằng an = 1 đúng với mọi n ∈ N. Bài 2: Bài toán ô chữ Trong một trò chơi ô chữ, có 15 chữ cái và một ô trống đặt trên một lưới 4× 4. Một bước chuyển gọi là hợp lệ nếu chữ cái chỉ di chuyển sang ô trống kề với nó. Ví dụ, một dãy gồm hai bước chuyển được mô tả như sau: Trong cấu hình trái nhất ở hình trên, chữ O và N là sai thứ tự. Liệu có cách chuyển hợp lệ để có thể hoán đổi vị trí của O và N mà vẫn giữ nguyên vị trí của các chữ khác, và vị trí ô trống vẫn ở góc phải bên dưới của lưới? Trong bài toán này, bạn sẽ chứng minh câu trả lời là “không thể". Định lý. Không tồn tại dãy chuyển để đưa từ cấu hình bên trái dưới đây sang cấu hình bên phải. 1 (a) Ta định nghĩa một “thứ tự” của các chữ trên lưới là dãy đi từ dòng trên xuống dòng dưới, và với mỗi dòng đi từ trái qua phải. Ví dụ, trong lưới bên phải thứ tự các chữ là A,B,C ,D, E, . . . . Liệu việc di chuyển một chữ theo hàng có làm thay đổi thứ tự trước sau của các cặp chữ? Có nghĩa rằng, liệu có cặp chữ (L1, L2) thỏa mãn L1 đứng trước L2 nhưng sau khi di chuyển một chữ theo hàng lại làm L1 đứng sau L2? Chứng minh câu trả lời của bạn. (b) Có bao nhiêu cặp chữ bị thay đổi thứ tự sau mỗi lần di chuyển một chữ theo cột? Chứng minh câu trả lời của bạn. (c) Một cặp chữ (L1, L2) gọi là ngược nếu L1 đứng trước L2 theo thứ tự từ điển, nhưng L1 lại đứng sau L2 theo thứ tự định nghĩa ở câu (a). Ví dụ, cấu hình sau đây: có đúng bốn cặp ngược: (D, E), (G,H), (F,H) và (F,G). Việc chuyển một chữ theo hàng ảnh hưởng đến tính chẵn lẻ của số các cặp ngược như thế nào? Chứng minh câu trả lời của bạn. (d) Việc chuyển một chữ theo cột ảnh hưởng đến tính chẵn lẻ của số các cặp ngược như thế nào? Chứng minh câu trả lời của bạn. (e) Chứng minh bổ đề sau đây: Bổ đề. Trong mỗi cấu hình đạt được từ cấu hình dưới đây, tính chẵn lẻ của số các cặp ngược khác với tính chẵn lẻ của hàng chứa ô trống. (f) Từ các nhận xét (a)–(e), hãy chứng minh định lý đã đưa ra ở trên. Bài 3: Robot Một robot đi trên một lưới nguyên hai chiều. Nó bắt đầu tại điểm (0,0), và di chuyển mỗi bước theo một trong bốn cách sau: 1. (+2,−1): sang phải 2 bước, đi xuống 1 bước. 2. (−2,+1): sang trái 2, đi lên 1 3. (+1,+3) 4. (−1,−3) 2 Liệu sau một số bước robot có thể đi tới được vị trí (1,1) không? Nếu được hãy chỉ ra một cách đi. Nếu không được hãy chứng minh. Bài 4: Hàm Ackermann Các bài tập sau đây liên quan đến hàm Ackermann. Hàm này được định nghĩa như sau: A(m,n) =  2n nếu m= 0 0 nếu m≥ 1 và n= 0 2 nếu m≥ 1 và n= 1 A(m− 1,A(m,n− 1)) nếu m≥ 1 và n≥ 2 1. Tìm các giá trị của hàm Ackermann (a) A(1,0) (b) A(1,1) (c) A(0,1) (d) A(2,2) (e) A(2,3) (f) A(3,3) 2. Tìm A(3,4) 3. Chứng minh rằng A(m,n+ 1)> A(m,n) với mọi số nguyên không âm m,n. 4. Chứng minh rằng A(m+ 1,n)> A(m,n) với mọi số nguyên không âm m,n. Bài 5: Lây cúm Trong lớp Toán rời rạc, các sinh viên được xếp ngồi trên một lưới n× n. Một sinh viên bị cúm sẽ lây cho một số sinh viên khác trong lớp. Dưới đây là một ví dụ khi n= 6 và các sinh viên bị cúm được đánh dấu ×. Hai sinh viên ở vị trí kề nhau nếu họ có chung cạnh (cụ thể, trên, dưới, phải, trái, nhưng không chéo); vậy, mỗi sinh viên kề với 2,3 hoặc 4 người khác. Bây giờ, việc lây lan bắt đầu diễn ra từng phút. Một sinh viên bị nhiễm cúm ở thời điểm tiếp theo nếu hoặc 3 • sinh viên này trước đó đã bị cúm, hoặc • sinh viên này kề với ít nhất hai người đã bị nhiễm cúm. Ví dụ, việc lây lan được chỉ ra như dưới đây Trong ví dụ trên, sau một vài bước, mọi sinh viên trong lớp sẽ bị nhiễm cúm. Hãy chứng minh định lý sau đây. Định lý. Nếu tại thời điểm ban đầu trong lớp có ít hơn n sinh viên bị nhiễm cúm, thì không bao giờ xảy ra việc cả lớp đều bị nhiễm cúm. Gợi ý: Để hiểu hệ thống kiểu như trên “tiến triển" thế nào theo thời gian, một chiến lược là 1. xác định một tính chất phù hợp của hệ thống ở giai đoạn ban đầu, và 2. chứng minh, bằng quy nạp theo bước thời gian, rằng tính chất này là bảo toàn ở mọi bước. Vậy hãy bắt đầu bằng việc tìm kiếm một tính chất (của tập sinh viên bị nhiễm cúm) không thay đổi (bất biến) theo thời gian. 4