Skip to main content
1 of 4
Seva
  • 23k
  • 2
  • 59
  • 141

A mere coincidence or something more?

(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 $[k_1,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 Erdos-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.

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

Seva
  • 23k
  • 2
  • 59
  • 141