Случайный трамвай посреди незнакомого города

, , . , , , . , , .

, ,

, , , 17. , ?



, 1 N , .



« » , . , , , , 34, "x2" 17. «»: 17. , - . , 17 34, "x1" "x2" — , , , .







- ? , , . , 30 . «30» — ? , 1000 , 999 30 , — 17. , 30- , 17- — ? , , , , , , , , - .

, , , .

, ,

, .



: , , , . , , , , , . , : . ?



, :

1. .
2. , , .
3. , , . «1» «2», , «3», «4», «5» «6» — .
4. , . , «», , «» — .

1) , . , , , 1). , , , 1) , .



, 2) «», , , , .



, . , , , 1/3, , , — 2/3. , 3) — , . , . , , , 1000 , , , $$$333-4\sqrt{1000\cdot 1/3\cdot 2/3}$, $$$333-60$, . , 3), , .



, : , , 50%. , , , . , . 4) , , .



, , . , , , , 4. , , - .

«»

, , : , - , , , . , , , , . , , .



: « , ?»







« » , "x1" "x2".



, . , $$$N$ . $$$1$ $$$N$ $$$k$, .



"x1" $$$V$ $$$N$ $$$k$. , $$$k$ $$$N$, , $$$V$ $$$2N$. : $$$V$, $$$k$, , $$$N/2$. $$$k$ $$$N/2$ $$$N$ 50%, — . , "x1" () , .



, "x2". , $$$k$, $$$V$ $$$2k$. , $$$2N$, , , $$$N/2$. , $$$V$ $$$N/2$, $$$k$ , $$$N/4$. $$$N$ 4- $$$1/4$, — . , "x2", , () 3/4 , .







, , , , $$$N$, $$$V$ $$$k$ , , . , . , , 0 π, . .



, $$$N$ , . $$$[0,N]$. $$$k$ , . , $$$V$ $$$N$, , $$$N$ , , . , , , $$$N$ .



, "x1" - 50%, "x2" — 75% , , .

- . , , , , $$$V$ , $$$f(k)$, $$$f()$ — , $$$(0,+\mathrm{\infty })$.



, $$$k_1$, — $$$k_2$, $$$k_1<k_2$. , , . , $$$k_1<k_2$ $$$f(k_1)<f(k_2)$, , $$$f()$ . , «» $$$k_1$ $$$k_2$ $$$V_1=f(k_1)$ $$$V_1=f(k_2)$ , , $$$f()$ .



, ,

$$$f()$. , $$$V$ ( ), $$$N/2\le f(k)\le 2N$. $$$k$ $$$N$, : $$$2k\le 2N$. , , $$$k$, $$$N$ $$$V$ $$$2k$. , $$$V$ $$$2k$, , , $$$V$ , «». , $$$f(k)$, $$$k>0$

$$$f(k)\ge 2k$.







, .



, $$$N$, $$$k$ — () , $$$V=f(k)$ — $$$N$. , , $$$V$ $$$N$? $$$V$, , — $$$2N$, — $$$N/2$.



$$$f()$ , $$$f^{-1}\left(v\right)$, . $$$f()$ $$$f(k)\ge 2k$, $$$f^{-1}()$ : $$$f^{-1}\left(v\right)\le 1/2v$ ( 1)





. 1



, $$$k$, $$$V$ , $$$k_{sup}=f^{-1}\left(2N\right)$. , $$$f^{-1}\left(\right)$ $$$k_{sup}=f^{-1}\left(2N\right)\le 2N$. , $$$k$, $$$V$ , $$$k_{inf}=f^{-1}\left(N/2\right)$. , $$$V$ $$$N$ ( ) , $$$k$ $$$k_{inf}$ $$$k_{sup}$. , $$$p_{success}(f,N)$, :

$$

:

$$

, $$$f$ , $$$\overline{N}$ $$$p_{success}(f,N)$. , , $$$f(k)$, :

$$

, $$$\rho \left(f\right)$, , $$$\phi (k)$ , :

$$

.

, , $$$\phi (k)$,

$$

,

$$$(0,+\mathrm{\infty })$, $$$l(k)=2k$. , ? , , . .







, , — , $$$f(k)=\lambda \cdot k$ ( $$$\lambda$ — ≥2) (*) . $$$f(k)=\lambda \cdot k$ $$$f^{-1}\left(v\right)={\lambda }^{-1}\cdot v$, $$$p_{success}$, :

$$

, $$$p_{success}$ $$$N$ , $$$\lambda$. , $$$f(k)=\lambda \cdot k$, $$$\lambda \ge 2$ (*), $$$l(k)=2k$.



, , , , , , — $$$\phi$ ?



$$$V$ $$$V_{cm}=f_{cm}(k_{cm})$, $$$V_m$ $$$k_m$ — , , :

$$

$$$A$ $$$B$, $$$A$ $$${\mu }_{AB}$. $$$V(k)$ $$$A$, $$$B$. $$$f_A(k_A)$ — $$$A$, $$$f_B(k_B)$ — $$$B$, :

$$

, $$$f_A(t)$ $$$f_B(t)$ ($$$t$ — ).



, , - , ? , ! , $$$\mu >0$ $$$\phi (t)$, $$$(\ast )$, $$$\psi (t)=\mu \cdot \phi ({\mu }^{-1}\cdot t)$ $$$(\ast )$. $$$\phi (t)$ $$$(\ast )$ , $$$t>0$ $$$\mu >0$ :

$$

$$$\mu =t$, $$$\phi$:

$$

, : , $$$\phi (t)$ $$$f(k)=\lambda \cdot k$, , $$$(\ast )$ $$$l(k)=2k$. "x2"?



: x2



, , , $$$l(k)=2k$, . , , .



$$$f(k)$, $$$f(k)\le 2k$, $$$v_0$ , $$$p_{success}\left(f,v_0\right)$.





. 2



$$$f^{\left(-1\right)}\left(v\right)$ $$$A=({v_0/2,f}^{-1}(v_0/2))$ $$$B=({{2v}_0,f}^{-1}({2v}_0))$ ( 2), , $$$Ov$

$$

$$$2/3$- $$$p_{success}\left(f,v_0\right)$. : $$$AB$ $$$i(v)$. $$$(v_0/2,2v_0)$ $$$i(v)$ , , $$$p_{success}\left(f,v_0\right)$ $$$3/2$- .



, $$$f(k)$ $$$l(k)=2k$ $$$p_{success}$, , "x2" .



:

1. $$$f(k)\ge 2k=l(k)$, $$$f^{\left(-1\right)}\left(v\right)\le l^{-1}\left(v\right)=1/2\cdot v$ $$$f^{\left(-1\right)}\left(v\right)$ $$$l^{-1}\left(v\right)$
2. $$$p_{success}\left(l,v\right)$ $$$v$ $$$3/4$, $$$l^{-1}\left(v\right)$ $$$1/2$.

, , $$$f(k)$ $$$l(k)$. , $$$\epsilon >0$ $$$v$ : $$$p_{success}(f,v)\ge 3/4+\epsilon$.



- $$$u_0>0$ $$$f^{\left(-1\right)}\left(v\right)$

$$

, $$$B_0{B}_1{B}_2...B_n...$ - $$$I(v)$. $$$u_0/2,2u_0,8u_0,\dots$ 4 , , $$$v_0/2$ $$$2v_0$. , $$$B_n{B}_{n+1}$ $$$I(v)$ $$$2/3\cdot {inf}_v[p_{success}\left(f,v\right)]\ge 2/3\cdot (3/4+\epsilon )=1/2+2/3\cdot \epsilon$.



$$$l^{-1}\left(v\right)$ $$$1/2$, $$$I(v)$ $$$1/2$ $$$2/3\cdot \epsilon$, $$$I(v)$ $$$u_0$, $$$v$ $$$l^{-1}\left(v\right)$. ( 3)





. 3



, $$$I(v)$ $$$f^{\left(-1\right)}\left(v\right)$, ( 1)) $$$l^{-1}\left(v\right)$. , $$$l\left(k\right)=2k$ .



:



, , , $$$OK$, — . , , , $$$l\left(k\right)=2k$, . .



, $$$f\left(k\right)$, , — $$$l\left(k\right)$. $$$f^{\left(-1\right)}\left(v\right)$ $$$l^{-1}\left(v\right)$, $$$f^{\left(-1\right)}\left(v\right)\le l^{-1}\left(v\right)$, $$$v$, $$$f^{\left(-1\right)}\left(v\right)$ $$$l^{\left(-1\right)}\left(v\right)$. $$$u_0$ $$$v$. , , $$$f^{\left(-1\right)}\left(v\right)$

$$

$$$B_0{B}_1{B}_2...B_n...$ ( 4). , - $$$I(v)$. , , $$$I(v)$ $$$B_n{B}_{n+1}$ $$$2/3\cdot {inf}_v[p_{success}\left(f,v\right)]$. $$$f$ , $$${inf}_v[p_{success}\left(f,v\right)]$ , $$${inf}_v[p_{success}\left(l,v\right)]=3/4$. , , $$$I(v)$ $$$2/3\cdot 3/4=1/2$.





. 4



$$$\mathrm{\Delta }$ $$$l^{\left(-1\right)}\left(u_0\right)-f^{\left(-1\right)}\left(u_0\right)$ : $$$g(v)=l^{-1}\left(v\right)-\mathrm{\Delta }$. $$$g(v)$ :

1. $$$u_0$ $$$g(v)$ $$$I(v)$
2. $$$g(v)$ $$$v$ $$$1/2$

, $$$I(v)$ $$$g(v)$ $$$v$ $$$u_0$ $$$0$. $$$I(v)$ $$$g(v)$ . $$$I(v)$ $$$(0,u_0)$ $$$g(v)$, $$$I(v)$ , $$$g(v)$. , $$$(0,u_0)$ $$$I(v)\le g(v)$.



$$$g(v)=1/2\cdot v+\mathrm{\Delta }$, $$$(0,2\mathrm{\Delta })$ $$$g(v)$ , $$$I(v)\le g(v)$ $$$I(v)$ . $$$I(v)$ — $$$f^{\left(-1\right)}\left(v\right)$, , ($$$f$ $$$k$), $$$I(v)$ . , $$$l\left(k\right)=2k$, .

« » « ». ?



, « » ,

10 . , $$$l\left(k\right)=2k$ - , , . , , , $$$l\left(k\right)=2k+10$. ?



, , . , , , «» «» . , « »?



.





2020

magnolia@bk.ru