12
$\begingroup$

(Here is a problem that emerged in a conversation with Fedor Petrov and should really be a sort of "joint posting" if this format were supported.)

For any positive integers $k_1\le k_2\le\dotsb\le k_n$, the following two statements are equivalent:

Statement 1: Every integer in the range $[0,k_1+\dotsb+k_n]$ is representable as a sum of some of the $k_i$ (without repetitions);

Statement 2: Every set of $k_1+\dotsb+k_n$ integers can be partitioned into $n$ subsets such that for each $i\in[n]$, the $i$th subset contains $k_i$ elements and the sum of these elements is divisible by $k_i$.

The equivalence is not difficult to prove using the Erdős-Ginzburg-Ziv theorem, but I wonder whether there is a direct combinatorial argument, not appealing to the EGZ explicitly or implicitly, reusing one of its known proofs. Such an argument would result to an alternative proof of the EGZ (known proofs are discussed here).

Also, what is the two-dimensional analogue of Statement 1? Is it equivalent to the evident two-dimensional analogue of Statement 2?

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ Would you include a more informative title? $\endgroup$
    – YCor
    Commented Feb 13, 2021 at 11:03
  • 3
    $\begingroup$ @მამუკაჯიბლაძე the necessary and sufficient condition is $k_1=1$, $k_{i+1}\leqslant 1+k_1+k_2+\ldots+k_i$ $\endgroup$
    – Fedor Petrov
    Commented Feb 13, 2021 at 11:41
  • 1
    $\begingroup$ Vague idea but maybe you could some how use the lattice of partitions of a set and Moebius inversion on this lattice. $\endgroup$
    – Sam Hopkins
    Commented Feb 14, 2021 at 0:50
  • 1
    $\begingroup$ @MaxAlekseyev: an ideal answer would lead to another proof of the EGZ, I was the first to mention this. $\endgroup$
    – Seva
    Commented Feb 14, 2021 at 6:52
  • 3
    $\begingroup$ Presumably this is the straightforward direction, but for the reference of others, since you don't mention it: Statement 2 implies Statement 1. For $1\leq m\leq K=k_1+\cdots+k_n$, consider the set of $m$ 0s together with $K-m$ many copies of $1$. $\endgroup$
    – Thomas Bloom
    Commented Feb 14, 2021 at 11:58

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .