Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2023 SSMO Accuracy Round Problems/Problem 9"

(Created page with "==Problem== Consider a <math>2023 \times 2023</math> grid called <math>A = P_{2023}</math>. We take one of the four smaller <math>2022 \times 2022</math> grids located in <mat...")
 
Line 21: Line 21:
  
 
==Solution==
 
==Solution==
 +
 +
Let <math>a_{i,j,k}</math> denote the number of tuples with last element at position <math>(i,j)</math>, where <math>0 \le i,j \le k</math>, for <math>A = P_{k+1}</math>. Let <math>a_{i,j,k} = 0</math> if <math>i</math> or <math>j</math> is out of bounds. We want to compute <math>a_{1011,1011,2022}</math>.
 +
 +
We claim that
 +
<cmath>a_{i,j,k} = \binom{k}{i} \cdot \binom{k}{j}.</cmath>
 +
 +
Note that by considering the four possible placements of <math>P_{k}</math>,
 +
<cmath>a_{i,j,k} = a_{i-1, j-1, k-1} + a_{i-1, j, k-1} + a_{i, j-1, k-1} + a_{i, j, k-1}.</cmath>
 +
 +
Now verify the claimed closed form:
 +
<cmath>\binom{k}{i} \cdot \binom{k}{j} = \left(\binom{k-1}{i-1} + \binom{k-1}{i}\right)\left(\binom{k-1}{j-1} + \binom{k-1}{j}\right),</cmath>
 +
which expands and matches the recursive relation above.
 +
 +
This also agrees with base cases: the recurrence correctly handles out-of-bounds values, and <math>a_{0,0,0} = 1</math> holds.
 +
 +
Thus, we need to compute:
 +
<cmath>2 \nu_2\left( \binom{2022}{1011} \right) = 2 \left( \nu_2(2022!) - 2\nu_2(1011!) \right) = \boxed{16}.</cmath>

Revision as of 21:12, 9 September 2025

Problem

Consider a $2023 \times 2023$ grid called $A = P_{2023}$. We take one of the four smaller $2022 \times 2022$ grids located in $P_{2023}$ as $P_{2022}$. We repeat the process of taking smaller grids until we eventually converge at the unit square $P_1.$

[asy] size(7cm); filldraw((0,0)--(0,10)--(10,10)--(10,0)--cycle, opacity(0.2)+lightblue, blue); fill((0,0)--(0,9)--(9,9)--(9,0)--cycle, opacity(0.1)+lightblue); draw((0,9)--(9,9)--(9,0), blue); fill((1,0)--(1,8)--(9,8)--(9,0)--cycle, opacity(0.1)+lightblue); draw((1,0)--(1,8)--(9,8), blue); label("$A = P_{2023}$", (8.3, 9.52)); label("$P_{2022}$", (6.8, 8.52)); label("$\dots$", (4.78, 7.52)); [/asy]

Of the $4^{2022}$ distinct tuples of shrinking grids $(P_{2023}, P_{2022}, \dots P_1)$, let $T$ be the number of these tuples such that their last element is the center square of the original grid $A$. Find the largest integer $a$ such $2^a \mid T.$

Solution

Let $a_{i,j,k}$ denote the number of tuples with last element at position $(i,j)$, where $0 \le i,j \le k$, for $A = P_{k+1}$. Let $a_{i,j,k} = 0$ if $i$ or $j$ is out of bounds. We want to compute $a_{1011,1011,2022}$.

We claim that \[a_{i,j,k} = \binom{k}{i} \cdot \binom{k}{j}.\]

Note that by considering the four possible placements of $P_{k}$, \[a_{i,j,k} = a_{i-1, j-1, k-1} + a_{i-1, j, k-1} + a_{i, j-1, k-1} + a_{i, j, k-1}.\]

Now verify the claimed closed form: \[\binom{k}{i} \cdot \binom{k}{j} = \left(\binom{k-1}{i-1} + \binom{k-1}{i}\right)\left(\binom{k-1}{j-1} + \binom{k-1}{j}\right),\] which expands and matches the recursive relation above.

This also agrees with base cases: the recurrence correctly handles out-of-bounds values, and $a_{0,0,0} = 1$ holds.

Thus, we need to compute: \[2 \nu_2\left( \binom{2022}{1011} \right) = 2 \left( \nu_2(2022!) - 2\nu_2(1011!) \right) = \boxed{16}.\]

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_SSMO_Accuracy_Round_Problems/Problem_9&oldid=260177"