Suppose you choose $n$ distinct random numbers from a contiguous subset of cardinality $f({\beta, n})$ with at least $f({\alpha_+, n})$ positive and at least $f({\alpha_-, n})$ negative values from a set of $2^{n+1}+1$ integers from $\{-2^n,\dots,-1,0,1,\dots,2^n\}$ at a fixed $\alpha_+,\alpha_-,\beta\in(0,1)$ where $\alpha_+,\alpha_-<\beta$ holds what is the maximum number and average number of subsets that sum to $0$ among all such choice for functions $f(a,b)=2^{ab}$ and $f(a,b)=2^{(\log b)^{1+a}}$?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ What definition of random numbers do you use? $\endgroup$– Włodzimierz HolsztyńskiCommented Jun 1, 2016 at 16:23
-
1$\begingroup$ @WłodzimierzHolsztyński uniform. $\endgroup$– user76479Commented Jun 1, 2016 at 19:00
-
$\begingroup$ Thank you. (I'd still like a less of an assembler, with intermediate objects, and with quantifiers). $\endgroup$– Włodzimierz HolsztyńskiCommented Jun 2, 2016 at 17:56
-
1$\begingroup$ @WłodzimierzHolsztyński it is difficult to make quantifier here since I cannot guess what the subset count would be. $\endgroup$– user76479Commented Jun 2, 2016 at 19:31
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
If $n=2k+1$, then the set $\{-k, \dots, -1,0,1, \dots, k\}$ contains the maximum number of subsets that sum to $0$ among all sets of $2k+1$ real numbers. Similarly, if $n=2k$, then $\{-k, \dots, -1\} \cup \{1, \dots, k\}$ achieves the maximum number of subsets that sum to $0$.
This is a deep result of Stanley (see Corollary 5.1), proved using the Hard Lefschetz Theorem from algebraic geometry.
answered Jun 3, 2016 at 18:46