Problem #61 HARD

The Inheritance Grid

Scenario Magic Squares Combinatorics Logic

Problem Statement

Is it possible to divide a 9×9 grid into three connected regions of 27 cells each, such that every row and every column contains exactly 3 cells from each region? If yes, describe a valid configuration.

Answer & Quick Explanation

Think you've got it? Click below to check your answer.

Yes, it is possible. Assign each cell (row i, column j) to region (i+j) mod 3. Each region appears exactly 3 times per row and 3 times per column, each region has 27 cells, and each region forms a connected diagonal stripe pattern across the 9×9 grid.

Detailed Editorial Solution

Want to see the step-by-step breakdown? Click below to reveal the editorial.

The key insight is to use modular arithmetic on cell coordinates. If we label cell (i,j) with value (i+j) mod 3, each value appears exactly 3 times in every row and every column, and the regions form connected diagonal stripes across the grid. Step 1: Define the labelling: cell in row i, column j (both 0-indexed from 0 to 8) gets label L(i,j) = (i+j) mod 3. Step 2: Prove balanced rows: in row i, column j ranges from 0 to 8. Values of (i+j) mod 3 for j=0..8: the nine values j mod 3 are {0,1,2,0,1,2,0,1,2}. Adding i (constant per row) just shifts the pattern cyclically — still exactly three 0s, three 1s, three 2s. Every row is balanced ✓. Step 3: Prove balanced columns: symmetric argument — in column j, row i ranges 0 to 8. Values (i+j) mod 3 cycle through each residue exactly 3 times ✓. Step 4: Prove connectivity: region 0 contains all cells where (i+j) mod 3 = 0. These form NE-SW diagonal stripes. Each stripe is connected along the diagonal, and adjacent stripes share corners — making the entire region connected ✓. Step 5: Each region has exactly 81/3 = 27 cells ✓. Kavya's solution: assign Kavya = label 0, Leela = label 1, Mala = label 2. Step 6: Visual: row 0 cells → labels 0,1,2,0,1,2,0,1,2. Row 1 → 1,2,0,1,2,0,1,2,0. Row 2 → 2,0,1,2,0,1,2,0,1. The three diagonal stripe regions are clearly connected. Key Insight: The formula L(i,j) = (i+j) mod 3 is the magic. It automatically satisfies both the row-balance and column-balance conditions due to the nature of modular arithmetic, and it produces connected diagonal regions. Modular indexing is a powerful tool for creating balanced, symmetric arrangements in grid problems.