Đáp án bài toán xếp gạch trong kỳ thi SAIMC 2019

Topic 70. COMBINATORIAL GEOMETRY

Problem: The figure below illustrates a 7-row brick wall with 2 holes (shaded in black). We want to choose a brick in each row such that any two bricks chosen in any adjacent rows are connected (two bricks are connected if they share at least a portion of their sides). In how many different ways can we choose the 7 bricks?

Dịch đề: Hình dưới đây biểu diễn một bức tường gạch xếp thành 7 hàng, trên đó có 2 lỗ hổng (như đã bôi đen). Ta cần chọn một viên gạch ở mỗi hàng sao cho cứ hai viên gạch được chọn ở hai hàng liền kề thì dính với nhau (hai viên gạch được coi là dính với nhau nếu chúng có chung ít nhất một phần cạnh). Hỏi có bao nhiêu cách để chọn ra 7 viên gạch thoả mãn yêu cầu?

Lời giải:

Ta gọi một cách chọn 7 viên gạch thỏa mãn yêu cầu là một đường đi hoàn chỉnh: mỗi viên được lấy ở một hàng, cứ hai viên gạch được chọn ở hai hàng liền kề thì dính với nhau.

Đánh số viên gạch theo từng hàng từ trái sang phải và từ trên xuống dưới theo quy tắc: Số n được đánh trong một viên gạch chính là số cách chọn đường đi từ các viên gạch ở hàng trên cùng đến nó sao cho thỏa mãn điều kiện cứ 2 viên ở 2 hàng liền kề thì dính nhau. Dễ thấy số dịch thuật ở mỗi viên gạch bằng tổng 2 số của 2 viên bên trên có chung cạnh với nó. Ta có thể mô tả quá trình đánh số theo sơ đồ sau:

Kết luận: Số cách để chọn ra 7 viên gạch thoả mãn yêu cầu chính bằng số các đường đi hoàn chỉnh và bằng 3 + 30 + 15 + 16 + 16 = 80 (cách).

Solution:

We call one brick selection that satisfies the given conditions a route: each row has one brick chosen, and any two bricks chosen in any adjacent rows are connected.

Now number all bricks on the wall from left to right and from top to bottom according to the following rule: A brick numbered n is a brick where there are n ways to link it to first-row bricks, such that on the course any two bricks in any adjacent rows are connected. Note that the number written on each brick equals to the sum of the two numbers written on the two bricks that connected with it (illustrations above).

Conclusion: The number of ways to select 7 bricks that satisfy the given conditions is the number of complete routes and equals: 3 + 30 + 15 + 16 + 16 = 80 (ways).

Minh Phương