Saya mengalami permainan berikut. Saya akan memigrasi ini seperti yang diminta.

• Bug sedang mengunjungi lingkaran, dan musuh ingin memaksimalkan waktu perjalanannya.

• Musuh menempatkan lingkaran di setiap belokan.

• Bug berjalan dari posisi saat ini langsung menuju pusat lingkaran terbaru, lalu berhenti ketika bertemu dengan interior lingkaran (dengan demikian: ia tidak berjalan jika lingkaran dimainkan menutupi lokasinya). Ini giliran bugnya.

• Ada lingkaran $N$ tersedia untuk musuh.

• Setiap lingkaran berikutnya memiliki radius kurang dari lingkaran sebelumnya.

• Setiap lingkaran harus memotong persimpangan dari semua lingkaran yang dimainkan sebelumnya. Artinya, semua lingkaran harus memiliki persimpangan yang sama setelah semua dimainkan.

EDIT: Musuh bebas untuk memilih jari-jari lingkaran, tunduk pada kendala bahwa jari-jari monoton berkurang.

Pertanyaan dan jawaban:

1. Apakah jarak sebagai $N\to\infty$ dibatasi? J: Tidak, contoh strategi musuh diberikan oleh Jawaban ini
2. Berapa jarak maksimum bug yang harus dilalui selama bermain lingkaran $N$A: itu tumbuh di $\Theta(\log(N))$ , dengan jawaban yang sama.

Varian 2 : Bug berjalan langsung ke persimpangan dua lingkaran yang paling baru diputar .

UPDATE: Varian ini ditujukan, dengan asumsi bahwa bug hanya dapat mengingat 2 lingkaran terakhir yang diputar di sini . Hasilnya lagi jarak yang tidak terbatas.

Apa dampak yang dimiliki memori tanpa batas ? yaitu bug pergi ke persimpangan semua lingkaran yang diputar sebelumnya . Ini menghasilkan "longgar" terikat , di mana d adalah diameter lingkaran pertama. Jelas tidak kurang dari ini. Lihat di sini . Batas atas saat ini adalah 1000 × d . Ini diperoleh dengan memperkirakan jalur kasus terburuk sebagai tur keliling lingkaran yang semakin kecil. Terlihat bahwa bug selalu membuat kemajuan menuju persimpangan terakhir, sehingga mengurangi jarak langkah selanjutnya yang harus dilalui.$O(d)$$d$$1000\times d$

Saya menduga jarak yang ditempuh adalah konstanta kecil kali keliling lingkaran pertama, tetapi saya saat ini tidak dapat memberikan bukti yang baik.

Jawaban ini memiliki dua bagian, bersama-sama menunjukkan bahwa batas yang benar adalah :$\Theta(\log N)$

1. Batas bawah (dikalikan jari-jari lingkaran pertama).$\Omega(\log N)$
2. Batas atas yang cocok dari .$O(\log N)$

Batas bawah $\Omega(\log N)$

Pertimbangkan dua unit lingkaran yang menyentuh pada suatu titik . (Lihat di bawah; p di sebelah kanan, bug dimulai di sebelah kiri.) Berganti-ganti antara satu lingkaran dan lainnya. Bug akan bergerak naik-turun zig-zag melintasi celah antara dua lingkaran, sebagian besar bergerak naik dan turun tetapi juga berkembang perlahan ke kanan. Jika saya melakukan trigonometri dengan benar, setelah N langkah, jarak dari titik umum adalah Θ ( 1 / $p$$p$$N$, dan langkahNakan menyebabkan bug berjalanΘ(1/N), untuk jarak totalΘ(logN).$\Theta(1/\sqrt N)$$N$$\Theta(1/N)$$\Theta(\log N)$

Berikut ini sketsa perhitungannya. Pertimbangkan dua langkah berurutan yang dilakukan bug. Dia beralih dari titik , ke b , ke c . Poin a dan c berada di lingkaran yang sama; titik b ada di lingkaran lain. Biarkan o menjadi pusat lingkaran di mana a berada. Pertimbangkan tiga segitiga berikut, dalam urutan ukuran menurun:$a$$b$$c$$a$$c$$b$$o$$a$

1. Segitiga isokel (ingat p adalah titik umum).$\triangle oap$$p$
2. Segitiga .$\triangle abp$
3. Segitiga kecil $\triangle abc$

Segitiga ini hampir mirip (yaitu, skala modulo kongruen). Lebih tepatnya, untuk , ketiganya memiliki properti berikut: rasio panjang kaki pendek dengan kaki panjang adalah Θ ( ϵ ) . (Saya tidak akan membuktikan ini secara lebih rinci di sini, tetapi perhatikan bahwa ϵ → 0 saat bug berjalan, dan dengan mengganggu satu titik pada setiap segitiga dengan jumlah yang dapat diabaikan, segitiga dapat dibuat serupa.)$\epsilon = |ap|$$\Theta(\epsilon)$$\epsilon\rightarrow 0$

Kaki panjang dan p o dari segitiga pertama memiliki panjang 1. Kaki pendek | a p | memiliki panjang ϵ . Segmen sebuah p adalah kaki panjang segitiga kedua, sehingga kaki pendek yang segitiga a b memiliki panjang$co$$po$$|ap|$$\epsilon$$ap$$ab$ . Segmen a b adalah kaki panjang dari segitiga ketiga, sehingga kaki pendek segitiga a c memiliki panjang Θ ( ϵ 3 ) . Dengan demikian, dalam dua langkah ini bug tersebut:$\Theta(\epsilon^2)$$ab$$ac$$\Theta(\epsilon^3)$

1. Jarak bug perjalanan adalah Θ ( ϵ 2 ) .$|ab|+|bc|$$\Theta(\epsilon^2)$
2. Jarak dari bug ke titik umum berkurang dari ϵ ke ϵ - Θ ( ϵ 3 ) .$p$$\epsilon$$\epsilon-\Theta(\epsilon^3)$

Tentukan waktu menjadi jumlah langkah sebelum ε t ≈ 1 / 2 k . Dengan (2) di atas, ϵ berkurang dengan faktor konstan setelah sekitar Θ ( 1 / ϵ 2 ) langkah, jadi t k + 1 = t k + Θ ( 2 2 k ) = t k + Θ ( 4 k ) . Dengan demikian, t k = Θ ( 4 $t_k$$\epsilon_t \approx 1/2^k$$\epsilon$$\Theta(1/\epsilon^2)$$t_{k+1} = t_k + \Theta(2^{2k}) = t_k + \Theta(4^k)$ . Artinya, setelah Θ ( 4 k ) langkah, jarak dari bug ke titik yang sama p akan sekitar 1 / 2 k . Mengubah variabel, setelah N langkah, jarak dari bug ke titik umum adalah ϵ = Θ ( 1 / $t_k = \Theta(4^k)$$\Theta(4^k)$$p$$1/2^k$$N$. Dan, pada langkahN, bug bergerakΘ(ϵ2)=Θ(1/N). Jadi total jarak yang ditempuh dalam pertamaNlangkah adalahΘ(1+1/2+$\epsilon = \Theta(1/\sqrt N)$$N$$\Theta(\epsilon^2) = \Theta(1/N)$$N$ .$\Theta(1+1/2+1/3+...+1/N) = \Theta(\log N)$

Ini adalah batas bawah.

Itu meluas ke Varian 2 yang diusulkan (seperti yang saya mengerti), sebagai berikut:

Menambahkan batasan bahwa bug harus pindah ke titik terdekat di persimpangan dua lingkaran yang paling baru ditempatkan tidak membantu. Artinya, batas bawah atas masih berlaku. Untuk mengetahui alasannya, kami akan memodifikasi contoh di atas dengan menambahkan lingkaran asing yang memungkinkan bug memenuhi batasan saat masih menempuh jalur yang sama:$\Omega(\log N)$

Lingkaran hijau dan biru adalah dua lingkaran dari contoh di atas. Titik potong dan b adalah sama dengan a dan b seperti pada contoh di atas. Lingkaran merah adalah lingkaran "asing" yang baru. Urutan sebelumnya berganti-ganti antara lingkaran biru dan hijau. Urutan baru akan menjadi urutan ini, tetapi dengan lingkaran merah ditambahkan sebelum setiap lingkaran dalam urutan lama: merah, biru, merah, hijau, merah, biru, merah, hijau, merah, biru, ...$a$$b$$a$$b$

Misalkan bug tersebut duduk di setelah biru ditempatkan. Lingkaran selanjutnya yang ditempatkan berwarna merah. Merah mengandung bug, sehingga bug tidak bergerak. Lingkaran berikutnya yang ditempatkan berwarna hijau. Sekarang bug bergerak ke b (yang merupakan titik terdekat di persimpangan lingkaran hijau dan merah). Dengan mengulangi ini, bug berjalan seperti sebelumnya.$a$$b$

Batas atas $O(\log N)$

Saya hanya membuat sketsa buktinya.

Perbaiki urutan lingkaran apa pun. Kami akan berpendapat bahwa sebagai , jarak total yang ditempuh oleh bug dilangkah-langkah N pertamaadalah O ( log N ) . Asumsikan tanpa kehilangan keumuman bahwa lingkaran pertama memiliki jari-jari 1.$N\rightarrow \infty$$N$$O(\log N)$

Memperbaiki sewenang-wenang besar . Biarkan p pada titik mana pun di persimpangan lingkaran N pertama . Perhatikan bahwa karena cara bug bergerak, pada setiap langkah bug bergerak semakin dekat ke hal .$N$$p$$N$$p$

Pertama, pertimbangkan langkah-langkah di mana rasio berikut setidaknya : pengurangan jarak ke $1/\log N$ Total jarak yang ditempuh dalam langkah-langkah tersebut adalahO(logN), karena total jarak yang ditempuh dalam langkah-langkah tersebut adalahO(logN

Pertama, kami berpendapat sesuatu yang sedikit lebih lemah: bahwa jarak total yang ditempuh dalam langkah-langkah tersebut sebelum jari-jari lingkaran berkurang menjadi 1/2 atau kurang adalah . (Kami tunjukkan nanti ini sudah cukup untuk memberi batas.)$O(\log N)$

Pertimbangkan langkah seperti itu. Biarkan dan b , masing-masing, menunjukkan lokasi bug sebelum dan sesudah langkah. Biarkan o menunjukkan pusat lingkaran saat ini. Biarkan b ′ menunjukkan titik pada ray → p b sedemikian rupa sehingga | p a | = | p b | :$a$$b$$o$$b'$$\overrightarrow{pb}$$|pa| = |pb|$

Pertimbangkan segitiga-segitiga berikut:

1. $\triangle opb$
2. $\triangle pba$
3. $\triangle abb'$

Dengan argumen geometris yang mirip dengan yang ada di batas bawah, untuk beberapa , masing-masing segitiga ini memiliki dua kaki panjang dan satu kaki pendek, dan rasio (untuk setiap segitiga) dari panjang kaki pendek dengan panjang kaki panjang adalah Θ ( ϵ ) : | b b ′ $\epsilon$$\Theta(\epsilon)$

Persamaan ini dan asumsi bahwa , Yang merupakan jari-jari lingkaran, dalam [ 1 / 2 , 1 ] menyiratkan bahwa | a b | = Θ ( | p a | 2 / | b o | ) = Θ ( | p a | 2 ) , dan kemudian itu | b b $|bo|$$[1/2,1]$$|ab| = \Theta(|pa|^2/|bo|) = \Theta(|pa|^2)$ .$|bb'| = \Theta(|ab||pa|/|bo|) = \Theta(|pa|^3)$

Sekarang kita fokus pada jarak bug ke . Sebut saja d sebelum langkah, dan d ′ setelah langkah. (Catatan d = | p a | , d ′ = | p b | , dan d - d ′$p$$d$$d'$$d=|pa|$$d'=|pb|$ .)$d-d' = |bb'|$

Pada langkah ini, jarak ini dikurangi dengan | b b ′ | , yang dengan pengamatan di atas adalah Ω ( d 3 ) .$d$$|bb'|$$\Omega(d^3)$

Dengan demikian, jumlah langkah tambahan yang diperlukan untuk mengurangi jarak dengan faktor 2 (paling banyak ) adalah O ( 1 / d 2 ) . Mengubah variabel, jika d = 1 / 2 k , jumlah langkah tambahan yang diperlukan untuk membawa jarak di bawah 1 / 2 k + 1 adalah O ( 4 k ) . Karena jumlahnya adalah geometris, jumlah langkah yang diperlukan untuk membawa jarak di bawah 1 / 2 k adalah O $d/2$$O(1/d^2)$$d=1/2^k$$1/2^{k+1}$$O(4^k)$$1/2^{k}$adalah O ( 1 / $O(1/4^k)$. Mengubah variabel lagi, setelah langkah, jarak ke $n$$p$.$O(1/\sqrt n)$

Akhirnya, mengingat persamaan yang ditampilkan beberapa paragraf ke atas, pada langkah ke- , jarak yang ditempuh bug, yaitu | a b | , adalah O ( ( jarak saat ini ke  p ) 2 ) = O ( 1 / n ) . Dengan demikian, total jarak yang ditempuh dalam pertama N langkah-langkah seperti saat jari-jari lingkaran dalam [ 1 / 2 , 1 ] adalah paling N Σ n ) = O $n$$|ab|$$O((\mbox{the current distance to } p)^2) = O(1/n)$$N$$[1/2,1]$

Dengan scaling, kami menyimpulkan bahwa, untuk setiap , total jarak yang ditempuh sedangkan jari-jari lingkaran adalah dalam kisaran [ 1 / 2 k , 1 / 2 k + 1 ] adalah O ( log ( N ) / 2 k ) . Menjumlahkan lebih dari k , jarak total yang ditempuh adalah O ( log N ) . QED$k$$[1/2^k, 1/2^{k+1}]$$O(\log(N)/2^k)$$k$$O(\log N)$

David E. menduga

"Mungkin jawabannya akan berbeda jika bug berjalan langsung ke titik terdekat di persimpangan saat ini, daripada menuju pusat lingkaran baru?"

(EDIT: Perhatikan bahwa ini tidak sama dengan "varian 2" di akhir pertanyaan pengirim asli.)

Inilah bukti (kurang lebih) dari dugaannya (itu dibatasi dalam kasus ini).

Kata pengantar singkat. Untuk varian yang disarankan oleh David, jarak total yang ditempuh oleh bug selalu , di mana d $O(d_0)$$d_0$ adalah jarak maksimum antara bug dan setiap titik di lingkaran pertama yang ditempatkan.

bukti. Asumsikan WLOG bahwa tempat peristirahatan terakhir adalah asal , dan bahwa bug dimulai pada jarak 1 dari o . Untuk eksposisi asumsikan bug dimulai pada waktu $o$$o$$0$ , bergerak pada tingkat unit (satu inci per detik), dan berhenti hanya ketika mencapai disk terakhir yang ditempatkan. Perhatikan bahwa (seperti yang dijelaskan lebih lanjut di bawah) saat bug merayapi jaraknya ke titik asal dikurangi secara ketat.

Partisi disk unit-radius (berpusat pada ) ke dalam banyak cincin tanpa batas dengan menggambar lingkaran konsentris jari-jari 1 , 0,99 , 0,99 2 , 0,99 3 , … .$o$$1, 0.99, 0.99^2, 0.99^3, \ldots$

Klaim. Di dalam lingkaran jari-jari (luar) , bug tersebut melakukan perjalanan paling banyak 10 $d$$10 d$ unit.

Sketsa bukti. Tanpa kehilangan keumuman (dengan penskalaan) mengasumsikan jari-jari luar adalah 1. Asumsikan untuk kontradiksi bahwa bug menghabiskan lebih dari 10 detik di cincin ini sebelum pindah ke cincin berikutnya (dari jari-jari luar 0,99). Kapan saja , pertimbangkan sudut α ( t $t$$\alpha(t)$ dibentuk oleh dua vektor berikut: vektor yang menunjuk dari bug ke arah perjalanan bug, dan vektor yang menunjuk dari bug ke asal.

Bug selalu bergerak menuju titik terdekat di persimpangan cakram yang ditempatkan sejauh ini, dan persimpangan itu adalah cembung dan berisi asal. Oleh karena itu, sudut $\alpha(t)$ selalu benar-benar kurang dari sembilan puluh derajat, dan jarak dari bug ke titik asal sangat menurun.

Setiap kali sudut adalah, katakanlah, kurang dari delapan puluh sembilan derajat, jarak ke asal menurun pada tingkat minimal 1 / 100 . Tapi, selama seluruh waktu di ring, jarak ini berkurang kurang dari 1 / 100 , sehingga jumlah total waktu yang dihabiskan di ring ketika α ( t ) < 89 adalah paling 1 detik. Jadi, setidaknya 9 detik dihabiskan dengan sudut α ( t ) setidaknya 89 derajat dan paling banyak 90 derajat. Sekarang pertimbangkan waktu seperti itu t . Karena $\alpha(t)$$1/100$$1/100$$\alpha(t) < 89$$9$$\alpha(t)$$t$ , dan cincin memiliki lebar 1 / 100 , bug tersebut berpergian baik jelas searah jarum jam di sekitar ring, atau jelas berlawanan arah jarum jam.$\alpha(t) \in [89,90]$$1/100$

Biarkan menunjukkan titik bahwa bug bergerak ke arah (titik terdekat di persimpangan disk yang ditempatkan sejauh ini). Saat bug bergerak ke arah p , pertimbangkan garis melalui bug dan tegak lurus dengan arah gerakan bug. Baris ini memisahkan pesawat menjadi dua bidang setengah, satu "di depan" bug (berisi p dan persimpangan cakram), dan yang lainnya "di belakang" bug. Tandai titik-titik di setengah bidang di belakang bug mati$p$$p$$p$ --- bug tidak pernah dapat kembali ke titik mana pun setelah ditandai mati (karena titik tersebut tidak berada di persimpangan disc).

Sejak , dan cincin memiliki radius 1 dan lebar 1 / 100 , hampir setengah dari poin di ring berada di belakang bug dan mati, termasuk poin segera balik bug. Bug tidak dapat kembali ke titik-titik tersebut, jadi, jika bug awalnya bepergian, katakanlah, searah jarum jam, maka bug tidak dapat "berbalik" dan mulai bepergian berlawanan arah jarum jam (lebih dari katakan, 1 detik). Dengan demikian, dari 10 detik, bug harus menghabiskan setidaknya 8 detik bepergian searah jarum jam. Tetapi lingkar cincin adalah 2 π < $\alpha(t) \in [89,90]$$1/100$$1$$10$$8$$2\pi< 7$, setengah dari cincin sudah mati segera setelah bug dimulai, dan bug tidak dapat kembali ke titik mati mana pun, jadi ini tidak mungkin. Ini membuktikan klaim (lebih atau kurang; mungkin seseorang dapat memberikan argumen yang lebih tepat).

Dengan klaim, jarak total perjalanan (dalam semua cincin) adalah paling

Jelas faktor konstan di sini longgar. Misalnya, jika bug bergerak dalam deringan pertama pada sudut 89 derajat atau lebih, ini segera membunuh hampir setengah titik pada cakram jari-jari 1 (bukan hanya titik-titik pada satu deringan itu).