Problem

Source: Iran Second Round MO 2018 - P5

Tags: combinatorics, Iran



Lamps of the hall switch by only five keys. Every key is connected to one or more lamp(s). By switching every key, all connected lamps will be switched too. We know that no two keys have same set of connected lamps with each other. At first all of the lamps are off. Prove that someone can switch just three keys to turn at least two lamps on.