Maths Olympiad Prep

Library / /1281 of 1394

, 2020

Number theory Difficulty 6.0 AIME, harder Prove it United States

Problem:

An 11×1111 \times 11 grid is labeled with consecutive rows 0,1,2,,100,1,2, \ldots, 10 and columns 0,1,2,,100,1,2, \ldots, 10 so that it is filled with integers from 11 to 2102^{10}, inclusive, and the sum of all of the numbers in row nn and in column nn are both divisible by 2n2^{n}. Find the number of possible distinct grids.

Solution

Solution:

We begin by filling the 10×1010 \times 10 grid formed by rows and columns 11 through 1010 with any values, which we can do in (210)100=21000\left(2^{10}\right)^{100} = 2^{1000} ways. Then in column 00, there is at most 11 way to fill in the square in row 1010, 22 ways for the square in row 99, down to 2102^{10} ways in row 00. Similarly, there is 11 way to fill in the square in row 00 and column 1010, 22 ways to fill in the square in row 00 and column 99, etc. Overall, the number of ways to fill out the squares in row or column 00 is 21222329210292821=21002^{1} \cdot 2^{2} \cdot 2^{3} \cdots 2^{9} \cdot 2^{10} \cdot 2^{9} \cdot 2^{8} \cdots 2^{1} = 2^{100}, so the number of possible distinct grids is 210002100=211002^{1000} \cdot 2^{100} = 2^{1100}.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.