Chủ đề này có 1 trả lời

[123abcd]

Cho số nguyên dương lẻ $n$. Trong phòng máy tính, có $n$ chiếc máy tính. Hai chiếc máy tính bất kì được nối với nhau bởi một đoạn cáp. Người ta muốn gán màu cho các chiếc máy tính và các đoạn cáp sao cho:

$i)$ $2$ chiếc máy tính bất kì được gán $2$ màu khác nhau;

$ii)$ $n − 1$ đoạn cáp nối với một chiếc máy tính bất kì (với $n − 1$ chiếc máy tính còn lại) được

gán $n − 1$ màu khác nhau;

$iii)$ $1$ chiếc máy tính bất kì và $1$ sợi cáp bất kì nối nó (với một chiếc máy tính khác) được gán

$2$ màu khác nhau.

Chứng minh rằng có thể thực hiện được điều đó mà chỉ sử dụng đúng $n$ màu khác nhau.

[hovutenha]

Bài này bạn chỉ cần suy nghĩ ra cách tô màu là có thể giải quyết hoàn toàn bài toán.

Cách tô màu của mình như sau:

Xét đa giác đều $n$ đỉnh với mỗi đỉnh là một chiếc máy tính. Gọi $O$ là tâm đa giác đều đó. 

Đặt các đỉnh lần lượt là $A_1,A_2,..,A_n$ với đỉnh $A_i$ được tô màu $i$

Xét đường thẳng $OA_{i}$, nối 2 đỉnh $A_{j}A_{k}, j,k \neq i$ sao cho nó vuông góc với $OA_{i}$ và tô cạnh đó bằng màu $i$

Ví dụ như hình sau.

Nhận thấy rằng các tô này hoàn toàn thỏa mãn đề bài nên ta có dpcm