Skip to main content
OlympiadHQ

Browse · MathNet

Print

Autumn tournament

Bulgaria counting and probability

Problem

In every cell of a board 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.

(Borislav Kirilov)
Solution
(Vlad Spataru) Index the rows and columns from to . We shall only work modulo in what follows. Observe that we may let by adding some constant to all the terms of the table. Next, because of the condition in the statement, for any . Thus, there exist and so that . Now, letting and be the sum of the and the respectively, the condition in the statement then yields . Note that Observe that the number of ways of adequately choosing one cell from each row corresponds to the number of -tuples with values from with sum equal to that is . Using the fact that is prime and computing the latter expression for we get the desired

Techniques

Generating functionsRoots of unityMatrices