Maths Olympiad Prep

Library / /662 of 860

Algebra Difficulty 5.3 AIME, harder Find the answer

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 1 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.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

We begin by filling the 10 by 10 grid formed by rows and columns 1 through 10 with any values, which we can do in (210)100=21000\left(2^{10}\right)^{100}=2^{1000} ways. Then in column 0, there is at most 1 way to fill in the square in row 10, 2 ways for the square in row 9, down to 2102^{10} ways in row 0. Similarly, there is 1 way to fill in the square in row 0 and column 10, 2 ways to fill in the square in row 0 and column 9, etc. Overall, the number of ways to fill out the squares in row or column 0 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 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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.