Нумерация подмножеств

10

Исправить . Для любого достаточно большого мы хотели бы пометить все подмножества размера точно натуральными числами из . Нам бы хотелось, чтобы эта маркировка удовлетворяла следующему свойству: есть множество целых чисел, stk5n{1..n}n/k{1...T}S

  1. Если подмножеств размера не пересекаются (т.е. объединение этих множеств образуют все множество ), то сумма их меток в .kn/k{1..n}S
  2. В противном случае, сумма их метки не в .S

Существует ли и метка st ?k5T|S|=O(1.99n)

Например, для любого мы можем пометить подмножества следующим образом. , каждое подмножество имеет битов в своем числе: первый бит равен если подмножество содержит , второй бит равен если подмножество содержит т. Д. Легко видеть, что содержит только один элемент . Но здесь . Можем ли мы сделать это лучше?kT=2nn1112S2n1T|S|=Θ(2n)

Алекс Головнев
источник
3
Почему 5, а не 3?
Домоторп
@domotorp: Вы знаете, как сделать это для меньшего ? k
Алексей Головнев
Это дало бы конструктивное доказательство вопроса на миллион долларов! Не так быстро! :)
Tayfun Pay
@Geekster: Не могли бы вы объяснить?
Алексей Головнев
3
Можно ли сделать T = O (1,99 ^ n)? Кажется, вопрос предполагает, что это возможно, но мне неясно, как это сделать.
Цуёси Ито

Ответы:

7

Частичный ответ состоит в том, что даже для такой маркировки не существует.k

Для набора из непересекающихся подмножеств (размером пусть обозначает сумму их значений).tS1,,Stn/kf(S1,,St)

Утверждение: если и то .t<kS1StS1Stf(S1,,St)f(S1,,St)

Чтобы понять, почему утверждение верно, выберите набор такой, что но затем один из этих новых наборов пересекает один из , поэтому не может быть таким же, как .St+1,,Ski=1kSi=[n]Sif(S1,,Sk)f(S1,,St,St+1,,Sk)

Следствие: .T>(ntn/k)/t

Установка дает нижнюю границу .t=k/2T2(nn/2)/k=Ω(2n/n)

Обратите внимание, что для нечетного можно получить нижнюю границу порядка . Уже при мы имеем поэтому показатель степени стремится к довольно быстро.k(nn(11/k)/2)2H((11/k)/2)n=2n(1O(1/k2))k=5H((11/k)/2)=H(0.4)0.971

Я бы предположил, что для нечетных тоже не существует решения, но я не уверен, как это доказать.k

За австрина
источник
Спасибо, очень красивое решение! Но я не уверен, сможем ли мы обобщить это на нечетное . k
Алексей Головнев
4

Это не ответ, а просто объяснение, почему при k = 2 такой маркировки не может быть (я уверен, что это уже было известно Алексу, так что это просто рецензия для других читателей, таких как я ...)

Для k = 2 имеем . Это потому, что есть подмножеств размера n / 2. Если любые два получают одинаковую метку, например, A и B, то либо сумма метки A и ее дополнения не в S, либо сумма метки B и дополнения A в S. Это подразумевает (для больших n).T(nn/2)1.99n(nn/2)T(nn/2)

Для больших k аналогичный аргумент показывает, что все метки должны быть разными, но это дает только более слабую экспоненциальную нижнюю границу. Так что уже k = 3 кажется неизвестным.

domotorp
источник
Да спасибо! Было бы замечательно, если бы кто-то мог дать какую-то интуицию, почему нет такой маркировки для больших , или почему трудно найти такую ​​маркировку. k
Алексей Головнев