Maths Olympiad Prep

Library / /11 of 14

Combinatorics Difficulty 6.2 National olympiad Prove it Bulgaria

In every cell of a board 101×101101 \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.

(Borislav Kirilov)

Solution

(Vlad Spataru) Index the rows and columns from 00 to 100100. We shall only work modulo 101101 in what follows. Observe that we may let (0,0)=0(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), (u, v) + (i, j) = (u, j) + (i, v),
for any u,v,i,ju, v, i, j. Thus, there exist a0=0,a1,,a100a_0 = 0, a_1, \dots, a_{100} and b0=0,b1,,b100b_0 = 0, b_1, \dots, b_{100} so that (i,j)=ai+bj(i, j) = a_i + b_j. Now, letting Σa\Sigma_a and Σb\Sigma_b be the sum of the aia_i and the bjb_j respectively, the condition in the statement then yields Σa+Σb=0\Sigma_a + \Sigma_b = 0. Note that
i=0100x101bi=(i=1100xbi)101:=i=0xiα(i). \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 corresponds to the number of 101101-tuples with values from {b0,b1,,b100}\{b_0, b_1, \dots, b_{100}\} with sum equal to Σb\Sigma_b that is α(Σb)+α(101+Σb)+\alpha(\Sigma_b) + \alpha(101 + \Sigma_b) + \dots.
Using the fact that 101101 is prime and computing the latter expression for x=exp(2πi/101)x = \exp(2\pi i/101) we get the desired
0=i=0α(101i+Σb). 0 = \sum_{i=0}^{\infty} \alpha (101i + \Sigma_b).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.