Đáp án bài toán tiếng Anh tô màu bản đồ

Bài toán tô màu bản đồ trong kỳ thi vòng 2 APMOPS 2011 chỉ sử dụng hai quy tắc cơ bản của nguyên lý là cộng và nhân. Tuy nhiên, nút thông minh đầu tiên của bài toán là phải phân loại đầu vào chính xác khi xem xét việc tô màu cho 2 bang A và D để sử dụng quy tắc cộng. Sau đó phải thống kê chi tiết và áp dụng quy tắc nhân khi tô màu cho 4 bang còn lại.

Topic 3: Counting

Problem: The above figure is a map of a nation which has 6 states. They are considering to color these states using 5 colors. Suppose that any two adjacent states, i.e. any two states that share a border, cannot be similarly colored, find the number of ways to color these 6 states.

Dịch đề: Đây là bản đồ của một nước có 6 bang. Họ định dùng 5 màu để tô màu bản đồ. Biết rằng các bang có cùng đường biên thì không được có cùng màu. Tính số cách để tô màu 6 bang đó.

Đáp án:

Ta sẽ bắt đầu tô màu cho A và D theo 2 khả năng sau đây:

1. Xét A và D tô cùng một màu:

Có 5 cách tô màu cho A và D tô cùng 1 màu.

Có 4 cách tô màu cho B khác với A và D.

Có 4 cách tô màu cho F khác với A và D.

Có 3 cách tô màu cho C khác A; D và B.

Có 3 cách tô màu cho E khác A; D và F.

Theo quy tắc nhân ta có số cách tô màu cho 6 bang là:

5 x 4 x 4 x 3 x 3 = 720 (cách) (1).

2. Xét A và D tô khác màu nhau:

Có 5 cách tô màu cho A.

Có 4 cách tô màu cho D khác A.

Có 3 cách tô màu cho C khác A và D.

Có 3 cách tô màu cho E khác A và D.

Có 3 cách tô màu cho B khác A và C.

Có 3 cách tô màu cho F khác A và E.

Theo quy tắc nhân ta có số cách tô màu cho 6 bang là:

5 x 4 x 3 x 3 x 3 x 3 = 1620 (cách) (2).

Theo quy tắc cộng thì từ (1) và (2) ta có tổng số cách tô màu cho 6 bang là:

720+1620=2340 (cách).

Solution:

Consider two possibilities while choosing the color for A and D:

1. A and D are similarly colored:

There are 5 ways to choose the color for both A and D.

There are 4 ways to choose the color for B so that B is colored differently from A and D.

There are 4 ways to choose the color for F so that F is colored differently from A and D.

There are 3 ways to choose the color for C so that C is colored differently from A, D, and B.

There are 3 ways to choose the color for E so that E is colored differently from A, D, and F.

According to the multiplication principle, the number of ways to color all 6 states in this case is:

5 x 4 x 4 x 3 x 3 = 720 (ways) (1)

2. A and D are differently colored

There are 5 ways to choose the color for A.

There are 4 ways to choose the color for D so that D is colored differently from A.

There are 3 ways to choose the color for C so that C is colored differently from A and D.

There are 3 ways to choose the color for E so that E is colored differently from A and D.

There are 3 ways to choose the color for B so that B is colored differently from A and C.

There are 3 ways to choose the color for F so that F is colored differently from A and E.

According to the multiplication principle, the number of ways to color all 6 states in this case is:

5 x 4 x 3 x 3 x 3 x 3 = 1620 (ways) (2).

Thus, according to the addition principle, from (1) and (2) we have the total number of ways to color all 6 states: 720+1620=2340 (ways).

Vocabulary

• Bài toán tiếng Anh tô màu bản đồ