Mengembara dalam tiga koridor • Konstantin Knoop • Tugas sains popular mengenai "Elemen" • Matematik

Mengembara dalam tiga koridor

Tugas

Tiga koridor lurus yang sama panjangnya d tentukan angka yang digambarkan dalam Rajah 1.

Rajah. 1.

Gangster dan anggota polis bergerak sepanjang koridor, dan kelajuan maksimum pegawai polis adalah 2 kali lebih tinggi daripada kelajuan maksimum gangster. Malangnya, koridor panjang, dan pegawai polis mempunyai pelbagai pandangan yang terhad – dia dapat melihat gangster hanya jika dia ternyata berada pada jarak tidak lebih daripada 1.

Datang dengan Algoritma yang membolehkan polis menangkap samseng: a) pada d = 3; b) pada d = 4,999; c) pada bila-bila d < 7.


Petua 1

Algoritma anggota polis tidak boleh bergantung kepada apa dan bagaimana gangster itu, kerana polis tidak melihat gangster dalam proses pelaksanaan algoritma (dan pada saat itu ketika dia melihat, gangster akan ditangkap karena polisi memiliki kelebihan kecepatan). Khususnya, algoritma yang betul harus berfungsi dengan tingkah laku mana-mana gangster, dan bahkan jika gangster itu menyedari di mana pasukan itu pada setiap masa. Oleh itu, pada hakikatnya, kita perlu mencari "lengkungan mengejar", yang membolehkan polis mencari gangster dalam "lembaran trefoil".Oleh itu, kita boleh mengandaikan bahawa sepanjang kurva ini, anggota polis sentiasa bergerak secepat mungkin.


Petua 2

Biarkan polis mula bergerak dari titik A ke pusat trefoil Okemudian berlalu beberapa jarak di sepanjang koridor OB dan kembali kepada O (Rajah 2). Sejauh mana dia boleh berjalan, sehingga pada saat kembali, pastikan tidak ada gangster di koridor Oa?

Rajah. 2


Petua 3

Jawapan kepada soalan yang dirumuskan dalam hujung 2 adalah 2. Oleh itu, perenggan a) sudah diselesaikan: tidak ada gangster di koridor Oatidak juga di koridor OBOleh itu, dia mesti berada di koridor OC, dan tepat ada lagi anggota polisnya.

Untuk menyelesaikan perkara itu b) polis mesti terus mengejar – pertama masuk ke koridor OC jarak supaya pada masa pulangan ia tepat difahami bahawa gangster tidak mempunyai masa untuk berlalu OB dalam Oa. (Buktikan bahawa jarak ini sama dengan 3.) Apabila dia kembali, dia menyikat lagi. OB supaya pada masa pulangan gangster itu tidak mempunyai masa untuk berlalu OC dalam Oa. Dan sebagainya – fikirkan mengapa ini akan mencukupi untuk sebarang nilai. dkurang daripada 5.

Rajah. 3


Penyelesaian

a) Jadi kenapa bila d = 3 adalah benar apa yang ditulis dalam petunjuk kedua? Itulah sebabnya selepas polis "menyelam" ke dalam koridor OB ke kedalaman 2 dan kembali ke O ia boleh dikatakan bahawa gangster itu betul-betul masuk OC? Sudah jelas bahawa dia tidak berada di koridor OBkerana, setelah diluluskan OB jaraknya d – 1 = 2, polis menyaksikan hujung koridor. Bolehkah gangster itu mempunyai masa untuk melompat keluar dari koridor pada masa ini? OC ke dalam koridor Oa dan berada di sana pada jarak di mana ia adalah dari satu titik O tidakkah polis melihat? Tidak, kerana pada mulanya dia berada di jarak> 1 di koridor OC, pada akhirnya hendaklah pada jarak> 1 di koridor Oa, yang bermaksud ia mesti lulus lebih dari 2. Bagaimanapun, sementara anggota polis berjalan di koridor OB, seorang gangster boleh melakukan perjalanan tidak lebih dari setengah jalan seorang anggota polis, iaitu (2 + 2) / 2 = 2. Titik a) diselesaikan.

b) Sekarang mari kita berurusan dengan kes itu d = 4.999. Dalam ara. 3 menunjukkan kedudukan pegawai polis selepas "menyelam" ke dalam koridor. OC pada kedalaman 3. Kembali ke titik O dan tidak melihat samseng, polis tahu bahawa di koridor OC gangster tidak sekurang-kurangnya sedalam 4. Selain itu, gangster tidak dapat menyeberang tanpa disedari dari koridor itu OB ke dalam koridor Oa, kerana untuk ini dia perlu pergi jauh lebih besar dari 4, sementara anggota polis telah lulus 2 + 3 + 3 = 8, dan ini mustahil dengan kelajuannya.

Sila ambil perhatian bahawa "menyelam" kedua dibuat oleh anggota polis ke kedalaman 3, kerana (2 + 3 + 3) / 2 <2 + 1 + 1. Bagaimana untuk mengira kedalaman penyelam pasukan seterusnya (sekali lagi ke koridor OB)? Dia mampu pergi ke sana jauh x dan kembali jika pada masa ini gangster tidak mempunyai masa untuk melompat keluar dari koridor OC dan menyelidiki Oa jarak yang lebih besar daripada 1. Oleh kerana polis pasti di koridor OC tidak ada gangster sekurang-kurangnya sehingga jarak 3 + 1 = 4, maka keadaan (3 + x + x) / 2 <4 + 1, i.e. x <3.5. Naik x = 3.5 ke koridor OB, polis sudah tahu bahawa dalam koridor ini gangster itu tidak jauh ke x + 1 = 4.5, jadi kedalamannya y menyelam koridor seterusnya OC mungkin seperti ketidaksamaan memegang (3.5 + y + y) / 2 <4.5 + 1, i.e. y < 3,75.

Kita melihat bahawa "kedalaman perendaman" seorang anggota polis (bergantian ke koridor OB dan OC) membentuk urutan 2, 3, 3.5, 3.75. Bolehkah kita menentukan formula yang menentukan anggota urutan ini? Sudah tentu. Jika dihidupkan nm langkah seorang anggota polis pergi ke salah satu koridor di jauh a(n), maka tidak ada gangster di koridor ini sehingga jarak a(n) + 1, yang bermaksud bahawa perendaman anggota polis seterusnya ke koridor seterusnya boleh mempunyai kedalaman sedemikian a(n + 1) ke

(a(n) + a(n + 1) + a(n + 1))/2 ≤ a(n) + 2.

Di mana kita mendapatnya a(n + 1) = (a(n) + 4) / 2. Hubungan berulang ini dengan mudah boleh diubah menjadi formula eksplisit untuk nahli dalam urutan: ini menunjukkan bahawa setiap titik berikutnya akan memisahkan segmen antara titik sebelumnya dan titik 4. Dengan kata lain, setiap titik berikutnya adalah dua kali lebih dekat dengan 4 dari yang sebelumnya. Tetapi ini bermakna bahawa jarak ke 4 (yang pada mulanya adalah 2), dipendekkan oleh dua kali dalam setiap menyelam berikutnya, iaitu, 4 – a(n) = (4 − a(0))/2n. Memudahkan persamaan ini, kita dapat 4 – a(n) = 2/2n, a(n) = 4 − 2/2n. Adalah jelas bahawa bermula dari beberapa n makna a(n) akan menjadi lebih daripada 3.999, yang bermaksud bahawa ia akan cukup untuk memaksa keluar gangster dari koridor panjang d = 4,999.

c) Dan kini momen paling menarik. Mengejar koridor OB dan OC secara bergantian, seperti yang kita lihat di atas, ini membolehkan anda menangani koridor panjang apa pun yang kurang dari 5. Tetapi bagaimana menyelesaikan masalah untuk koridor yang lebih panjang?

Ini adalah di mana peluang yang kita tidak gunakan sebelum datang kepada bantuan kami: telah memacu gangster cukup jauh dari titik itu O, seorang anggota polis boleh menyikat salah satu koridor ke akhir (untuk definiteness, koridor itu OB dia diluluskan oleh anggota polis ke titik yang mana dia akan melihat hujung koridor itu). Ya, sementara gangster itu akan dapat keluar dari koridor. OC dalam Oa melalui titik Owalau bagaimanapun dia tidak dapat meninggalkan di lorong Oa sangat jauh! Lulus kemudian koridor itu Oa Kepada kedalaman yang diperlukan, polis akan memastikan bahawa gangster tidak ada di sana. Bagaimana jika gangster mempunyai masa untuk bergerak dari OC sekali lagi dalam OB? Ya, biarlah dia punya masa, jika hanya dia berjaya melintas ke sisi OB jelas kurang daripada mungkin untuk terjun ke dalam Oa dalam langkah sebelumnya. Sekiranya kita melihat bahawa urutan penyelaman untuk gangster dikurangkan kepada 0, ini bermakna bahawa lambat laun polis dapat menjamin bahawa tidak ada gangster di koridor seterusnya, dan kemudian gangster itu akan mempunyai satu-satunya koridor di mana dia akan ditangkap.

Semua yang tersisa untuk kita adalah dengan berhati-hati mengira semua "selaman" ini.

Biarkan jarak yang masuk ke koridor OC sebelum menyikat ke hujung koridor OBsama dengan c. Sejak itu di koridor OB polis pergi dan balik d – 1, maka pada masa ini gangster itu tidak melebihi d – 1 + c / 2. Dan sejak dia berasal O tidak lebih dekat daripada c + 1, kemudian masuk ke dalam Oa dia tidak boleh lebih daripada a = d − 2 − c/ 2. Untuk memastikan bahawa gangster itu tidak benar-benar masuk Oa, polis perlu memasuki koridor ini pada kedalaman 2 (a – 1). (Sememangnya, pada masa ini gangster itu akan dapat lulus tidak lebih daripada a – 1, yang bermaksud ia tidak akan lebih dari 2a – 1 dari titik O, iaitu, tidak lebih dari 1 dari anggota polis, dan akan dikesan dan ditangkap.) Apabila polis memulakan cek koridor ini Oagangster berada OC tidak lebih dekat daripada 1 jauhnya O. Oleh itu, pada akhir cek (apabila pegawai polis kembali ke O), gangster itu boleh masuk ke koridor OB tidak jauh dari jarak b = 2a – 3. Keadaan "b < a"yang kita mahu capai adalah bersamaan dengan ketidaksamaan 2a − 3 < aiaitu, itu a <3 Oleh itu, keperluan dc/2 < 5, d < 5 + c/ 2. Sejak nilai itu c boleh dibuat dengan sewenang-wenang dekat dengan 4, kemudian d boleh dibuat dengan sewenang-wenangnya hingga 7.


Selepas perkataan

Tugas mengejar seorang anggota polis dan gangster adalah kepunyaan beberapa tugas carian terjamin (lihat Pursuit-evasion). Untuk pertama kalinya, masalah tersebut telah dipertimbangkan oleh American Torrens Parsons (Torrence Parsons) pada tahun 1978. Plot asal masalah itu, yang dipecahkan Parsons, berkaitan dengan pencarian seorang lelaki yang hilang dalam gua gelap. Dianggap bahawa orang yang mencari dia, membuat lencongan graf, dan mendapati orang yang hilang sekiranya dia mendapati dirinya di puncak sebelahnya.

Beberapa tahun kemudian, pada tahun 1982, karya P. A. dari Leningrad telah diterbitkan.Golovach, di mana ε-search pertama kali dipertimbangkan, iaitu, bukannya melintasi graf, jalan dipertimbangkan pada objek geometri, dan keadaan untuk kejayaan (pengesanan objek) dirumuskan dari segi mencapai beberapa jarak ε kepadanya. Dalam formulasi sedemikian, sudah jelas bahawa objek yang dicari boleh menentang pengesanan dan tugasnya adalah untuk mengetahui di mana kes rintangan ini dapat berhasil.

Perlu diingatkan bahawa kedua-dua Parsons dan Golovach menyelesaikan masalah yang sedikit berbeza – mereka mencari nilai minimum dari jumlah pengejar yang akan menjamin kejayaan penangkapan (dengan sebarang tindakan atau pembangkang). Dan tugas seorang anggota polis dan seorang gangster muncul dengan ketat antara pembebasan karya-karya Parsons dan Golovach, dan di tempat yang sangat tidak dijangka – di Olimpik Matematik Moscow, dalam pilihan kelas 9 dan 10. Ia tidak begitu jelas sama ada pengarang masalah itu mengetahui tentang penggubalan yang lebih umum, atau sama ada ini ternyata menjadi satu kebetulan.

Sejak bertahun-tahun, tugas itu telah memperoleh pelbagai pilihan dan generalisasi. Jadi, bibliografi beranotasi mengenai isu ini, yang diterbitkan pada tahun 2008 dalam jurnal khas Sains Komputer Teoritis, mengandungi 172 jawatan, dan pada tahun 2011 terdapat kursus latihan berasingan untuk pelajar – "The Game of Cops and Robbers on Graphs".


Like this post? Please share to your friends:
Tinggalkan Balasan

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