|
7
|
|
edited Dec 9 2011 at 14:19 |
Let $X=\{x_1,...,x_n\}$ be a multiset of $n$ real numbers, and let $x_1+\dots+x_n = 0$. Is there a way to find the maximum number of unique subsets any $X$ can have given $n$, such that each subset sums to $0$, but contains no subset itself that sums to $0$?
Or more precisely, is the following max over all multisets of size $n$ bounded above polynomially as $n$ gets large?: $max\{|f(X)| : X = \{x_1,...,x_n\}\}${x_1,...,x_n\} \land x_1+\dots+x_n = 0\}$ where $f(X) = \{Y \subseteq X : sumY=0 \land \forall_{Z\subset Y}sumZ\neq0 \}$.
I'm interested in this as a bound for an algorithm. I have a feeling it doesn't grow very fast, but I'm unsure how to approach the problem.
I have tried to brute force it for small values of $x$ and have found the following values for $n \in [0,10]$: $[1, 1, 1, 2, 2, 3, 5, 8, 12, 20, 32]$. OEIS doesn't seam to have a related entry.
Edit: To work against confusion, here are some examples using distinct integers only, that I believe to be optimal:
0: {} {{}}
1: {0} {{0}}
2: {-1,1} {{-1,1}}
3: {-1,0,1} {{0},{-1,1}}
4: {-2,-1,1,2} {{-2,2},{-1,1}}
5: {-2,-1,0,1,2} {{0},{-2,2},{-1,1}}
6: {-3,-2,-1,1,2,3} {{-3,3},{-2,2},{-1,1},{-3,1,2},{-2,-1,3}}
7: {-6,-4,-1,1,2,3,5} {{-1,1},{-6,1,5},{-4,-1,5},{-4,1,3},{-6,-1,2,5},{-6,1,2,3},{-4,-1,2,3},{-6,-4,2,3,5}}
8: {-8,-7,-3,1,2,4,5,6} {{-8,2,6},{-7,1,6},{-7,2,5},{-3,1,2},{-8,-3,5,6},{-8,1,2,5},{-7,-3,4,6},{-7,1,2,4},{-8,-7,4,5,6},{-8,-3,1,4,6},{-8,-3,2,4,5},{-7,-3,1,4,5}}
|
|
|
|
|
6
|
|
edited Dec 9 2011 at 11:58 |
Let $X=\{x_1,...,x_n\}$ be a multiset of $n$ real numbers, and let $x_1+\dots+x_n = 0$.
Is there a way to find the maximum number of unique subsets any $X$ can have given $n$, such that each subset sums to $0$, but contains no subset itself that sums to $0$?
Or more precisely, is the following max over all multisets of size $n$ bounded above polynomially as $n$ gets large?: $max\{|f(X)| : X = \{x_1,...,x_n\}\}$ where $f(X) = \{Y \subseteq X : sumY=0 \land \forall_{Z\subset Y}sumZ\neq0 \}$.
I'm interested in this as a bound for an algorithm. I have a feeling it doesn't grow very fast, but I'm unsure how to approach the problem.
I have tried to brute force it for small values of $x$ and have found the following values for $n \in [0,10]$: $[1, 1, 1, 2, 2, 3, 5, 8, 12, 20, 32]$. OEIS doesn't seam to have a related entry.
Edit: To work against confusion, here are some examples using distinct integers only, that I believe to be optimal:
0: {} {}
{}}
1: {0} {{0}}
2: {-1,1} {{-1,1}}
3: {-1,0,1} {{0},{-1,1}}
4: {-2,-1,1,2} {{-2,2},{-1,1}}
5: {-2,-1,0,1,2} {{0},{-2,2},{-1,1}}
6: {-3,-2,-1,1,2,3} {{-3,3},{-2,2},{-1,1},{-3,1,2},{-2,-1,3}}
7: {-6,-4,-1,1,2,3,5} {{-1,1},{-6,1,5},{-4,-1,5},{-4,1,3},{-6,-1,2,5},{-6,1,2,3},{-4,-1,2,3},{-6,-4,2,3,5}}
8: {-8,-7,-3,1,2,4,5,6} {{-8,2,6},{-7,1,6},{-7,2,5},{-3,1,2},{-8,-3,5,6},{-8,1,2,5},{-7,-3,4,6},{-7,1,2,4},{-8,-7,4,5,6},{-8,-3,1,4,6},{-8,-3,2,4,5},{-7,-3,1,4,5}}
|
|
|
|
|
5
|
|
edited Dec 9 2011 at 11:23 |
Let $X=\{x_1,...,x_n\}$ be a multiset of $n$ real numbers, and let $x_1+\dots+x_n = 0$.
Is there a way to find the maximum number of subsets any $X$ can have given $n$, such that each subset sums to $0$, but contains no subset itself that sums to $0$?
I'm interested in this as a bound for an algorithm. I have a feeling it doesn't grow very fast, but I'm unsure how to approach the problem.
I have tried to brute force it for small values of $x$ and have found the following values for $n \in [1,10]$0,10]$: $[1, 1, 1, 2, 2, 3, 5, 8, 12, 20, 32]$. OEIS doesn't seam to have a related entry.
Edit: To work against confusion, here are some examples using distinct integers only, that I believe to be optimal:
0: {} {}
1: {0} {{0}}
2: {-1,1} {{-1,1}}
3: {-1,0,1} {{0},{-1,1}}
4: {-2,-1,1,2} {{-2,2},{-1,1}}
5: {-2,-1,0,1,2} {{0},{-2,2},{-1,1}}
6: {-3,-2,-1,1,2,3} {{-3,3},{-2,2},{-1,1},{-3,1,2},{-2,-1,3}}
7: {-6,-4,-1,1,2,3,5} {{-1,1},{-6,1,5},{-4,-1,5},{-4,1,3},{-6,-1,2,5},{-6,1,2,3},{-4,-1,2,3},{-6,-4,2,3,5}}
8: {-8,-7,-3,1,2,4,5,6} {{-8,2,6},{-7,1,6},{-7,2,5},{-3,1,2},{-8,-3,5,6},{-8,1,2,5},{-7,-3,4,6},{-7,1,2,4},{-8,-7,4,5,6},{-8,-3,1,4,6},{-8,-3,2,4,5},{-7,-3,1,4,5}}
|
|
|
|
4
|
|
edited Dec 9 2011 at 11:08 |
Let $X=\{x_1,...,x_n\}$ be a multiset of $n$ real numbers, and let $x_1+\dots+x_n = 0$.
Is there a way to find the maximum number of subsets any $X$ can have given $n$, such that each subset sums to $0$, but contains no subset itself that sums to $0$?
I'm interested in this as a bound for an algorithm. I have a feeling it doesn't grow very fast, but I'm unsure how to approach the problem.
I have tried to brute force it for small values of $x$ and have found the following values for $n \in [0,10]$1,10]$: $[1, 1, 2, 2, 3, 5, 8, 12, 20, 32]$. OEIS doesn't seam to have a related entry.
|
|
|
|
|
3
|
|
edited Dec 8 2011 at 20:39 |
Let $X=\{x_1,...,x_n\}$ be a multiset of $n$ real numbers, and let $sum(x_1,...,x_n) x_1+\dots+x_n = 0$.
Is there a way to find the maximum number of subsets any $X$ can have given $n$, such that each subset sums to $0$, but contains no subset itself that sums to $0$?
I'm interested in this as a bound for an algorithm. I have a feeling it doesn't grow very fast, but I'm unsure how to approach the problem.
I have tried to brute force it for small values of $x$ and have found the following values for $n \in [0,10]$: $[1, 1, 2, 2, 3, 5, 8, 12, 20, 32]$. OEIS doesn't seam to have a related entry.
|
|
|
|
|
2
|
|
edited Dec 8 2011 at 13:46 |
Let $X=\{x_1,...,x_n\}$ be a multiset of $n$ real numbers, and let $sum(x_1,...,x_n) = 0$.
Is there a way to find the maximum number of subsets any $X$ can have given $n$, such that each subset sums to $0$, but contains no subset itself that sums to $0$?
I'm interested in this as a bound for an algorithm. I have a feeling it doesn't grow very fast, but I'm unsure how to approach the problem.
I have tried to brute force it for small values of $x$ and have found the following values for $n \in [0,9]$0,10]$: $[1, 1, 2, 2, 3, 5, 8, 12, 20]$20, 32]$. OEIS doesn't seam to have a related entry.
|
|
|
|
|
1
|
|
asked Dec 8 2011 at 13:34 |
Problem regarding subsets that sum to 0
Let $X=\{x_1,...,x_n\}$ be a multiset of $n$ real numbers, and let $sum(x_1,...,x_n) = 0$.
Is there a way to find the maximum number of subsets any $X$ can have given $n$, such that each subset sums to $0$, but contains no subset itself that sums to $0$?
I'm interested in this as a bound for an algorithm. I have a feeling it doesn't grow very fast, but I'm unsure how to approach the problem.
I have tried to brute force it for small values of $x$ and have found the following values for $n \in [0,9]$: $[1, 1, 2, 2, 3, 5, 8, 12, 20]$. OEIS doesn't seam to have a related entry.
|
|
|
