|
2 | added 78 characters in body | ||
|
I worked on this for a bit with Ricky Liu, who came up with this very quick solution: Take your set T. Suppose $\sum p_i = kn$, where $k \geq 2$. Create the following set T': let $i$ appear $p_i$ times. This creates a set $T'$ with at least $2n$ elements (by your first constraint and $k \geq 2$), whose sum is divisible by $n$ by your second constraint. However, by Erdos-Ginsberg-Ziv, there's a subset of $n$ elements which add to $n$, which exactly corresponds to your generator, so we're done. |
||||
|
|
1 |
|
||
|
I worked on this for a bit with Ricky Liu, who came up with this very quick solution: Take your set T. Suppose $\sum p_i = kn$, where $k \geq 2$. Create the following set T': let $i$ appear $p_i$ times. This creates a set $T'$ with at least $2n$ elements (by your first constraint and $k \geq 2$), whose sum is divisible by $n$ by your second constraint. However, by Erdos-Ginsberg-Ziv, there's a subset of $n$ elements which add to $n$, which exactly corresponds to your generator, so we're done. |
||||
