Esta pergunta foi publicada no CS.SE há duas semanas , mas não obteve uma resposta satisfatória.
Suponha que você tenha o seguinte jogo:
Existem infinitamente muitos contadores , todos inicializados em 0.
Em cada etapa, você escolhe um contador e aumenta seu valor em 1.
Infelizmente, a cada , cada contador que possui um valor positivo é diminuído por 1.
Além disso, os valores dos contadores são delimitados por , portanto você não pode incrementar mais um contador.
1. Dado o número de etapas que você desejar, muitos contadores com valores positivos podem ser alcançados?
2. Quantos contadores com valores positivos são alcançáveis após as etapas ?
Para a pergunta (1), aqui está aa acúmulo detalhado para contadores positivos:
- Enquanto você tiver menos de contadores no valor M :
- Incrementar o contador índice mínimo, cujo valor é estritamente menor que .
(Isso deve convergir à medida que a soma dos contadores aumenta cada passo )
Deixe- .
Enquanto ( )
uma. enquanto ( )
- Incremento
b.
Agora, para a análise: a primeira observação é que o número de contadores positivos é .
Agora seja o valor máximo que c r atingiu. Para r = T , obtemos M ( 1 - 1. Parar=T+1, obtemosmr(1-1, ou em geral∀r≥T:mr=M(1-1
A seguir, notamos que quando é alcançado, c 0 = m r . Isso significa que o loop será interrompido quando m r < 1 (integralidade de dar ou receber e estratégias de final de jogo).
Isso nos dá (1-1
É possível fazer melhor? Alguém pode provar que isso é ideal?