The number of ways is divisible by 101

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

The number of ways is divisible by 101

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Bulgarian Autumn Tournament 2023, 10.4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1385 posts

#1 h Nov 19, 2023, 10:53 AM

Y by

In every cell of a board $101 \times 101$ is written a positive integer. For any choice of $101$ cells from different rows and columns, their sum is divisible by $101$ . Show that the number of ways to choose a cell from each row of the board, so that the total sum of the numbers in the chosen cells is divisible by $101$ , is divisible by $101$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1721 posts

oVlad

#2 h Nov 19, 2023, 5:13 PM

Y by

Index the rows and columns from 0 to 100. We shall only work modulo 101 in what follows. Observe that we may let $(0,0)=0$ by adding some constant to all the terms of the table. Next, because of the condition in the statement, $(u,v)+(i,j)=(u,j)+(i,v),$ for any $u,v,i,j.$ Thus, there exist $a_0=0,a_1,\ldots,a_{100}$ and $b_0=0,b_1,\ldots,b_{100}$ so that $(i,j)=a_i+b_j.$ Now, letting $\Sigma_a$ and $\Sigma_b$ be the sum of the $a_i$ and the $b_i$ resepctively, the condition in the statement then yields $\Sigma_a+\Sigma_b=0.$ Note that $\sum_{i=0}^{100}x^{101b_i}=\left(\sum_{i=1}^{100}x^{b_i}\right)^{101}:=\sum_{i=0}^\infty x^i\alpha(i).$ Observe that the number of ways of adequately choosing one cell from each row correspoonds to the number of 101-tuples with values from $\{b_0,b_1,\ldots,b_{100}\}$ with sum equal to $\Sigma_b$ that is $\alpha(\Sigma_b)+\alpha(101+\Sigma_b)+\cdots.$

Using the fact that 101 is prime and computing the latter expression for $x=\exp(2\pi i/101)$ we get the desired $0=\sum_{i=0}^\infty\alpha\left(101i+\Sigma_b\right).$

This post has been edited 2 times. Last edited by oVlad, Nov 20, 2023, 1:01 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5000 posts

#3 h Nov 19, 2023, 6:58 PM

Y by

I will actually show that if the sum of any $101$ cells from different rows and columns is fixed (i.e. doesn't depend on the choice of cells) modulo $101$ , then the number of ways to select a cell from each row of the board such that the sum is congruent to a (possibly different) fixed residue $r$ modulo $101$ is divisible by $101$ .

Index the rows and columns $0$ through $101$ and let $a_{x,y}$ denote the number at $(x,y)$ (the first coordinate is row number). We now work entirely in $\mathbb{F}_{101}$ (and relevant extensions)—note that $101$ is prime. By shifting all the entries by the same constant, assume $a_{0,0}=0$ . Because of the given condition, we have $a_{p,q}+a_{r,s}=a_{p,s}+a_{r,q}$ . Thus the rest of the grid is uniquely determined by row and column $0$ ; in particular, $a_{i,j}=a_{i,0}+a_{0,j}$ .

Now consider the generating function "of row $0$ ", which is
$F(x):=\sum_{j=0}^{100} x^{a_{0,j}}.$ Because $a_{i,j}=a_{i,0}+a_{0,j}$ , the generating function "of row $i$ " is thus
$\sum_{j=0}^{100} x^{a_{i,0}+a_{0,j}}=x^{a_{i,0}}F(x).$
If we multiply all the row generating functions, the number of ways to select an element of each row such that the chosen elements sum to $r$ is simply the sum of the coefficients of terms whose exponent is $r \pmod{101}$ . On the other hand, letting $s=a_{0,0}+\cdots+a_{100,0}$ , this product is just
$x^sF(x)^{101}=x^sF(x^{101})=x^s\sum_{j=0}^{100} x^{101a_{0,j}},$ by Frobenius Endomorphism/binomial theorem. If $r \neq s$ then we don't get any (nonzero) terms at all and this sum is thus $0$ . If $r=s$ then the coefficient sum is just $\underbrace{1+\cdots+1}_{101\text{ ones}}=0$ , so we're done in both cases. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1197 posts

#4 h Nov 19, 2023, 10:00 PM

Y by

Proposed by the legend Borislav Kirilov . There is a natural combinatorial solution as well - after obtaining $(u,v)+(i,j)=(u,j)+(i,v),$ as well as $(i,j)=a_i+b_j,$ when computing the sum of numbers in different rows, we see that it is $\sum a_i + \sum d_ib_i$ where $d_i$ is the number of cells in column $i$ among the $p$ chosen ones and hence it depends entirely on $(d_1,d_2,\ldots,d_p)$ . For any such tuple there are Multinomial( $p;d_1,\ldots,d_p$ ) possible collections of cells with this property and if at least two $d_i$ are non-zero, then it is a multiple of the prime $p = 101$ . (The case where only one $d_i = p$ is non-zero corresponds to cells in the same column and is checked easily separately.)

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a