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

[quangminhltv99]

Ở "Thế giới Đường thẳng", có $n\geq 1$ thị trấn nằm dọc một đường thẳng theo chiều từ trái qua phải. Mỗi thị trấn có một máy ủi trái nằm ở bân trái thị trấn và một máy ủi phải ở bên phải thị trấn. Kích thước của $2n$ máy ủi này đôi một khác nhau. Mỗi lần khi có hai máy ủi trái và phải gặp nhau, máy ủi nào to hơn sẽ "ủi" máy còn lại ra khỏi đường đi. Tuy nhiên, các máy ủi không được chế tạo tốt lắm ở phần đuôi, thế nên khi một máy ủi ủi vào đuôi máy ủi khác, thì không kể kích cỡ của máy bị ủi như thế nào, nó sẽ bị ủi ra ngoài.

Cho hai thị trấn $A$ và $B$, $A$ nằm bên trái $B$.Ta nói thị trấn $A$ "ủi" được thị trấn $B$ nếu máy ủi phải của $A$ có thể đi tới $B$ và ủi tất cả các máy nó gặp ra khỏi đường đi. Tương tự ta nói thị trấn $B$ ủi được thị trấn $A$ nếu máy ủi trái của $B$ có thể đi tới $A$ và ủi tất cả các máy nó gặp ra khỏi đường đi.

CMR có đúng một thị trấn không thể bị ủi bởi các thị trấn khác.

[the unknown]

Lời giải:

Trước hết ta gọi $C_1,C_2,...,C_n$ lần lượt là các thị trấn theo thứ tự từ trái sang phải. Dễ dàng suy ra từ giả thiết rằng nếu một thị trấn $C_i$ có thể ủi được thị trấn $C_j$ thì thị trấn $C_i$ sẽ ủi được tất cả mọi thị trấn nằm ở giữa hai thị trấn này.

Ta sẽ chứng minh bài toán bằng quy nạp mạnh theo $n$. Dễ thấy trường hợp $n=1$ là hiển nhiên.

Bây giờ ta giả sử bài toán đúng với mọi $k<n$. Trước hết ta thấy có hai chiếc máy ủi "vô dụng" đó là chiếc bên trái của $C_1$ và chiếc bên phải của $C_n$, do đó ta bỏ qua hai chiếc máy này. Bây giờ nếu chiếc máy bên trái của $C_n$ ( hoặc chiếc bên phải của $C_1$) có thể ủi được tất cả các thị trấn thì bài toán được chứng minh, vì khi đó không một chiếc máy ủi nào có thể ủi lại chiếc máy ủi này và thị trấn $C_n$ không bao giờ bị ủi.

Giả sử nếu điều này là không thể. Bây giờ trong $2n-2$ chiếc máy ủi còn lại thì phải có một chiếc lớn nhất ( do kích thước các chiếc xe khác nhau). Ta có thể giả sử là chiếc bên phải của thị trấn $C_k$ với $k<n$. Khi đó chiếc xe này sẽ ủi hết tất cả các chiếc xe khác ở bên phải của nó và do đó nó sẽ ủi tất cả các thị trấn $C_{k+1},...,C_n$. Do đó nếu ta loại bỏ các thị trấn này đi thì các thị trấn còn lại sẽ không thay đổi trạng thái ủi và bị ủi của mình. Hơn nữa theo giả thiết quy nạp do $k<n$ nên trong $k$ thị trấn này có $1$ thị trấn không bao giờ bị ủi. Vậy giả thiết quy nạp đúng và bài toán được chứng minh. $\square$