Исправить . Для любого достаточно большого мы хотели бы пометить все подмножества размера точно натуральными числами из . Нам бы хотелось, чтобы эта маркировка удовлетворяла следующему свойству: есть множество целых чисел, st
- Если подмножеств размера не пересекаются (т.е. объединение этих множеств образуют все множество ), то сумма их меток в .
- В противном случае, сумма их метки не в .
Существует ли и метка st ?
Например, для любого мы можем пометить подмножества следующим образом. , каждое подмножество имеет битов в своем числе: первый бит равен если подмножество содержит , второй бит равен если подмножество содержит т. Д. Легко видеть, что содержит только один элемент . Но здесь . Можем ли мы сделать это лучше?
Ответы:
Частичный ответ состоит в том, что даже для такой маркировки не существует.k
Для набора из непересекающихся подмножеств (размером пусть обозначает сумму их значений).t S1,…,St n/k f(S1,…,St)
Утверждение: если и то .t<k S1∪…∪St≠S′1∪…∪S′t f(S1,…,St)≠f(S′1,…,S′t)
Чтобы понять, почему утверждение верно, выберите набор такой, что но затем один из этих новых наборов пересекает один из , поэтому не может быть таким же, как .St+1,…,Sk ⋃ki=1Si=[n] S′i f(S1,…,Sk) f(S′1,…,S′t,St+1,…,Sk)
Следствие: .T>(ntn/k)/t
Установка дает нижнюю границу .t=k/2 T≥2(nn/2)/k=Ω(2n/n−−√)
Обратите внимание, что для нечетного можно получить нижнюю границу порядка . Уже при мы имеем поэтому показатель степени стремится к довольно быстро.k (nn(1−1/k)/2)≈2H((1−1/k)/2)n=2n(1−O(1/k2)) k=5 H((1−1/k)/2)=H(0.4)≈0.97 1
Я бы предположил, что для нечетных тоже не существует решения, но я не уверен, как это доказать.k
источник
Это не ответ, а просто объяснение, почему при 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 кажется неизвестным.
источник