Numérotation des sous-ensembles

10

Fixe . Pour tout n assez grand , nous aimerions étiqueter tous les sous-ensembles de { 1 .. n } de taille exactement n / k par des entiers positifs de { 1 ... T } . Nous aimerions que cet étiquetage satisfasse la propriété suivante: il y a un ensemble S d'entiers, stk5n{1..n}n/k{1...T}S

  1. Si sous - ensembles de taille n / k ne pas recoupé ( par exemple l'union de ces ensembles forment tout l'ensemble { 1 .. n } ), la somme de leurs étiquettes est en S .kn/k{1..n}S
  2. Dans le cas contraire, la somme de leurs étiquettes ne sont pas en .S

Existe-t-il un et un étiquetage, st T | S | = O ( 1,99 n ) ?k5T|S|=O(1.99n)

Par exemple, pour tout nous pouvons étiqueter les sous-ensembles de la manière suivante. T = 2 n , chaque sous-ensemble a n bits dans leur nombre: le premier bit est égal à 1 si le sous-ensemble contient 1 , le deuxième bit est égal à 1 si le sous-ensemble contient 2 etc. Il est facile de voir que S ne contient qu'un seul élément 2 n - 1 . Mais ici T | S | = Θ ( 2 n ) . Pouvons-nous faire mieux?kT=2nn1112S2n1T|S|=Θ(2n)

Alex Golovnev
la source
3
Pourquoi 5 et non 3?
domotorp
@domotorp: Savez-vous comment le faire pour des plus petits ? k
Alex Golovnev
Cela donnerait une preuve constructive de la question à un million de dollars! Pas si vite! :)
Tayfun Payez le
@Geekster: Pourriez-vous s'il vous plaît expliquer?
Alex Golovnev
3
Est-il possible de faire T = O (1,99 ^ n)? La question semble suggérer que c'est possible, mais je ne sais pas comment procéder.
Tsuyoshi Ito le

Réponses:

7

Une réponse partielle est que, même pour , un tel étiquetage n'existe pas.k

Pour un ensemble de sous-ensembles disjoints S 1 , , S t (de taille n / k , soit f ( S 1 , , S t ) la somme de leurs valeurs).tS1,,Stn/kf(S1,,St)

Affirmation: si et S 1S tS 1S t alors f ( S 1 , , S t ) f ( S 1 , , S t ) .t<kS1StS1Stf(S1,,St)f(S1,,St)

Pour voir pourquoi la prétention est vraie, choisissez un ensemble tel que k i = 1 S i = [ n ] mais alors l'un de ces nouveaux ensembles coupe l'un des S i afin f ( S 1 , , S k ) ne doit pas être identique à f ( S 1 , , S t , SSt+1,,Ski=1kSi=[n]Sif(S1,,Sk).f(S1,,St,St+1,,Sk)

Corollaire: .T>(ntn/k)/t

Le réglage donne une borne inférieure de T 2 ( nt=k/2.T2(nn/2)/k=Ω(2n/n)

Notez que pour impair, on obtient une borne inférieure d'ordre ( nk(nn(11/k)/2)2H((11/k)/2)n=2n(1O(1/k2))k=5H((11/k)/2)=H(0.4)0.971

k

Per Austrin
la source
k
4

Ce n'est pas une réponse, juste une explication pour laquelle pour k = 2, un tel étiquetage ne peut pas exister (je suis sûr que cela était déjà connu d'Alex, donc c'est juste un article pour d'autres lecteurs comme moi ...)

T(nn/2)1.99n(nn/2)T(nn/2)

Pour un ka plus grand, un argument similaire montre que toutes les étiquettes doivent être différentes, mais cela ne donne qu'une borne inférieure exponentielle plus faible. Donc déjà k = 3 semble inconnu.

domotorp
la source
k