0
$\begingroup$

Given $r$ numbers $a_1,a_2,...,a_r$ and $n=qP$ where $P$ is the product of these $r$ numbers. $q$ is a natural number such that $q \geq 2$.

Also given is a matrix $A$ of the following form: $$A=\begin{pmatrix}x_{11}&x_{12}&...&x_{1r}\\x_{21}&x_{22}&...&x_{2r}\\:&:&:&:\\x_{n1}&x_{n2}&...&x_{nr}\end{pmatrix}.$$ Here all $x_{ij}$'s are either $0$ or $1$. Each row has exactly one $1$ and each column sums up to some multiple of $a_j$, where $j$ is the column number.

Also, the sum of all elements of the matrix is equal to $n$, as defined above.

Allowing rearrangement of rows of $A$, how do I show that for each $j = 1, 2, · · · , r$, the sum of the first $P$ terms in the $j^{th}$ column of the matrix $A$ can be made a multiple of $a_j$?

I know that it can be done by repeatedly applying the EGZ theorem, but I fail to see how.

Note: This is part of a bigger problem that I am solving, and this is all the relevant context that is required.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

We may not care that elements are zeroes or ones. By EGZ applied to a first column (several times) we may partition rows to $n/a_i$ blocks so that the sum in each block is divisible by $a_i$. Now we consider only permutations for which these blocks are consecutive. Consider the second column, we have $n/a_i$ numbers (sums in blocks), they may be partitioned onto $n/a_1a_2$ superblocks of cardinality $a_2$ so that sum in each superblock is divisible by $a_2$. Proceed this way or use induction.

Improve this answer
$\endgroup$
8
  • $\begingroup$ " By EGZ applied to a first column (several times) we may partition rows to $n/a_i$ blocks so that the sum in each block is divisible by $a_i$." How is this obvious? Could you please elaborate just this part? I didnt understand how you could "partition" the rows into blocks of length $a_i$ when what the theorem gives you is just the existence of $a_i$ integers among $2a_i-1$ integers. $\endgroup$
    – Apurv
    Commented Jun 29, 2016 at 12:13
  • $\begingroup$ Choose the first block. Consider other numbers. Choose the second block, etc. The sum of the last block is automatically divisible by $a_1$. $\endgroup$
    – Fedor Petrov
    Commented Jun 29, 2016 at 12:50
  • $\begingroup$ One more question. How is the sum of the first P numbers in each column divisible by $a_j$? It is divisible by $a_1$ for the first column, as we have permuted the rows accordingly. Why will the same permutation work for all the columns? $\endgroup$
    – Apurv
    Commented Jul 2, 2016 at 18:26
  • $\begingroup$ After we fix blocks for the first column, we choose how rearrange them for the second column, uniting in greater blocks, and so on. $\endgroup$
    – Fedor Petrov
    Commented Jul 2, 2016 at 19:13
  • $\begingroup$ I get it. Was thinking maybe we could replace $P$ with any other multiple of $a_1,a_2,...,a_r$? The argument will still work in the same way, right? $\endgroup$
    – Apurv
    Commented Jul 3, 2016 at 5:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .