Existe alguma forma matemática fechada (ou assintótica um tanto rígida) para o "Google Eggs Puzzle"?

8

A breve descrição a seguir do conhecido "Google Eggs Puzzle" vem principalmente do site Google Eggs :

Quebra-cabeça de ovos do Google: dados n andares e m ovos, qual é a abordagem para encontrar o andar mais alto a partir do qual os ovos podem ser jogados com segurança, minimizando os arremessos (não os ovos quebrados).

O chamado "andar mais alto" no problema acima merece uma definição mais formal:

"mais alto:" deve haver um piso de f (em qualquer edifício suficientemente alto) de tal forma que um ovo caiu do f th quebras de chão, mas caiu do ( f-1 ) º andar não vai. Então, f-1 aqui é o andar mais alto.

Na verdade, a descrição de "mais alto" é um trecho do livro "The Algorithm Design Manual (Second Edition)", de Steven S. Skiena. Sendo um exercício no Capítulo 8 "Programação dinâmica", há muitos recursos na Web dedicados a resolver o quebra-cabeça por meio da programação dinâmica, como Google Eggs e The Two Egg Problem .

No entanto, há uma pergunta do livro acima:

$E(n, m) = \Theta(n^{\frac{1}{m}})$ $E(\cdot)$

É a pergunta que motiva o meu problema:

$E(n, m) = \Theta(n^{\frac{1}{m}})$

ds.algorithms puzzles dynamic-programming hengxin
fonte

4

m

$m$

m = \log n

$m = \log n$

Θ (min_{k \leq m} k n^{1 / k})

$\Theta(\min_{k\leq m} kn^{1/k})$

m

$m$

\log n

$\log n$

m

$m$

@RobinKothari Eu concordo com você. Os experimentos numéricos no material Alegria da Queda de Ovos apoiam sua observação. No entanto, eu não entendo o significado de . Como meu palpite, o parâmetro é o número real de ovos em uso. Então, o que isso significa como um fator em ? Muito obrigado.

Θ (min_{k \leq m} k n^{\frac{1}{k}})

$\Theta(\min_{k \le m} kn^{\frac{1}{k}})$

k

$k$

k n^{\frac{1}{k}}

$kn^{\frac{1}{k}}$

Hengxin

Posso tentar explicar o significado, mas é um pouco longo, então vou postá-lo como resposta.

precisa

8

Com m ovos e medidas k, o maior número de andares que pode ser verificado é exatamente (talvez dependendo da definição exata). A prova é trivial por indução. Esta expressão não tem forma fechada inversa, mas fornece boas assintóticas.

n (m, k) = (\binom{k}{0}) + (\binom{k}{1}) + \dots + (\binom{k}{m}),

$n(m,k)={k \choose 0} + {k \choose 1} + \ldots + {k \choose m},$

\pm 1

$\pm 1$

domotorp
fonte

4

Apenas esboçar um pouco a estratégia de desistência tornaria a resposta mais completa. Talvez não seja apropriado, pois acho que não é de nível de pesquisa. De qualquer forma, com 2 ovos, você pode pular andares na sua primeira queda e, se não quebrar, pular , e se não quebrar pular , etc. O que dá como o andar mais alto que você poderia alcançar usando essa estratégia.

k

$k$

k - 1

$k - 1$

k - 2

$k - 2$

k (k + 1) / 2

$k(k+1) / 2$

21412 Joe

@domotorp Parece construtivo examinar o quebra-cabeça da perspectiva que você acabou de mostrar. E a equação sobre pode ser provado pela indução de e . Embora não exista uma forma clara e fechada para o lado direito desta equação, ela pode fornecer a expressão assintótica ?

n (m, k)

$n(m,k)$

m

$m$

k

$k$

k (n, m) = Θ (n^{\frac{1}{m}})

$k(n,m) = \Theta(n^{\frac{1}{m}})$

Hengxin

2

@ hengxin, yesish, porque é um polinômio em de grau , então isso mostra que manter constante fornece . Mas veja o comentário de Robin sobre a questão. A questão mais interessante é se essa expressão exata permite um limite mais preciso aproximando a cauda binomial, por exemplo, com erf.

(\binom{k}{m})

$\binom{k}{m}$

k

$k$

m

$m$

m

$m$

n (m, k) = Θ (k^{m})

$n(m, k) = \Theta(k^m)$

Peter Taylor

2

No meu comentário acima, eu disse que talvez seja um limite apertado. Não tenho certeza sobre o limite inferior, mas como você quer apenas uma explicação para o que significa, posso explicar a intuição usando o limite superior. $\Theta(\min_{k \le m} kn^{\frac{1}{k}})$ $k$

Como você adivinhou, é o número de ovos realmente usados. Isso explica a do lado de fora. Agora que decidimos usar eggs, eis uma estratégia que funciona: pense no número como sendo escrito na base . Portanto , a representação de terá "dígitos" (a palavra "dígito" é geralmente reservada para a base 10, mas usarei aqui), e cada dígito possui um valor de 0 a . Com nossos ovos, estamos tentando extrair os dígitos de um por um. Primeiro, começamos com o dígito mais significativo. Isso pode ser determinado jogando um ovo do chão numerado $k$ $\min$ $k$ $n$ $n^{1/k}$ $n$ $k$ $n^{1/k}-1$ $k$ $n$ $100..00$ , e assim por diante. Após no máximo lances, aprendemos qual é o bit mais significativo e, no pior dos casos, quebramos apenas 1 ovo. Agora fazemos isso para todos os outros dígitos. Como existem dígitos, precisaremos de lances. $200..00$ $n^{1/k}-1$ $k$ $O(kn^{1/k})$

Como verificação de sanidade, observe que, quando , essa estratégia se resume a retirar ovos de cada andar, um a um, começando no andar 1. Quando , estamos apenas trabalhando na base 2. Portanto, isso gera o algoritmo de busca binária. $k=1$ $k = \log n$

Robin Kothari
fonte

1

Uma característica interessante da solução da domotorp, diferente da sua, é que ela não exige conhecimento prévio!

Jeffε

Existe alguma forma matemática fechada (ou assintótica um tanto rígida) para o "Google Eggs Puzzle"?

Respostas: