Tài liệu thách thức tư duy thuật toán Bebras

Mục lục

I Một sốchủđềxuất hiện trong kì thi Thách thức tư duy Thuật toán 3

1 Các bài toán liên quan đến suy luận logic 5 1.1 Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Hướng dẫn giải các bài tập . . . . . . . . . . . . . . . . . . . . . . . . 14

2 Bài toán vùng lân cận 21 2.1 Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2 Hướng dẫn giải các bài tập . . . . . . . . . . . . . . . . . . . . . . . . 29

3 Mã hóa và xửlý dữliệu 37 3.1 Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2 Hướng dẫn giải các bài tập . . . . . . . . . . . . . . . . . . . . . . . . 49

4 Bài toán đếm 55 4.1 Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.2 Hướng dẫn giải các bài tập . . . . . . . . . . . . . . . . . . . . . . . . 60

5 Bài toán lần ngược từcuối 67 5.1 Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.2 Hướng dẫn giải các bài tập . . . . . . . . . . . . . . . . . . . . . . . . 73

6 Các bài toán vềtrò chơi 83 6.1 Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 6.2 Hướng dẫn giải các bài tập . . . . . . . . . . . . . . . . . . . . . . . . 91

II Đềthi và đáp án kỳthi chính thức năm 2020 99

7 Đềthi chính thức năm 2020 101 7.1 Đềthi cấp độ1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 7.2 Đềthi cấp độ2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 7.3 Đềthi cấp độ3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 7.4 Đềthi cấp độ4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

1

2 MỤC LỤC

8 Hướng dẫn giải đềthi năm 2020 141 8.1 Hướng dẫn giải đềthi cấp độ1 . . . . . . . . . . . . . . . . . . . . . 141 8.2 Hướng dẫn giải đềthi cấp độ2 . . . . . . . . . . . . . . . . . . . . . 144 8.3 Hướng dẫn giải đềthi cấp độ3 . . . . . . . . . . . . . . . . . . . . . 148 8.4 Hướng dẫn giải đềthi cấp độ4 . . . . . . . . . . . . . . . . . . . . . 153

TÀI LIỆU THAM KHẢO 157

Chương 1

Các bài toán liên quan đến suy luận logic

1.1 Bài tập

Bài tập 1.1. Hải ly có một khu vườn với các ô đất được chia dạng lưới tổong như hình minh họa bên dưới. Bạn ấy đã trồng cà chua ởnhững ô đất có màu xám và đang chuẩn bịtrồng thêm những cây cúc vạn thọđểđuổi côn trùng. Biết rằng số được ghi ởmỗi ô đất trồng cà chua tương ứng là sốô trồng cúc vạn thọởkềnó.

Sốbịche ởsau chữA là sốnào?

(A) 0 (B) 1

(C) 2 (D) 4

Bài tập 1.2. Hình dưới mô tảbản ghi trạng thái của bốn dãy 8-bit (byte) trong một thanh nhớ, tuy nhiên có một bit nào đó đã bịghi nhầm. Biết rằng mỗi byte đều có một sốchẵn bit 1 và khi xét tại mỗi thứtựbit, sốbit 1 của cảbốn byte cũng là một sốchẵn.

5

6 Các bài toán liên quan đến suy luận logic

Bit nào đã bịghi nhầm giá trị?

(A) bit 2 của byte 1 (B) bit 6 của byte 3

(C) bit 4 của byte 2 (D) bit 5 của byte 4

Bài tập 1.3. Trong một cuộc thi chạy có sựtranh tài của các bạn hải ly và các bạn chó. Biết rằng có tất cả9 vận động viên với thứhạng lần lượt là 1, 2, 2, 4, 5, 6, 6, 8, 9. Có hai chú chó nào đó vềđích cùng lúc và người ta nhận thấy rằng:

ˆ Không bạn chó nào vềđích sau bất kỳbạn hải ly nào.

ˆ Có một bạn chó và một bạn hải ly nào đó vềđích cùng lúc với nhau.

Hỏi có bao nhiêu bạn chó tham gia cuộc thi chạy này?

(A) 2 (B) 6

(C) 3 (D) 7

Bài tập 1.4. Sau giờhọc, các bạn hải ly thường đi chơi cùng với nhau. Thường thì các bạn sẽmuốn đi nhiều nơi khác nhau nên đểtránh việc tranh cãi, họđã thống nhất đưa ra quyết định bằng cách tung xúc xắc. Nhóm bạn sẽtung xúc xắc 2 hoặc 3 lần và chọn điểm đến theo bảng chỉdẫn sau:

Tung xúc xắc hai lần Nếu Lần thứnhất lớn hơn lần thứhai Thì Đi chơi trong rừng

Không thì

Tung xúc xắc thêm một lần nữa Nếu Lần thứba nhỏhơn lần thứnhất Thì Đi chơi ởsông Không thì Đi trượt cỏ