Chủ nghĩa bảo thủ của hệ thống vô tận

33

G. Kurdimov

Chủ nghĩa bảo thủ của một hệ thống vô tận

Ghi chú này giải quyết bài toán M500g) từ Zadaniak «Kvant» («Kvant», 1978, số 4; xem thêm 1979, số 2). Ở cuối ghi chú có ba bài toán, lời giải mới, hai trong số đó (bài toán 1 và 3) chưa rõ.

Có vô số sự tái cổ điển theo cả hai hướng. Theo lệnh bên trái-VO, tất cả các xe cổ điển, ngoại trừ chiếc cuối cùng, nhiều người trong số họ, rẽ sang trái; phần còn lại quay sang phải. Trong mỗi giây tiếp theo, mỗi chiếc cổ điển sẽ quay 180° nếu người thứ nhất và thứ ba trong số những người đứng trước nó quay mặt về phía nó. Tất cả các reclassics khác vẫn bất động. Chứng minh rằng chuyển động trong hệ vô hạn này sẽ dừng lại sau một thời gian hữu hạn.

Hãy để tất cả những người theo chủ nghĩa tái cổ điển ban đầu đối mặt với chúng ta (Hình 1, a). Sau lượt đầu tiên, tất cả sẽ nhìn sang trái hoặc phải. Rõ ràng, ngay từ đầu, ai thực hiện đúng lệnh “sang trái” sẽ ở bên phải, còn “kẻ vi phạm” sẽ ở bên trái.

Theo điều kiện, tại thời điểm đầu tiên có một số lượng hữu hạn các bản tái cổ điển còn lại.

Chúng ta hãy mô tả những người tái cổ điển, những người sẽ quay lại trong giây tiếp theo, với những vertun (có thể dễ dàng nói rằng tại mỗi thời điểm có một số lượng hữu hạn những vertun). Chúng tôi sẽ gọi những kẻ quay cánh tả là độc hại. Rõ ràng, một người theo chủ nghĩa tái cổ điển bên trái là có ác ý nếu có một người theo chủ nghĩa tái cổ điển bên trái đứng trước nó ở vị trí thứ nhất hoặc thứ ba (Hình 1, c). Chúng ta sẽ vẽ các Vertin có màu xanh lá cây, các bộ phân loại lại độc hại có màu đỏ và các Vertin bên phải có màu xanh lam (Hình 1, c).

Trước khi trình bày chứng minh ở dạng tổng quát, chúng ta xét một trường hợp đặc biệt để minh họa. Giả sử có đúng bảy lần phân loại lại còn lại và tất cả chúng đều đứng thành một hàng. Sự phát triển của một hệ thống như vậy theo thời gian được thể hiện trong Hình 2. Chúng ta thấy rằng sau 12 giây không còn lại phần tái phân loại nào. Tương tự,

Hình 1.

34

Chúng ta hãy xem sự tiến hóa của đội hình khi có bất kỳ phần liên tục nào của n học sinh lớp một bên trái: sau 2n-2 giây tất cả học sinh lớp một sẽ thuận tay phải và chuyển động sẽ dừng lại.
Bây giờ chúng ta trình bày chứng minh cho trường hợp tổng quát - khi học sinh lớp 1 bên trái đứng tùy ý. Chúng ta cần một vài định nghĩa bổ sung. Chúng ta hãy gọi một hòn đảo là một đoạn nối phần ngoài cùng bên phải của phần bên trái và phần ngoài cùng bên trái
một trong những người cánh tả tồi tệ nhất. Chúng ta sẽ gọi đầm lầy là đoạn ngắn nhất liền kề với hòn đảo bên trái và bao gồm tất cả các vertun (tất nhiên, có thể không có đầm lầy).
Những học sinh lớp một không vào đảo hoặc đầm lầy được gọi là biển (Hình 3).
Bổ đề 1 (hiển nhiên). Nếu bên phải của học sinh lớp 1 A đứng im lặng bên phải của học sinh lớp 1 thì A luôn là mak và ta đúng (Hình 4).

Hình 2.
biển
đầm lầy
hòn đảo
biển

Hình 3.