Numeração de subconjuntos

10

Corrija . Para qualquer grande o suficiente , gostaríamos de rotular todos os subconjuntos de de tamanho exatamente por números inteiros positivos de . Gostaríamos que essa rotulagem satisfizesse a seguinte propriedade: existe um conjunto de números inteiros, stn { 1 .. n } n / k { 1 ... T } Sk5n{1..n}n/k{1...T}S

  1. Se subconjuntos de tamanho não se cruzam (ou seja, a união desses conjuntos de formar todo o conjunto ), então a soma de suas etiquetas está em .n / k { 1 .. n } Skn/k{1..n}S
  2. Caso contrário, a soma de seus rótulos não está em .S

Existe um e uma rotulagem, st ?k5T|S|=O(1.99n)

Por exemplo, para qualquer , podemos rotular subconjuntos da seguinte maneira. , cada subconjunto possui bits em seu número: o primeiro bit é igual a se o subconjunto contém , o segundo bit é igual a se o subconjunto contém etc. É fácil ver que contém apenas um elemento . Mas aqui . Podemos fazer melhor?kT=2nn1112S2n1T|S|=Θ(2n)

Alex Golovnev
fonte
3
Por que 5 e não 3?
domotorp 24/07/12
@domotorp: Você sabe como fazer isso para menor ? k
21812 Alex Golovnev
Isso daria uma prova construtiva para a pergunta de um milhão de dólares! Não tão rápido! :)
Tayfun Pay
@ Geekster: Você poderia explicar?
21812 Alex Golovnev
3
É possível fazer T = O (1,99 ^ n)? A pergunta parece sugerir que isso é possível, mas não está claro para mim como fazer isso.
Tsuyoshi Ito

Respostas:

7

Uma resposta parcial é que, mesmo para essa rotulagem não existe.k

Para um conjunto de subconjuntos (de tamanho , deixe denotar a soma de seus valores).S 1 , , S t n / k f ( S 1 , , S t )tS1,,Stn/kf(S1,,St)

Reivindicação: se e então .S 1... S tS ' 1... S ' t f ( S 1 , ... , S t ) f ( S ' 1 , ... , S ' t )t<kS1StS1Stf(S1,,St)f(S1,,St)

Para ver por que a afirmação é verdadeira, escolha um conjunto que mas um desses novos conjuntos intercepta um dos 's, então não pode ser igual a .k i = 1 S i = [ n ] S i f ( S 1 , , S k ) f ( S 1 , , S t , S t + 1 , ... , S k )St+1,,Ski=1kSi=[n]Sif(S1,,Sk)f(S1,,St,St+1,,Sk)

Corolário: .T>(ntn/k)/t

Definir fornece um limite inferior de .t=k/2T2(nn/2)/k=Ω(2n/n)

Observe que, para ímpares obtém-se um limite inferior de ordem . Já para , temos portanto, o expoente tende a rapidamente.k(nn(11/k)/2)2H((11/k)/2)n=2n(1O(1/k2))k=5H((11/k)/2)=H(0.4)0.971

Eu acho que também não existe uma solução para o estranho , mas não sei como prová-lo.k

Per Austrin
fonte
Obrigado, solução muito bonita! Mas não tenho certeza se podemos generalizá-lo para ímpar . k
21812 Alex Golovnev
4

Esta não é uma resposta, apenas uma explicação do porquê k = 2 não existe tal rotulagem (tenho certeza de que Alex já sabia disso, portanto, isso é apenas um resumo de outros leitores como eu ...)

Para k = 2, temos . Isso ocorre porque existem subconjuntos de tamanho n / 2. Se dois tiverem o mesmo rótulo, por exemplo, A e B, então a soma do rótulo de A e seu complemento não está em S, ou a soma do rótulo de B e o complemento de A está em S. Isso implica (para n grande).T(nn/2)1.99n(nn/2)T(nn/2)

Para ka maior, argumento semelhante mostra que todos os rótulos devem ser diferentes, mas isso apenas fornece um limite inferior exponencial mais fraco. Então, k = 3 parece desconhecido.

domotorp
fonte
Sim obrigado! Será ótimo se alguém puder intuir por que não existe uma rotulagem para maior ou por que é difícil encontrar essa rotulagem. k
Alex Golovnev