Clever Geek Handbook

Bonde aleatório no meio de uma cidade desconhecida





Há um problema bastante curioso, que há muito tempo foi incluído no folclore matemático e também se tornou um teste favorito em entrevistas. Suas condições são simples e a solução parece sugerir-se, mas não vamos tirar conclusões precipitadas. Pegue um lápis, uma folha de papel em branco, sente-se e vamos descobrir.



Qual, de fato, é a tarefa



Então, imagine que você chegou a uma cidade completamente desconhecida e o primeiro bonde que encontrou lá era o número 17. Como você pode estimar quantas linhas de bonde existem nesta cidade?



Para simplificar, considere que as rotas do bonde na cidade são numeradas sem lacunas com números de 1 a N, e inicialmente cada um desses números com chances iguais poderia ser o número do bonde que você veria primeiro.



Pela primeira vez ouvi o problema do "bonde acidental" de Nikolai Nikolaevich Vasiliev, meu amigo matemático de São Petersburgo. Em seguida, ele compartilhou comigo a observação de que, entre aqueles a quem ele contou esse problema, e depois pediu uma resposta sem hesitação, a maioria das pessoas ligou para o número 34, ou seja, " x2 " de 17. Na minha experiência, o mais extravagante foi a resposta do meu amigo com “Mechmat”: 17. Apenas uma semana depois percebi que ele foi movido pelo princípio da maximização da probabilidade, que estava dormindo em algum lugar no subcórtex de seu cérebro. Ok, mas 17 e 34, em outras palavras " x1 " e " x2 ", são respostas ingênuas e impensadas, mas qual é a resposta correta e, em geral, esse problema tem uma?



Armadilhas e o reino da fantasia



Por que vale a pena duvidar da existência de uma resposta universalmente correta? Essa ideia é fácil de chegar se você considerar vários universos simples, embora fictícios. Por exemplo, imagine que existem exatamente 30 rotas de bonde em cada cidade da Terra. "30" será a única resposta correta neste universo? Agora imagine que em outro universo existem 1000 cidades na Terra, e em 999 delas existem 30 rotas de bonde, e no restante - há exatamente 17 delas. Qual resposta será a correta desta vez e como será afetada pelo fato de cidades com São muitas 30 rotas, mas com 17 só há uma? Devo dizer desde já que é muito difícil usar aqui considerações probabilísticas, porque a pessoa que é solicitada a estimar o número de rotas não sabe se a cidade que agora está visitando foi escolhida por acaso no mapa,ou há alguma razão nesta escolha e há o cálculo de alguém.



O princípio do pessimismo matemático extremo



Apesar das dificuldades declaradas, na matemática existe um princípio com o qual se pode dar uma resposta para o nosso problema, que permanece significativo mesmo nos mundos mais bizarros.

Quando se trata de jogos, esse princípio é chamado de maximização de ganhos garantidos

e , para entender sua essência, vamos dar uma olhada em um exemplo simples.



Imagine um jogo: secretamente de você com um dos meus punhos, escondo um pequeno objeto, que seja uma ervilha seca, depois estico os braços para a frente e peço que adivinhe em qual está essa ervilha Deixe-nos ter tempo para jogar uma longa série de jogos, e inicialmente você não sabe se estou tentando vencê-lo, estou tentando sucumbir deliberadamente ou permaneço indiferente ao seu sucesso. Digamos que seu objetivo seja ganhar o máximo de jogos possível. Qual estratégia você deve seguir neste caso?



Primeiro, vamos tentar analisar as vantagens e desvantagens das seguintes quatro estratégias simples:



  1. Sempre escolha sua mão direita.
  2. Comece com a mão direita e depois escolha a mão em que a ervilha foi encontrada pela última vez.
  3. , , . «1» «2», , «3», «4», «5» «6» — .
  4. , . , «», , «» — .


Se você decidir usar a estratégia 1) e ao mesmo tempo eu sempre esconder uma ervilha em minha mão direita, todos os jogos terminarão a seu favor. Podemos dizer que o cenário do desenvolvimento do partido, em que escondo uma ervilha exclusivamente na mão direita, é o melhor para 1) . No entanto, no meu pior cenário, um cenário em que escondo uma ervilha exclusivamente na minha mão esquerda, estratégia 1), não permitirá que você ganhe um único jogo, não importa quanto tempo nosso jogo seja.



É fácil adivinhar que a estratégia 2) sofre do mesmo "vício", ou seja, no pior cenário para ela, quando eu começo com minha mão esquerda e depois alterno as mãos em cada um dos jogos seguintes, ela não permitirá que você ganhe uma única vez, por mais nossa festa durou.



Agora, vamos descer à estratégia que vem em terceiro lugar em nossa lista. Se você usá-lo, suas chances de ganhar em todos os jogos em que a ervilha estiver escondida em sua mão direita serão de 1/3, e em jogos em que a ervilha estiver em sua mão esquerda - 2/3. É claro que o pior cenário para 3) é quando tenho o hábito de esconder uma ervilha exclusivamente na mão direita. No entanto, mesmo neste caso, em qualquer conjunto de jogos suficientemente longo, cerca de um terço deles terminará em sua vitória. Teoricamente, é claro, você pode não ter sorte e nunca adivinhará a mão certa, mas na prática, digamos em um jogo de 1000 jogos, é quase impossível que o número de suas vitórias seja menor que$ 333-4 \ sqrt {1000 \ \ cdot1 / 3 \ cdot2 / 3} \ $, isto é, menos que $ 333 - $ 60, e em um jogo de um milhão de jogos, a possível porcentagem de diferenças será ainda menor. Na verdade, ao escolher a estratégia 3), você garante a si mesmo que cerca de um terço dos jogos do partido permanecerá com você.



Se você usou a quarta estratégia da lista, então nosso jogo adquire uma característica interessante: na verdade, deixa de ser importante para você, desta vez escondi a ervilha na mão direita ou coloquei na esquerda, pois em ambas as situações suas chances de ganhar serão as mesmas e será exatamente 50%. Você pode até dizer que qualquer sequência de mãos que eu delineei onde vou esconder uma ervilha será o melhor e o pior cenário para o desenvolvimento da festa para você. Acontece que, em qualquer caso, em um lote bastante longo de jogos, cerca de metade deles deve terminar com a sua vitória. Nesse sentido, a estratégia 4) oferece as maiores garantias em comparação com todas as outras estratégias que já consideramos aqui.



O princípio de maximizar o payoff garantido prescreve que você enumere todas as estratégias possíveis do jogo, para cada uma delas calcular o valor do payoff no pior cenário para ele e declarar a estratégia ótima para a qual o valor desse payoff será o maior. Pode-se mostrar que no jogo de adivinhar a localização da ervilha, o ótimo, e não apenas o melhor da lista, é a estratégia número 4. Em essência, maximizar a vitória garantida é semelhante ao credo de vida daquelas pessoas que sempre tendem a esperar o pior, mas ainda assim tentando melhorar de alguma forma sua posição na vida.



O problema de um bonde "aleatório" assume sua forma final



Formalismo



Para usar o princípio de maximizar os ganhos garantidos, imagine que o destino está jogando um jogo com você: ele o envia repetidamente para uma cidade desconhecida localizada em algum universo desconhecido, espera até que você encontre o primeiro bonde lá e, em seguida, pergunta quanto o mesmo nesta cidade, existem apenas linhas de eléctrico. Assumiremos que sua resposta é considerada aceitável e o jogo termina a seu favor, se apenas o número que você nomeou difere menos de duas vezes do verdadeiro, tanto para cima quanto para baixo. Também assumiremos que se trata de um lote muito longo de jogos, que durará uma vida inteira.



Agora é bastante legítimo fazer a pergunta: "Qual estratégia no jogo descrito será ideal para você no sentido de que pode fornecer o número máximo de respostas aceitáveis ​​garantidas?"



Uma análise detalhada das estratégias mais simples



Como uma "primeira batalha" com o problema recém-proposto, vamos tentar descobrir o quão boas as estratégias ingênuas " x1 " e " x2 " são para ele .



Então, o destino nos jogou em outra cidade desconhecida. Como antes, a carta$ N $indica o número de linhas de bonde nesta cidade. Por condição, todos os números de$ 1 $ antes $ N $ com igual probabilidade pode ser um número de rota $ k $, que será seguido pelo primeiro bonde que avistamos.



De acordo com a estratégia " x1 "$ V $ para o número $ N $ deve ser por si só $ k $... É claro que$ k $ nunca mais $ N $, então não pode acontecer que $ V $ foi mais $ 2N $... Portanto, nossa estimativa será inaceitável apenas em um caso: se$ V $, ou seja $ k $, acaba sendo menor que $ N / 2 $... Probabilidade de obter$ k $ Menos $ N / 2 $ com estranho$ N $não exceda 50%, e até mesmo - igual a eles. Segue-se que ao usar a estratégia " x1 " em um conjunto muito longo de jogos, pelo menos (aproximadamente) metade das estimativas feitas são garantidas como aceitáveis, não importa o cenário que o destino possa ter.



Agora, suponha que decidimos usar a estratégia " x2 ". De acordo com as regras desta estratégia, quando você vê o número do bonde$ k $, devemos como $ V $ diga o número $ 2k $... Como no caso anterior, nossa estimativa nunca ultrapassará$ 2N $e, portanto, será considerado inaceitável apenas sob uma condição, se seu valor for menor que $ N / 2 $... Ao mesmo tempo,$ V $ será menos $ N / 2 $, somente se o número do bonde $ k $ será menos que $ N / 4 $... A probabilidade do último evento para cidades com$ N $ múltiplo de 4 é igual a $ 1/4 $, e menos ainda para outras cidades. Portanto, se decidirmos aderir à estratégia " x2 ", então ganhamos a garantia de que em qualquer jogo longo de pelo menos (aproximadamente) 3/4 de todas as nossas respostas serão aceitáveis, não importa o quão mal o destino se comporte conosco.



Dos espinhos às estrelas



Antes de prosseguir para a parte principal da história, onde estamos procurando estratégias ótimas, vou modificar ligeiramente as condições do problema e assumir que$ N $, $ V $ e $ k $agora pode assumir não apenas o natural, mas também quaisquer valores reais maiores que zero. Essa etapa é necessária para se livrar das advertências irritantes e da enumeração enfadonha de casos especiais associados à discrição. Claro, agora ainda é difícil imaginar uma cidade que tenha bondes com todos os números de 0 a π, mas isso não é necessário para você. Nosso problema em sua nova modificação contínua tem um modelo simples e bastante realista.



Imagine que alguém tirou uma longa tira de filme fotográfico$ N $cm e resolvi observar como as partículas vindas do espaço vão deixar sua marca nele. Na escala do experimento, a densidade de probabilidade de partículas atingirem o filme será descrita por uma distribuição uniforme ao longo do intervalo$ [0, \, N] $... Neste experimento, o experimentador informa a distância$ k $entre a borda esquerda do filme e o ponto onde a primeira partícula registrada atingiu. Como antes, você deve dar uma classificação aceitável$ V $ para desconhecido para você $ N $, ou seja, uma estimativa que difere de $ N $não mais do que duas vezes, tanto para cima quanto para baixo. Como antes, o destino joga com você um longo jogo de jogos, cada vez decidindo o que será$ N $em outro jogo.



Como um exercício simples, mostre que, apesar das condições alteradas, a estratégia " x1 " ainda garante cerca de 50%, e os estrategistas " x2 " - os mesmos cerca de 75% das estimativas aceitáveis, respectivamente, independentemente do cenário escolhido pelo destino.



Caminho longo para a perfeição



Pré-triagem



Finalmente, todos os preparativos estão concluídos e nesta seção podemos começar a procurar as estratégias ideais. Para simplificar, no entanto, não consideraremos todas as estratégias, mas nos restringiremos àquelas em que a estimativa$ V $ imagine como $ f (k) $Onde $ f () $ É alguma função de valor real definida no intervalo $ (0, \ + \ infty) $...



Imagine agora que, em um experimento, a distância do ponto de impacto da partícula até a borda esquerda do filme fosse igual a$ k_1 $, e em outro experimento - $ k_2 $, e $ k_1 <k_2 $... Não seria razoável dar uma estimativa menor para a duração do filme no primeiro experimento do que no segundo? Se sim, então a partir da desigualdade$ k_1 <k_2 $ a desigualdade deve sempre seguir $ f (k_1) <f (k_2) $em outras palavras, a função $ f () $deve ser estritamente crescente. Não é menos razoável supor que para aqueles "próximos" em valor$ k_1 $ e $ k_2 $ avaliações $ V_1 = f (k_1) $ e $ V_1 = f (k_2) $ também deve estar próximo, ou seja, a função $ f () $deve ser contínuo.



Se analisarmos quais respostas consideramos aceitáveis, teremos outra

restrição$ f () $... Veja, em nossa compreensão do problema$ V $ aceitável se (e somente se) $ N / 2 \ le f (k) \ le2N $... Distância$ k $ entre o ponto iluminado por uma partícula cósmica e a borda esquerda do filme fotográfico nunca excede o comprimento do filme $ N $, daí obtemos diretamente a desigualdade: $ 2k \ le2N $... A partir da última desigualdade, segue-se que não seria razoável aprender com o experimentador a distância$ k $, Avalie $ N $ número $ V $ menor $ 2k $... Na verdade, se aumentarmos a estimativa$ V $ antes $ 2k $, então definitivamente não o faremos excessivamente grande, no entanto, nos casos em que $ V $era originalmente inaceitavelmente pequeno, tal redefinição pode até "consertá-lo". Assim, no processo de busca de estratégias ótimas, basta considerarmos apenas essas funções$ f (k) $, cujos valores para todos $ k> 0 $ sujeito à desigualdade

$ f (k) \ geq2k $...



Fórmula de Sua Majestade



Agora vamos tentar expressar o valor do ganho garantido na forma de alguma fórmula analítica geral para uma estratégia arbitrária.



Então, no próximo experimento de registro de partículas cósmicas, um filme fotográfico de comprimento$ N $, $ k $ - remoção do ponto de impacto da primeira partícula de sua borda esquerda (filme), e $ V = f (k) $ - nossa estimativa para $ N $... Deixe o experimento apenas ter que acontecer, qual é então a probabilidade de que$ V $ será aceitável para $ N $? O maior valor$ V $, quando ainda é considerado aceitável, é $ 2N $, o menor é $ N / 2 $...



Porque o$ f () $ é estritamente crescente e contínuo, então há uma função inversa $ f ^ {- 1} \ left (v \ right) $, que também é estritamente crescente e contínuo. Para valores$ f () $ em todos os lugares a desigualdade $ f (k) \ geq2k $, então para os valores $ f ^ {- 1} () $ a dupla desigualdade deve ser satisfeita: $ f ^ {- 1} \ left (v \ right) \ le 1/2 v $(fig. 1)





fig. 1



Agora é fácil descobrir que o valor máximo$ k $além de que $ V $ torna-se inaceitavelmente grande, é $ k_ {sup} = f ^ {- 1} \ left (2N \ right) $... Isso decorre do fato de que$ f ^ {- 1} \ left (\ right) $ aumenta estritamente e $ k_ {sup} = f ^ {- 1} \ left (2N \ right) \ le 2N $... Da mesma forma, o valor mínimo$ k $menos do que $ V $ torna-se inaceitavelmente pequeno, é $k_{inf}=f^{-1}\left(N/2\right)$... Das duas últimas afirmações, segue-se que$V$ será aceitável em relação a $N$ se (e somente se) a distância $k$ entre o ponto exposto e a borda esquerda do filme será colocado entre $k_{inf}$ e $k_{sup}$... A probabilidade do último evento, nós a denotamos como$p_{success}(f,\ N)$, é igual a:

$\frac{k_{sup}-\ k_{inf}\ }{N}$



ou em mais detalhes:

$p_{success}(f,\ N)=\ \frac{f^{-1}\left(2N\right)-\ f^{-1}\left(N/2\right)\ }{N}$



Deve ser óbvio que o pior para $f$ o cenário será uma sequência de tais experimentos, em cada um dos quais a duração do filme fotográfico $\bar{N}$ minimiza o valor $p_{success}(f,\ N)$... Segue-se que, em sequências muito longas de experimentos, a fração de respostas aceitáveis ​​garantida pela estimativa$f(k)$, será dado pela expressão:

${\rho\left(f\right)={inf}_N[\ p}_{success}(f,\ N)]$



Podemos agora argumentar que qualquer estratégia ideal deve maximizar $\rho\left(f\right)$, em outras palavras, $\varphi(k)$ será ideal se e somente se:

${inf}_N[p_{success}\left(\varphi,\ N\right)]={sup}_f\ {inf}_N[p_{success}\left(f,\ N\right)]$

...

Assim, o problema de encontrar estimativas ótimas foi reduzido à questão de como a função se parece$\varphi(k)$que entrega a expressão

$(*)\ \ \ \ \ \ inf_N\left[\frac{f^{-1}\left(2N\right)-f^{-1}\left(N/2\right)}{N}\right]$



o máximo na classe de todas as funções contínuas fortemente crescentes definidas

no intervalo$(0,+\infty)$cujos gráficos não são inferiores a $l(k)=\ 2k$... Não é verdade que neste cenário a tarefa pode parecer assustadoramente difícil? Acho que isso vai parecer inesperado para você, mas a resposta é extremamente simples. Vamos tentar adivinhar juntos.



A arte do raciocínio plausível



Talvez a coisa mais simples para começar seja descobrir qual função da forma$f(k)=\ \lambda\cdot k$ (aqui $\lambda$- qualquer número real ≥2) dá à expressão (*) o valor mais alto. Reverter para$f(k)=\ \lambda\cdot k$ serve a função $f^{-1}\left(v\right)=\lambda^{-1}\cdot v$, substituindo-o na expressão de $p_{success}$, temos:

$p_{success}\left(N,\lambda\right)=\ \frac{\lambda^{-1}\cdot2N-\lambda^{-1}\cdot N/2}{N}=\frac{3}{2}\ \cdot\ \lambda^{-1}\ $



Como você pode ver, $p_{success}$ não depende de $N$ e assume quanto maior o valor, menor foi $\lambda$... Assim, na classe de função$f(k)=\ \lambda\cdot k$, $\lambda\geq2$ o maior valor para a expressão (*), é dado pela função já familiar para nós $l(k)=\ 2k$...



Agora vamos pensar no que acontece se medirmos a distância não em centímetros, mas, digamos, em metros, polegadas ou anos-luz - como então a forma da função mudará$\varphi$estimativa ideal?



Deixe a estimativa em centímetros$V$ tem a forma $V_{cm}=\ f_{cm}(k_{cm})$e $V_m$ e $k_m$ - as mesmas quantidades expressas em metros, então:

$V_m=\frac{1}{100}V_{cm}=\frac{1}{100}f_{cm}({100\cdot k}_m)=\ f_m(k_m)$



Em geral, vamos lidar com a escala de comprimento $A$ e escala de comprimento $B$que é obtido de $A$ multiplicando pelo coeficiente $\mu_{AB}$... Cada pontuação$ V (k) $ pode ser calculado como em unidades de escala $ A $, e em unidades de escala $ B $... Deixe ser$ f_A (k_A) $ - sua representação em unidades de escala $ A $e $ f_B (k_B) $ - representação em unidades de escala $ B $, então:

$ f_B (t) = \ mu_ {AB} \ cdot f_A ({\ mu_ {AB}} ^ {- 1} \ cdot t) $



A forma da última equação indica que as funções $ f_A (t) $ e $ f_B (t) $ provavelmente diferente ($ t $neste caso, é uma variável real com um significado neutro).



Você acha que é plausível que nós e alguns representantes de uma civilização cósmica distante recebamos respostas diferentes para o problema que está sendo resolvido aqui apenas porque temos unidades diferentes de medida de comprimento? Provavelmente não! Portanto, segue-se que para qualquer$ \ mu> 0 $ e qualquer função $ \ varphi (t) $que maximiza a expressão $ (*) $função $ \ psi (t) = \ mu \ cdot \ varphi (\ mu ^ {- 1} \ cdot t) $ também deve maximizar $ (*) $... Se de repente$ \ varphi (t) $ é o único ótimo $ (*) $ função, então para todos $ t> 0 $ e $ \ mu> 0 $ a identidade contém:

$ \ varphi (t) = \ mu \ cdot \ varphi (\ mu ^ {- 1} \ cdot t) $

Colocando nesta identidade $ \ mu = t $, encontramos assim a forma da função $ \ varphi $:

$ \ varphi (t) = t \ cdot \ varphi (t ^ {- 1} \ cdot t) = t \ cdot \ varphi (1) $



Veja o que acontece: se todas as nossas muitas suposições estiverem corretas, a função ideal $ \ varphi (t) $ pertence à classe de funções $ f (k) = \ \ lambda \ cdot k $, mas antes já descobrimos que dentro da classe especificada o valor máximo da expressão $ (*) $ anexa função $ l (k) = \ 2k $... " X2 " é a estratégia ideal ?



Conclusões rigorosas: Otimização de x2



Ok, temos muitas dicas de que a estimativa dada pela função$ l (k) = \ 2k $, é o ideal. Vamos provar essa hipótese rigorosamente, e também estabelecer sob quais condições não existem outras estimativas ótimas.



Tome uma função arbitrária contínua estritamente crescente$ f (k) $satisfazendo a desigualdade $ f (k) \ le2k $, nós consertamos alguns $ v_0 $ do intervalo de seus valores e primeiro tente descobrir qual significado geométrico está oculto por trás do valor $ p_ {sucesso} \ left (f, \ v_0 \ right) $...





Figura: 2



Se o gráfico de função$ f ^ {\ left (-1 \ right)} \ left (v \ right) $ marcar pontos $A=({v_0/2,\ f}^{-1}(v_0/2))$ e $B=({{2v}_0,\ f}^{-1}({2v}_0))$ (Figura 2), e a seguir conecte-os com um segmento, a seguir a tangente do ângulo de inclinação deste segmento ao eixo $Ov$ será expresso pela fórmula

$\frac{f^{-1}\left(2v_0\right)-f^{-1}(v_0/2)}{3/2\ \cdot\ v_0}$

ou seja, na verdade, será igual a $2/3$a partir de $ p_ {sucesso} \ left (f, \ v_0 \ right) $... A mesma observação pode ser expressa de uma forma ligeiramente diferente: para isso, você precisa de um segmento$AB$ parece um gráfico de alguma função $i(v)$... Dentro do intervalo$(v_0/2,\ 2v_0)$ função $i(v)$ obviamente tem uma derivada constante e $ p_ {sucesso} \ left (f, \ v_0 \ right) $ é igual $3/2$-ésimo de sua magnitude.



Agora não é mais difícil mostrar que a função$ f (k) $ não pode bater $ l (k) = \ 2k $ o maior infinum $ p_ {sucesso} $, em outras palavras, a estratégia " x2 " é ótima.



Vou começar com duas observações preliminares:



  1. $f(k)\geq2k= l(k)$, tão $f^{\left(-1\right)}\left(v\right)\le l^{-1}\left(v\right)=1/2\cdot v$ ou seja, o gráfico da função $ f ^ {\ left (-1 \ right)} \ left (v \ right) $ não está acima do gráfico $l^{-1}\left(v\right)$
  2. valor valor $p_{success}\left(l,\ v\right)$ não depende de $v$ e é igual $3/4$, derivado $l^{-1}\left(v\right)$ em todos os pontos é $1/2$...


Para chegar a uma contradição mais tarde, vamos primeiro assumir que $ f (k) $ estritamente melhor $l(k)$... Este último só é possível se houver algum$\varepsilon>0$ e para todos $v$ a desigualdade se mantém: $p_{success} (f,v)≥3/4 + ε$...



Para alguns$u_0>0$ observe no gráfico as funções $ f ^ {\ left (-1 \ right)} \ left (v \ right) $ sequência de pontos

$B_0=(u_0/2,\ f^{\left(-1\right)}\left(u_0/2\right)),\ B_1=(2u_0,\ f^{\left(-1\right)}\left(u_0\right)),\ B_2=(8u_0,\ f^{\left(-1\right)}\left(8u_0\right)),\ ...$

, conecte-os a um $B_0\ B_1B_2...B_n...$ e interpretamos esta linha quebrada como o gráfico de uma função linear por partes $I(v)$... Em sequência$u_0/2,\ 2u_0,\ 8u_0, \ldots\ $ cada valor subsequente é 4 vezes maior do que o anterior, então para cada dois números seguindo um ao outro, podemos olhar para alguns $v_0/2$ e $2v_0$... O último significa que em cada link$B_nB_{n+1}$ linha quebrada $I(v)$ sua derivada será pelo menos $ inline $ 2/3 \ cdot {inf} _v [p_ {sucesso} \ left (f, \ v \ right)] ≥2 / 3⋅ (3/4 + ε) = 1/2 + 2 / 3⋅ε $ inline $...



Desde a derivada$l^{-1}\left(v\right)$ é igual a $1/2$e a derivada $I(v)$ em todos os pontos mais $1/2$ pelo menos para $2/3⋅ε$, então, independentemente do valor $I(v)$ no ponto $u_0$, com ampliação ilimitada $v$ mais cedo ou mais tarde sua programação será maior do que a programação $l^{-1}\left(v\right)$... (fig. 3)





fig. 3



Ao mesmo tempo, você precisa se lembrar que os vértices da polilinha$I(v)$ estão localizados no gráfico da função $ f ^ {\ left (-1 \ right)} \ left (v \ right) $, portanto (consulte a observação 1)) eles próprios e toda a linha tracejada não deve ser maior do que o gráfico $l^{-1}\left(v\right)$... A contradição resultante apenas prova que$l\left(k\right)=2k$é ótimo.



Conclusões rigorosas: singularidade



O que acontecerá se, na prova que acabamos de apresentar, construirmos uma linha quebrada ao longo de tal sequência de vértices, que, em vez de se afastar infinitamente do eixo$OK$, será o contrário - se esforça por isso. Na verdade, isso pode provar que em qualquer universo onde as dimensões das tiras de filme não sejam de forma alguma limitadas por baixo, exceto para a estratégia com a função$l\left(k\right)=2k$, não há outras estratégias ideais. Vamos ver isso.



Suponha que haja uma função$f\left(k\right)$, que por um lado é ideal e, por outro lado, é diferente de $l\left(k\right)$... Neste caso, a função$ f ^ {\ left (-1 \ right)} \ left (v \ right) $ diferente de $l^{-1}\left(v\right)$, e uma vez que a desigualdade $f^{\left(-1\right)}\left(v\right)\le l^{-1}\left(v\right)$, então, pelo menos um valor deve ser encontrado $v$em qual $ f ^ {\ left (-1 \ right)} \ left (v \ right) $ será estritamente menos $l^{\left(-1\right)}\left(v\right)$... Deixe ser$u_0$ um desses valores $v$... Semelhante a como agimos acima, no gráfico$ f ^ {\ left (-1 \ right)} \ left (v \ right) $ marque a sequência de pontos

$B_0=(2u_0,\ f^{\left(-1\right)}\left(2u_0\right)),\ B_1=(u_0/2,\ f^{\left(-1\right)}\left(u_0/2\right)),\ B_2=(u_0/8,\ f^{\left(-1\right)}\left(u_0/8\right)),\ ...$

e desenhe uma linha tracejada através deles $B_0\ B_1B_2...B_n...$(Figura 4). Mais uma vez, iremos interpretar esta linha interrompida como uma função linear por partes$I(v)$... Exatamente pelas mesmas razões de antes, a derivada da função$I(v)$ em cada link $B_nB_{n+1}$ não será menos que $2/3\cdot{inf}_v[p_{success}\left(f,\ v\right)]$... Porque o$ f $ é ótimo, então ${inf}_v[p_{success}\left(f,\ v\right)]$ não deve ser menor que ${inf}_v[p_{success}\left(l,\ v\right)]=3/4$... Combinando as duas últimas declarações, obtemos que a derivada da função$I(v)$ em nenhum lugar menos $2/3\cdot3/4 = 1/2$...





Figura: 4



Vamos denotar o símbolo$\Delta$ diferença $l^{\left(-1\right)}\left(u_0\right)-f^{\left(-1\right)}\left(u_0\right)$ e introduzir outra função: $g(v)=l^{-1}\left(v\right) - \Delta$... Entre as propriedades óbvias$g(v)$ o seguinte pode ser observado:



  1. no ponto $u_0$ valor $g(v)$ corresponde ao valor da função $I(v)$
  2. derivado $g(v)$ com tudo $v$ é o mesmo e igual $1/2$


Vamos ver como os valores das funções mudarão. $I(v)$ e $g(v)$ ao diminuir o argumento $v$ a partir de $u_0$ antes $0$... Valores primeiro$I(v)$ e $g(v)$são iguais. Derivado$I(v)$ em nenhum ponto entre $(0,u_0)$ não menos que derivado $g(v)$, então os valores da função $I(v)$ diminuir não mais lento do que diminuir os valores $g(v)$... Decorre dos fatos listados que durante todo o intervalo$(0,\,u_0)$ $I(v)\le g(v)$...



Porque o$g(v)=1/2\cdot v\ +\Delta$, então no intervalo $(0,\,2\Delta)$ significado $g(v)$ são negativos, e desde $I(v)\le g(v)$ então os valores $I(v)$também deve ser negativo. Ao mesmo tempo, no máximo$I(v)$ São os pontos do gráfico de função $ f ^ {\ left (-1 \ right)} \ left (v \ right) $, uma função que pode assumir valores exclusivamente positivos ($ f $ definido apenas para positivo $ k $), então os valores $I(v)$não pode ser negativo. A contradição assim obtida prova que, além de$l\left(k\right)=2k$, não há outras estimativas ótimas.



Questões de discussão



Tente adaptar independentemente a solução do problema da "partícula aleatória" às condições do problema do "bonde aleatório". Qual é o seu resultado?



Imagine que estamos resolvendo o problema de uma "partícula aleatória" em um universo onde o filme

não pode ser menor que 10 centímetros. Mostre que essas condições estimam$l\left(k\right)=2k$ainda será ótimo, embora não seja mais o único. Mostre que o ideal, por exemplo, é a estimativa$l\left(k\right)=2k+10$... Que outras notas ótimas você encontrou?



Há muitas reclamações sobre o princípio de maximizar os ganhos garantidos se for sabido que seu oponente não deseja derrotá-lo. Este princípio, por exemplo, dificilmente pode ser considerado justificado quando uma festa de jogos é jogada “contra” as condições meteorológicas ou “contra” o mercado de ações mundial. Que princípios de seleção de estratégias nesses casos você poderia sugerir em vez disso, quais deles são aplicáveis ​​ao problema do "bonde aleatório"?



Eu ficaria feliz em ver seus pensamentos e comentários.



Sergey Kovalenko

2020

magnolia@bk.ru


More articles:


All Articles