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
    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
    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
    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
    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
    Jul 3, 2016 at 5:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.