Bài toán trong kỳ thi BIMC 2018 của Bulgaria rất khó nếu phải tìm đáp số trong 6 phút. Trong số độc giả gửi lời giải, chỉ có ba bạn tìm đúng là 18 hình.
Với một số dạng bài toán đếm có đáp số không quá lớn dành cho học sinh dưới 13 tuổi, bạn chỉ cần đưa ra một cách đếm không trùng lặp và vét hết khả năng. Việc cố gắng ép một thuật toán tổng quát chung không phù hợp với bài toán này.
Topic 25: Counting Rectangles
Problem: How many rectangular regions (including square regions) of the table below have the property that the sum of the numbers in them is divisible by 49?
Dịch đề: Có bao nhiêu hình chữ nhật trong bảng dưới đây (tính cả hình vuông) sao cho tổng của các số trong hình chữ nhật chia hết cho 49?
Hướng dẫn giải:
Từ yêu cầu bài toán và hình vẽ dẫn đến việc xét 4 khả năng sau đây:
a) Tổng tất cả các số nằm trong hình vuông lớn nhất 7 × 7 là:
S = 1 + 2 + 3 + ... + 47 + 48 + 49 = 25 × 49, chia hết cho 49.
Suy ra hình vuông 7 × 7 chứa 2 số đầu và cuối (1; 49) thỏa mãn.
b) Xét các hình chữ nhật 1 × 7 có tổng các số ở trong các hình này chia hết cho 49. Để ý rằng trong các hình 1 × 7 chỉ có duy nhất hình ở cột thứ 7 tạo ra 5 hình chữ nhật sau đây có tổng các số ở bên trong nó chia hết cho 49:
(7; 14; 21; 28; 35; 42; 49); (7; 14; 21; 28; 35; 42); (14; 21; 28; 35); (21; 28); (49).
Chú ý rằng từ 5 hình chữ nhật này không thể bổ sung thêm vào nó một số hình chữ nhật khác để tạo ra một hình chữ nhật mới (khác với hình 7 × 7 đã cho) có tổng các số chia hết cho 49.
c) Từ (a) và (b) suy ra hình chữ nhật 6 × 7 chứa 2 số đầu và cuối (1; 48) thỏa mãn.
d) Bây giờ ta sẽ lấy hình 6 × 7 chứa 2 số đầu và cuối (1; 48) ở mục c) làm gốc để lần lượt bớt đi các hình đối xứng qua tâm (24;25) với các cặp số có tổng bằng 49. Khi đó ta có thêm 11 hình chữ nhật có tổng các số ở trong các hình này chia hết cho 49 (viết theo 2 số đầu và cuối): (2; 47), (3; 46), (8; 41), (9; 40), (10; 39), (15; 34), (16; 33), (17; 32), (22; 27), (23; 26), (24; 25).
Kết luận: Từ (a); (b); (c); (d) ta có 1 + 5 + 1 + 11= 18 (hình chữ nhật).
Solution:
From the given table, consider the 4 following categories:
a) The sum of the numbers in the largest square of 7 × 7 is:
S = 1 + 2 + 3 + ... + 47 + 48 + 49 = 25 × 49, which is divisible by 49.
Therefore, this 7 × 7 square with the first and last numbers (1; 49) has the needed property.
b) Consider the 1 × 7 rectangles whose sum of numbers in them is divisible by 49. Among them, only the one on the 7th column contains 5 other rectangles with the same property.
(7; 14; 21; 28; 35; 42; 49); (7; 14; 21; 28; 35; 42); (14; 21; 28; 35); (21; 28); (49).
Note that we cannot expand these 5 rectangles to create another rectangle (distinct from the given 7 × 7 rectangle) whose sum of numbers in it is divisible by 49.
c) From (a) and (b), it follows that the 6 × 7 rectangle with the first and last numbers (1; 48) has the needed property.
d) Remove the pairs of numbers whose sum are 49 from this 6 × 7 rectangle. We will have 11 rectangles whose sum of numbers in them is divisible by 49, with the first and last numbers (2; 47), (3; 46), (8; 41), (9; 40), (10; 39), (15; 34), (16; 33), (17; 32), (22; 27), (23; 26), (24; 25) respectively.
Conclusion: From (a); (b); (c); (d) we have a total of 1 + 5 + 1 + 11 = 18 (rectangles).