Maths Olympiad Prep

Library / /12 of 13

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Italy

Problem:

A panel contains 100 light bulbs, arranged so as to form a square of 10 rows and 10 columns. Some of them are on, the others are off.
The electrical system is such that when the button corresponding to any one of the bulbs is pressed, all the bulbs that are on its column and all those that are on its row (including the bulb corresponding to the switch pressed) change state (that is, they turn on or off).

a) Starting from which configurations, by operating appropriately, is it possible to arrange for all the bulbs to end up on?

b) What is the answer to the previous question if the bulbs are 81, arranged so as to form a panel of 9 rows and 9 columns?

Solution

Solution:

a) It is easy to verify that if one presses the button of all the bulbs of a row and of a column, all the bulbs of the panel change state an even number of times, with the sole exception precisely of the bulb located at the intersection of the row and column considered, which changes state 19 times.
In short, these "moves" make it possible to turn on one bulb at a time. It is therefore possible to reach the configuration in which all the bulbs are on starting from any configuration.

b) In this case it is easy to verify that by pressing the button of a single bulb, the number of bulbs that change state on each individual row and on each individual column is in any case odd (either 1 or 9). A consequence of this fact is that a necessary condition for reaching the configuration in which all the bulbs are on is that at the start the number of bulbs that are on be even for all the rows and for all the columns, or be odd for all the rows and all the columns.
This condition is moreover also sufficient. Suppose in fact that we start from a configuration in which there is an odd number of bulbs that are off in each row and each column. Let us press the button of all the bulbs that are off. In this way every bulb that is on changes state as many times as there are bulbs that are off on its own row and on its own column, hence an even number of times (odd + odd), while every bulb that is off changes state an odd number of times (odd + odd - 1, where the "-1" serves to avoid counting twice the bulb in question that is off, once as a component of its row and once again as a component of its column): thus all the bulbs that are on remain on, and all those that are off turn on.
The same move, that is, pressing the button of all the bulbs that are off, also works if in the starting configuration there is an even number of bulbs that are off in each row and each column. Indeed, even in this case the bulbs that are on change state an even number of times (even + even), while those that are off change state an odd number of times (even + even - 1).

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 translated into English from it; metadata (topic, difficulty) added by this project.