Maths Olympiad Prep

Library / /52 of 92

Combinatorics Difficulty 6.5 National olympiad Prove it Iran

There are five keys that assigned to lamps of a room. Each key is connected to one or more lamps and by switching a key, all lamps which is connected to that key will be switched. The set of connected lamps to each key is distinct with another. If all lamps are turned off at the beginning, prove that there are 3 keys that by switching all of them at least two lamps will be turned on.

Solution

Let a1,a2,,ana_1, a_2, \dots, a_n denote the lamps, and b1,b2,,b5b_1, b_2, \dots, b_5 denote the keys. First, it is easy to see that n3n \ge 3, because otherwise there are at most 4 subsets of lamps and it's in contradiction with the assumption of the problem. Construct a 10×n10 \times n table that each row corresponds to a triple set of keys and each column corresponds to a lamp.

Figure 1

In intersection of row ii and column jj assign number 1 if after switching 3 keys corresponding to row ii, lamp aja_j turns on, and else assign 0. Denote the sum of row ii's numbers by ziz_i. Suppose lamp aia_i is connected to key XjX_j. Now sum of numbers in column jj is (Xj3)+(Xj1)(5Xj2)\binom{X_j}{3} + \binom{X_j}{1}\binom{5-X_j}{2}, so

i=110zi=j=1n((Xj3)+(Xj1)(5Xj2))(1) \sum_{i=1}^{10} z_i = \sum_{j=1}^{n} \left( \binom{X_j}{3} + \binom{X_j}{1} \binom{5-X_j}{2} \right) \qquad (1)

XjX_j is positive integer between 1 and 5. It's easy to check that (Xj3)+(Xj1)(5Xj2)\binom{X_j}{3} + \binom{X_j}{1}\binom{5-X_j}{2} phrase is always greater than 3. Because of equation 1, it is deduced that

i=110zi4n. \sum_{i=1}^{10} z_i \geq 4n.

Because of pigeonhole principle there exist ii so that zi4n102z_i \geq \lfloor \frac{4n}{10} \rfloor \geq 2 and we're done. ■

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 and solution reproduced as published; topic and difficulty added by this site.