Maths Olympiad Prep

Track / Stage 5 / 86 of 400 #686 of 1964

Problem 686

AIME late
Combinatorics Difficulty 5.2 Find the answer

8. A 3×33 \times 3 grid with the following properties is called a "T-grid":
(1) Five cells are filled with 1, and four cells are filled with 0;
(2) Among the three rows, three columns, and two diagonals, at most one of these eight lines has three numbers that are pairwise equal.
Then the number of different T-grids is \qquad.

A number or a short expression. Spacing, $ signs and \frac vs / are all fine.

Official solution

8. 68.

First, the number of all ways to fill a 3×33 \times 3 grid with five 1s and four 0s is C94=126\mathrm{C}_{9}^{4}=126.

Next, consider the number of ways that do not satisfy property (2), i.e., methods that result in at least two lines of three equal numbers (hereafter referred to as good lines).

We will count these by categorizing them. Good lines can be rows, columns, or diagonals.

If the two good lines are both diagonals, then they are all 1s, with 1 method;

If the two good lines are both rows (or columns), then one row is filled with 0s and one row is filled with 1s, there are C32×2×C31=18\mathrm{C}_{3}^{2} \times 2 \times \mathrm{C}_{3}^{1}=18 methods, by the symmetry of rows and columns, there are 2×18=362 \times 18=36 methods;

If the two good lines are one row and one column, in this case, the good lines are all 1s, there are 3×3=93 \times 3=9 methods;

If the two good lines are one row and one diagonal, in this case, the good lines are all 1s, there are 3×2=63 \times 2=6 methods;

If the two good lines are one column and one diagonal, in this case, the good lines are all 1s, there are 3×2=63 \times 2=6 methods.
Therefore, the number of methods that satisfy the property is
126136966=68 126-1-36-9-6-6=68 \text {. }

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.