Maths Olympiad Prep

Library / /3 of 10

Combinatorics Difficulty 5.6 AIME, harder Find the answer Italy

Problem:

Marina fills the cells of a 4×44 \times 4 grid by writing in each one the number 11, the number 22 or the number 33. In how many ways can the grid be filled so that the sum of each row and the sum of each column are divisible by 33?

Pick one

Solution

Solution:

The answer is (D). Let us start by filling the 3×33 \times 3 sub-table in the top left in any way we like: for each of the 99 cells we have 33 choices, hence in total 393^{9} possibilities. Now we show that, for each of these, the choice of the other 77 cells turns out to be forced and always possible.

Each of the first three cells of the fourth row (call them A,B,CA, B, C) is clearly forced by the sum of the three cells in its own column, and the same holds for the first three cells of the fourth column (D,E,FD, E, F).

Now the last remaining cell, in the bottom right, is forced by the sum of the cells in the last row and also by the sum of the cells in the last column: we show that these sums leave the same remainder upon division by 33, which allows us to conclude. Calling SS the sum of the 99 numbers chosen at the beginning, A+B+C+SA+B+C+S is a multiple of 33, and so is D+E+F+SD+E+F+S, but then A+B+CA+B+C and D+E+FD+E+F leave the same remainder upon division by 33, as we wanted. In particular, in the bottom right corner only the remainder of SS upon division by 33 can go (doing so, the sum of the columns on the fourth row has the same remainder upon division by 33 as A+B+C+SA+B+C+S, that is 00, and similarly for the fourth column).

Therefore for each of the 393^{9} initial choices there is one and only one working completion, so the answer is 393^{9}.

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 translated into English from it; metadata (topic, difficulty) added by this project.