Maths Olympiad Prep

Library / /12 of 18

Combinatorics Difficulty 5.9 AIME, harder Find the answer Italy

Problem:

Little Boole has drawn a strip of 8 boxes, in each of which either a 0 or a 1 can be written. Initially every box contains a 0. At each move, Boole performs one of the following operations:

a. Replaces every 0 with a 1 and every 1 with a 0;

b. Chooses three consecutive boxes and, only in these, replaces every 0 with a 1 and vice versa.

How many different combinations of 0's and 1's can Boole obtain?

Pick one

Solution

Solution:

We observe that all the operations commute with one another, and that applying an operation twice is the same as not applying it. Hence we can associate to each operation an ON/OFF button (corresponding to whether or not that given operation has been carried out), and to each sequence of operations one and only one state of the buttons.

The combinations obtainable are then at most as many as all the possible states of the buttons, which are 272^{7}.

Suppose now, for contradiction, that there are two different states leading the 8 cells to contain the same numbers. This means that there exists a state of the buttons (not all set to OFF) whose result is to transform the combination 00000000 into itself.

Suppose that operation TT has been carried out. Then necessarily B1B_{1} and B6B_{6} have also been carried out (in order for the first and last cell to be 0). This means that B2B_{2} and B5B_{5} are OFF, otherwise the second and second-to-last cell would have a 1; for the same reason B3B_{3} and B4B_{4} are also OFF, but this would mean that cells 4 and 5 contain a 1, which is impossible.

Hence operation TT has not been carried out, so neither have B1B_{1} and B6B_{6}, otherwise the outer cells would have a 1. But then B2B_{2} and B5B_{5} are also OFF; similarly B3B_{3} and B4B_{4} must not have been carried out either, which is absurd because we had assumed that at least one operation had been performed.

Therefore each state of the buttons corresponds to a different combination, hence the reachable combinations are exactly 272^{7}.

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.