Qual é o valor desse "jogo" (rebalanceamento dos contadores)?

8

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 {c1,c2,} , todos inicializados em 0.

Em cada etapa, você escolhe um contador ci e aumenta seu valor em 1.

Infelizmente, a cada T , 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.M

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 ?TM1


Para a pergunta (1), aqui está aa acúmulo detalhado para contadores positivos:Tlog(M)

  1. Enquanto você tiver menos de contadores no valor M : T1M
    • Incrementar o contador índice mínimo, cujo valor é estritamente menor que .M

(Isso deve convergir à medida que a soma dos contadores aumenta cada passo )T

  1. Deixe- .r=T

  2. Enquanto ( )c0>1

    uma. enquanto ( )c0>cr

    • Incremento cr

    b. r=r+1

Agora, para a análise: a primeira observação é que o número de contadores positivos é .r

Agora seja o valor máximo que c r atingiu. Para r = T , obtemos M ( 1 - 1mrcrr=T. Parar=T+1, obtemosmr(1-1M(11T)r=T+1, ou em geralrT:mr=M(1-1mr(11T)=M(11T)2

rT:mr=M(11T)rT+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).mrc0=mrmr<1

Isso nos dá (1-1

M(11T)rT+1<1
(r-T+1)log(1-1
(11T)rT+1<M1
r-T+1<-logM
(rT+1)log(11T)<logM
r<-logM
rT+1<logMlog(11T)
r<logM
r<logMlog(11T)+T1
r<logMk11kTk+T1<T(logM+1)1

É possível fazer melhor? Alguém pode provar que isso é ideal?

RB
fonte

Respostas:

5

Limite inferior para a pergunta 2:

Teorema: Depois passos, com a estratégia delineada abaixo, você terá pelo menosTM1 dos contadores positivos.(T1)logM

Notação: Definir passo de tempo para ser o início do T M - 1 passos, e T M - 1 para ser a extremidade. Decrementos acontecem na etapa T do tempo1TM1TM1 , 1 k < M .Tk1k<M

Defina o limite superior como , onde N é o intervalo de tempo atual. Esse limite começa em M e diminui em um sempre que os contadores diminuem, terminando em 1 . Esse limite é escolhido porque, se mais contadores forem colocados em uma célula do que o limite superior, eles serão desperdiçados, porque o contador terá um valor maior queMN/TN1 na etapa T M - 1 .1TM1

Estratégia: em todas as etapas, aumente o contador mais à esquerda, cujo valor seja menor que o limite superior.

Notação: Defina a importância de um contador para ser , onde V é seu valor atual e U L é o limite superior atual.V/ULUL

Lema: Em cada grupo de etapas que terminam em decréscimo, a soma das importâncias dos contadores aumenta em pelo menos ( T - 1 ) /T , onde L ? L é o limite superior de corrente.(T1)/ULUL

Prova de lema: Cada vez que um contador é incrementado, a sua importância aumenta em . Quando o decréscimo acontece, todos, exceto um contador, estão no seu limite superior e têm uma importância de U L / U L = 1 . Importância do contador restante é encolhido por, no máximo, 1 / U L , porque o seu valor diminui em 1 e U L não aumenta. Assim, os incrementos de T e decréscimo de 1 aumentam a importância total em pelo menos ( T - 1 ) /1/ULUL/UL=11/UL1ULT1 . Além disso, no último grupo de t - 1 - 1 ) / L L .(T1)/ULT1incrementos, onde não ocorre decréscimo, a soma das importações aumenta em (T1)/UL

TT1(T1)/ULTM1k=1m(T1)/k(T1)logMTM11(T1)logM

isaacg
fonte
5

Aqui está um limite superior para a pergunta 2.

TMTlogM

0(TM+1)

0

1T12T13TkT+1(k1)T1k . Precisamos de um lema que provaremos mais tarde.

Lema: para um contador ser positivo, ele deve ter um valor total de pelo menos1

Ti=1M1iTlogM1

kT(k1)Tk1k1k

E aqui está um limite superior para a pergunta 1. Vamos usar a mesma estratégia geral de provas de antes. Novamente, atribuímos um valor de1kkT+1(k1)T1M2MTMT002MT12MT1MTlogM+TT(logM+1)

Peter Shor
fonte
xxNN=TMΩ(TlogM) contadores podem ser positivos,
RB
Ou talvez eu possa dar uma ligação melhor. Obrigado novamente.
RB