Пусть мы зафиксируем и целое число .
для любого и для любого вектора такого, что
Я не знаю, верно ли это утверждение или ложь. Я думаю, что это правда.
Моя интуиция исходит из наблюдения, что для векторов (с желаемым свойством относительно суммы) мы имеем ; в этом случае мы можем выбрать только подмножество из набора .
В другом случае мы можем создать хорошее подмножество (st сумма больше, чем ), используя координаты в но также, возможно, используя несколько координат из набора мы могли бы создать другой хороший набор!
Итак, докажите это или найдите ошибку! надеясь, что это может быть забавная игра для вас!
Мотивация вопроса :
Предположим, у вас есть случайная величина , типичная мера «сколько случайности» в - это минимальная энтропия
В некотором интуитивном смысле мин-энтропия является худшим случаем знаменитой энтропии Шеннона (это средний случай ).
Нам интересно ограничить минимальную энтропию случайной величины где равномерно распределено по множеству .
Грубо говоря, если нам повезет, мы можем поймать биты которые имеют «хорошую энтропию», и поэтому мы, если то
Какова вероятность того, что нам повезло?
Проблема хорошо изучена, и существует много литературы, например, см. Лемму А.3. в устойчивой к утечкам криптографии с открытым ключом в модели с ограниченным поиском
источник
Ответы:
Гипотеза в посте не верна, но более слабая гипотеза (по отношению к полу), упомянутая в комментариях, остается верной. На самом деле что-то сильнее держит.
Лемма 1. Гипотеза в посте не имеет места. То есть есть экземпляр, удовлетворяющий данным предположениям, где
Доказательство. Рассмотрим случай с , , и . Тогда . Для левой части мы имеем потому что любое подмножество которое не содержит обеих сумм 1, не превышает 1.7, и есть только два подмножества ( и ), содержащие оба 1. И правая часть - этоn=3 c=(1,1,0.7) E=2.7/3=0.9 t=2 Et=1.8
Более слабая гипотеза, предложенная в комментариях, а именно граница с полом, , имеет место. На самом деле что-то чуть сильнее держит:⌊En⌋
Лемма 2. Зафиксируем , целые числа и вектор с помощью . Тогда0<E<1 n,t>0 c∈[0,1]n ∑i∈[n]ci≥En
∣∣{S⊆[n]:∑i∈S ci≥Et}∣∣>(⌊En⌋t)+(⌊En⌋t+1)+⋯+(⌊En⌋⌊En⌋).
Доказательство. Пусть . Предположим, что WLOG . (В противном случае масштабируйте и каждый вниз на единообразный коэффициент, чтобы сделать это так. Это поддерживает и не изменяет ни сумму подмножеств как минимум ни желаемую нижнюю границу числа таких подмножеств.) Предположим, что WLOG (в противном случае утверждение выполняется тривиально).a=⌊En⌋ a=En E ci ∑ici≥En Et t≤a
Рассмотрим любое подмножество размером не менее , где . Поскольку и содержит все, кроме не более элементов (каждый из которых не более 1), мы имеем , по желанию.S⊆[n] n−d d=a−⌈at/n⌉≥0 ∑i∈[n]ci≥a S d ∑i∈Sci≥a−d=⌈at/n⌉=⌈Et⌉≥Et
Количество таких подмножеств равноS
Но (используя ), поэтому последняя сумма является как минимум желаемой нижней границей для числа хороших подмножеств.a−d=⌈at/n⌉≤t a/n=E<1 □
источник