Track / Stage 4 / 44 of 340 #784 of 2444

Problem 784

AMC 12 late, AIME early

Combinatorics Difficulty 4.3 Find the answer HMMT November · United States · 2023

There is a $6 \times 6$ grid of lights. There is a switch at the top of each column and on the left of each row. A light will only turn on if the switches corresponding to both its column and its row are in the "on" position. Compute the number of different configurations of lights.

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Official solution

Solution:

Take any configuration of switches such that there exists at least one row and one column which are switched on. There are $\left(2^{6}-1\right)^{2}=3969$ such configurations.

We prove that any two such configurations $A$ and $B$ lead to a different set of lights. Without loss of generality assume $A$ has row $r$ switched on and $B$ doesn't have row $r$ switched on. Thus, configuration $A$ will contain at least one light turned on in row $r$ (since there exists at least one column switch which is turned on), while configuration $B$ contains zero such lights turned on. Thus configuration $A$ and $B$ lead to different sets of lights.

All configurations where all columns or all rows are turned off lead to all lights being turned off. We add 1 extra option to account for this case, getting $3969+1=3970$ total possibilities.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.