2022 AMC 12B Problems/Problem 17
Problem
How many arrays whose entries are 0s and 1s are there such that the row sums (the sum of the entries in each row) are 1, 2, 3, and 4, in some order, and the column sums (the sum of the entries in each column) are also 1, 2, 3, and 4, in some order? For example, the array
satisfies the condition.
Solution (Linear transformation, permutation)
In this problem, we call a matrix that satisfies all constraints given in the problem a feasible matrix.
First, we observe that if a matrix is feasible, and we swap two rows or two columns to get a new matrix, then this new matrix is still feasible.
Therefore, any feasible matrix can be obtained through a sequence of such swapping operations from a feasible matrix where for all , the sum of entries in row is and the sum of entries in column is , hereafter called as a benchmark matrix.
Second, we observe that there is a unique benchmark matrix, as shown below:
With above observations, we now count the number of feasible matrixes. We construct a feasible matrix in the following steps.
Step 1: We make a permutation of rows of the benchmark matrix.
The number of ways is .
Step 2: We make a permutation of columns of the matrix obtained after Step 1.
The number of ways is .
Following from the rule of product, the total number of feasible matrixes is .
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
Solution
Let be the number of paths of moves such that the bug never will have been more than unit away from the starting position. Clearly, by symmetry, there are two possible states here, the bug being on the center and the bug being on one of the vertices of the unit hexagon around the center. Let be the number of paths with the aforementioned restriction that end on the center. Let be the number of paths with the aforementioned restriction that end on a vertex of the surrounding unit hexagon. We have since from the center, there are possible points to land to and from a vertex there are possible points to land to (the two adjacent vertices and the center). We also have , since to get to the center the bug must have come from a vertex, and since from a vertex there are two vertices to move to, and from the center there are vertices to move to. We can construct a recursion table using the base cases and and our recursive rules for and as follows: Then, and the desired probability is thus
-fidgetboss_4000
Video Solution
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)