2
$\begingroup$

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}}$?

$\endgroup$
  • $\begingroup$ What definition of random numbers do you use? $\endgroup$ – Włodzimierz Holsztyński Jun 1 '16 at 16:23
  • 1
    $\begingroup$ @WłodzimierzHolsztyński uniform. $\endgroup$ – user76479 Jun 1 '16 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ński Jun 2 '16 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$ – user76479 Jun 2 '16 at 19:31
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy