Lang thang trong ba hành lang • Konstantin Knoop • Các nhiệm vụ khoa học phổ biến về “Yếu tố” • Toán học

Đi lang thang trong ba hành lang

Nhiệm vụ

Ba hành lang thẳng có chiều dài bằng nhau d hình thành hình vẽ được mô tả trong Hình 1.

Hình 1.

Tên gangster và cảnh sát di chuyển dọc theo hành lang, và tốc độ tối đa của nhân viên cảnh sát cao gấp 2 lần tốc độ tối đa của tên gangster. Thật không may, các hành lang dài, và cảnh sát có một tầm nhìn hạn chế – anh ta chỉ có thể nhìn thấy tên gangster nếu anh ta có thể ở khoảng cách không quá 1.

Hãy đến với Một thuật toán cho phép một cảnh sát bắt một tên gangster: a) tại d = 3; b) tại d = 4,999; c) tại bất kỳ d < 7.


Mẹo 1

Thuật toán cảnh sát không nên phụ thuộc vào cách thức và cách thức xã hội đen thực hiện, bởi vì cảnh sát không nhìn thấy tên gangster trong quá trình thực hiện thuật toán (và vào lúc đó khi nhìn thấy, tên gangster sẽ bị bắt vì cảnh sát có lợi thế về tốc độ). Đặc biệt, thuật toán chính xác sẽ hoạt động với bất kỳ hành vi nào của tên xã hội đen, và ngay cả khi tên xã hội đen có ý thức rõ về vị trí của cảnh sát tại mỗi thời điểm. Do đó, trên thực tế, chúng ta phải tìm ra “đường cong theo đuổi”, điều này sẽ cho phép cảnh sát tìm thấy tên gangster trong “tấm trefoil”.Vì vậy, chúng ta có thể giả định rằng dọc theo đường cong này, cảnh sát luôn di chuyển càng nhanh càng tốt.


Mẹo 2

Hãy để cảnh sát bắt đầu di chuyển từ điểm A đến trung tâm của trefoil Osau đó đi một khoảng cách dọc theo hành lang OB và quay lại O (Hinh 2). Làm thế nào đến nay ông có thể đi bộ, do đó, tại thời điểm trở lại của mình, hãy chắc chắn rằng không có gangster trong hành lang Oa?

Hình 2


Mẹo 3

Câu trả lời cho câu hỏi được xây dựng trong mẹo 2 là 2. Vì vậy, đoạn văn a) đã được giải quyết: không có xã hội đen nào trong hành lang Oacũng không phải trong hành lang OBdo đó, anh ta phải ở trong hành lang OCvà chính xác là cảnh sát của anh ta tiếp tục bắt.

Để giải quyết mục b) cảnh sát phải tiếp tục đuổi theo – trước tiên đi vào hành lang OC một khoảng cách để tại thời điểm trả lại nó được hiểu chính xác rằng các xã hội đen không có thời gian để chạy qua OB trong Oa. (Chứng minh rằng khoảng cách này bằng 3.) Khi anh ta quay trở lại, anh ta đang chải lại. OB vì vậy mà vào thời điểm trả lại tên gangster không có thời gian để chạy từ OC trong Oa. Và cứ thế – hãy tìm ra lý do tại sao điều này sẽ đủ cho mọi giá trị. dít hơn 5.

Hình 3


Giải pháp

a) Vậy tại sao khi d = 3 là đúng những gì được viết trong gợi ý thứ hai? Đó là, tại sao sau khi cảnh sát "lặn" vào hành lang OB đến độ sâu 2 và quay lại O nó có thể được lập luận rằng các xã hội đen là chính xác trong OC? Rõ ràng là anh ta không ở trong hành lang OBbởi vì, đã trôi qua OB khoảng cách d – 1 = 2, cảnh sát nhìn thấy cuối hành lang. Liệu tên gangster có thời gian nhảy ra khỏi hành lang trong thời gian này không? OC vào hành lang Oa và ở đó ở khoảng cách mà nó đến từ một điểm O cảnh sát sẽ thấy không? Không, bởi vì lúc đầu anh ta ở khoảng cách> 1 trong hành lang OC, cuối cùng phải ở khoảng cách> 1 ở hành lang Oa, có nghĩa là nó phải vượt qua hơn 2. Tuy nhiên, trong khi cảnh sát bước vào hành lang OB, một tên côn đồ có thể di chuyển không quá một nửa con đường của một cảnh sát, đó là (2 + 2) / 2 = 2. Điểm a) đã giải quyết.

b) Bây giờ hãy xử lý vụ việc d = 4.999. Trong hình. 3 cho thấy vị trí của nhân viên cảnh sát sau khi "lặn" vào hành lang. OC ở độ sâu 3. Quay trở lại một điểm O và không nhìn thấy tên gangster, cảnh sát biết rằng trong hành lang OC các gangster không phải là ít nhất là sâu như 4. Ngoài ra, các xã hội đen không thể vượt qua không được chú ý từ hành lang OB vào hành lang Oa, bởi vì điều này anh cần phải đi một khoảng cách lớn hơn 4, trong khi cảnh sát đi qua 2 + 3 + 3 = 8, và điều này là không thể với tốc độ của anh ta.

Xin lưu ý rằng "bổ nhào" thứ hai đã được thực hiện bởi cảnh sát đến độ sâu 3, bởi vì (2 + 3 + 3) / 2 <2 + 1 + 1. Cách tính toán độ sâu của việc bổ nhào của cảnh sát tiếp theo (một lần nữa vào hành lang OB)? Anh ta có thể đủ khả năng để đi đến đó một khoảng cách x và quay trở lại nếu trong thời gian này bọn gangster không có thời gian nhảy ra khỏi hành lang OC và đi sâu vào Oa khoảng cách lớn hơn 1. Vì cảnh sát chắc chắn rằng trong hành lang OC không có gangster ít nhất lên đến khoảng cách 3 + 1 = 4, sau đó điều kiện (3 + x + x) / 2 <4 + 1, tức là x <3.5. Đi lên x = 3,5 đến hành lang OB, cảnh sát đã biết rằng trong hành lang này, tên gangster không ở xa x + 1 = 4,5, do đó độ sâu y hành lang tiếp theo lặn OC có thể là sự bất bình đẳng giữ (3,5 + y + y) / 2 <4.5 + 1, tức là y < 3,75.

Chúng ta thấy rằng "độ sâu chìm" của một cảnh sát (xen kẽ vào hành lang OBOC) tạo thành một chuỗi gồm 2, 3, 3,5, 3,75. Chúng tôi có thể chỉ định công thức xác định các thành viên của chuỗi này không? Tất nhiên rồi. Nếu vào nm bước một cảnh sát đi vào một trong những hành lang ở một khoảng cách một(n), thì không có tên gangster nào trong hành lang này lên đến khoảng cách một(n) + 1, có nghĩa là cảnh sát tiếp theo đang chìm vào hành lang tiếp theo có thể có chiều sâu như vậy một(n + 1) đến

(một(n) + một(n + 1) + một(n + 1))/2 ≤ một(n) + 2.

Chúng ta lấy nó ở đâu một(n + 1) = (một(n) + 4) / 2. Mối quan hệ lặp lại này có thể dễ dàng được biến thành một công thức rõ ràng cho nthành viên thứ tự của chuỗi: nó chỉ ra rằng mỗi điểm tiếp theo sẽ chia đôi phân đoạn giữa điểm trước đó và điểm 4. Nói cách khác, mỗi điểm tiếp theo là gấp đôi gần 4 so với điểm trước đó. Nhưng điều này có nghĩa là khoảng cách đến 4 (lúc đầu là 2), được rút ngắn hai lần trong mỗi lần lặn tiếp theo, nghĩa là, 4 – một(n) = (4 − một(0))/2n. Đơn giản hóa phương trình này, chúng tôi nhận được 4 – một(n) = 2/2n, một(n) = 4 − 2/2n. Rõ ràng là bắt đầu từ một số n ý nghĩa một(n) sẽ lớn hơn 3.999, có nghĩa là nó sẽ đủ để buộc hoàn toàn băng đảng từ hành lang chiều dài d = 4,999.

c) Và bây giờ là thời điểm thú vị nhất. Chasing các hành lang OBOC luân phiên, như chúng ta đã thấy ở trên, nó cho phép bạn xử lý các hành lang có chiều dài nhỏ hơn 5. Nhưng làm thế nào để giải quyết vấn đề cho các hành lang dài hơn?

Đây là nơi mà một cơ hội mà chúng tôi đã không được sử dụng trước khi đến viện trợ của chúng tôi: có lái xe gangster đủ xa khỏi điểm O, một cảnh sát có thể chải một trong các hành lang đến cuối cùng (để xác định, hành lang OB anh ta bị cảnh sát đưa đến điểm mà anh ta sẽ thấy cuối hành lang). Có, trong khi tên côn đồ sẽ có thể nhảy ra khỏi hành lang. OC trong Oa qua điểm Otuy nhiên anh ta sẽ không thể rời khỏi hành lang Oa rất xa! Đi qua hành lang Oa đến độ sâu yêu cầu, cảnh sát sẽ chắc chắn rằng tên gangster không có ở đó. Điều gì sẽ xảy ra nếu tên côn đồ có thời gian để di chuyển từ OC một lần nữa trong OB? Vâng, hãy để anh ta có thời gian, nếu anh ta chỉ có thể vượt qua một bên OB rõ ràng là ít hơn nó sẽ có thể lao vào Oa ở bước trước. Nếu chúng ta thấy rằng một chuỗi lặn cho bọn côn đồ bị giảm xuống 0, điều này có nghĩa là sớm hay muộn cảnh sát có thể đảm bảo rằng không có băng đảng ở hành lang tiếp theo, và sau đó tên côn đồ sẽ có hành lang duy nhất nơi anh ta bị bắt.

Tất cả những gì còn lại cho chúng ta là tính cẩn thận tất cả những "lặn" này.

Để khoảng cách mà cảnh sát đi vào hành lang OC trước khi chải đến cuối hành lang OBbằng c. Kể từ đó trong hành lang OB cảnh sát đã đi qua lại d – 1, sau đó trong thời gian này gangster đã vượt qua không quá d – 1 + c / 2. Và kể từ khi anh ta đến từ O không gần hơn c + 1, sau đó đi sâu vào Oa anh ta không thể hơn một = d − 2 − c/ 2. Để đảm bảo rằng tên gangster không thực sự ở Oa, cảnh sát cần vào hành lang này ở độ sâu 2 (một – 1). (Thật vậy, trong thời gian này, tên côn đồ sẽ có thể vượt qua không quá một – 1, có nghĩa là nó sẽ không quá 2một – 1 từ điểm O, đó là, không xa hơn 1 từ cảnh sát, và sẽ được phát hiện và bị bắt.) Khi cảnh sát bắt đầu hành lang này kiểm tra Oatên gangster đang ở OC không gần hơn 1 O. Do đó, vào cuối kiểm tra (khi cảnh sát quay trở lại O), tên côn đồ có thể chạy vào hành lang OB không xa hơn khoảng cách b = 2một – 3. Điều kiện "b < một"mà chúng tôi muốn đạt được là tương đương với sự bất bình đẳng 2một − 3 < mộtcó nghĩa là, một <3. Do đó cần dc/2 < 5, d < 5 + c/ 2. Kể từ khi giá trị c có thể được thực hiện tùy ý gần 4, sau đó d có thể được thực hiện tùy tiện gần 7.


Lời nói

Nhiệm vụ đuổi theo một cảnh sát và một tên xã hội đen thuộc về một loạt các nhiệm vụ tìm kiếm được đảm bảo (xem Pursuit-evasion). Lần đầu tiên vấn đề này được xem xét bởi Torrens Parsons (Torrence Parsons) của Mỹ năm 1978. Cốt truyện ban đầu của vấn đề, mà Parsons giải quyết, có liên quan đến việc tìm kiếm một người đàn ông đã bị lạc trong một hang động tối tăm. Người ta giả định rằng người đang tìm kiếm anh ta, làm cho một đường vòng của đồ thị, và tìm thấy người mất tích trong trường hợp anh ta thấy mình ở đỉnh bên cạnh anh ta.

Một vài năm sau, vào năm 1982, tác phẩm của P. A. từ Leningrad đã được xuất bản.Golovach, trong đó ε-tìm kiếm được xem xét lần đầu tiên, thay vì duyệt qua biểu đồ, một con đường được xem xét trên các đối tượng hình học và điều kiện thành công (phát hiện đối tượng) được xây dựng theo cách đạt được khoảng cách ε. Trong một công thức như vậy, rõ ràng là đối tượng được tìm kiếm có thể chống lại sự phát hiện và nhiệm vụ là tìm ra trong trường hợp này sự kháng cự này có thể thành công.

Cần lưu ý rằng cả hai Parsons và Golovach đã giải quyết một vấn đề hơi khác nhau – họ đang tìm kiếm giá trị tối thiểu của số lượng kẻ truy đuổi sẽ đảm bảo sự thành công của việc bắt giữ (với bất kỳ sự bất lực hoặc đối lập). Và nhiệm vụ của một cảnh sát và một tên gangster xuất hiện nghiêm túc giữa việc phát hành các tác phẩm của Parsons và Golovach, và ở một nơi rất bất ngờ – tại Olympic Toán học Moscow, trong các lựa chọn cho 9 và 10 lớp. Nó không phải là rất rõ ràng cho dù các tác giả của vấn đề biết sau đó về một công thức tổng quát hơn, hoặc cho dù điều này hóa ra là một sự trùng hợp ngẫu nhiên.

Trong những năm qua, nhiệm vụ đã thu được nhiều tùy chọn và khái quát. Vì vậy, thư mục chú thích về vấn đề này, được xuất bản năm 2008 trong một số tạp chí đặc biệt Khoa học máy tính lý thuyết, có 172 vị trí, và trong năm 2011 thậm chí còn có một khóa đào tạo riêng cho sinh viên – "Trò chơi cảnh sát và cướp trên đồ thị".


Like this post? Please share to your friends:
Trả lời

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: