Library / /31 of 740

, 2023

Combinatorics Difficulty 4.3 AIME Find the answer United States

Problem:

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.

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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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