# What branch of mathematics do these types of questions fall under and what would be a good book to get started with?

Questions such as:

You are walking by a row of $K$ ($4 \le K \le 25$) lights, some of which are on and some of which are off. In this initial conﬁguration, there is no consecutive sequence of four lights that are on. Whenever four or more consecutive lights are on, the lights in that consecutive block will turn off. You can only turn on lights that are off. What is the minimum number of lights you need to turn on in order to end up with all $K$ lights off?

What branch does this fall under? What would be a good book to get started with?

-
It's actually somewhat hard to tell without knowing the solution to the problem. It may look like a combinatorics problem but end up being a number theory or abstract algebra problem. Such things are not uncommon in mathematics. Also, some problems (the best ones!) admit different solutions from different branches, or perhaps have solutions which require methods from many branches! (This is a very long-winded way of saying "I'm not sure.") –  Qiaochu Yuan Aug 10 '11 at 15:38
Thanks for replying :) I see what you mean. I was just hoping that there would be some particular branch it would fall under. I keep on coming up with solutions to problems like these but my methods are haphazard and involve a lot of trial and error. I think my problem mostly stems from me being unable to represent the problem effectively and manipulate it. –  Rikaard Aug 10 '11 at 15:44

As Qiaochu said, it can be difficult to classify a problem. If you like problems of this flavor, however, I suggest you seek out a book on combinatorics. (In particular, you may find that you enjoy problems on "combinatorial designs.")

I find "A Walk Through Combinatorics" by Miklos Bona to be immensely readable. Though it does not cover designs, it does have many interesting problems that sharpen your general combinatorial skill.

If you would like take a look at designs, try "Combinatorial Designs" by W. D. Wallis. It is slightly more advanced, but you can work through it with some patience.

-
Thanks :) I'll take a look at these books. –  Rikaard Aug 10 '11 at 16:16

I would tentatively label this a problem in combinatorial optimization. You have a finite set of objects (the set of possible initial conditions), and you're trying to find one that maximizes a certain property (the minimum number of steps needed to turn all the lights off). I'm not sure whether that will help you find a solution, though. My guess is that a solution to this problem will require more general abstract thinking (whatever that means) than specific techniques from specific fields of mathematics.

Some thoughts. If you consider sequences like

o..o.o..o.o..o. etc.

where o denotes a lamp that's on and . denotes a lamp that's off, you cannot do better than getting rid of the lamps in pairs (by turning on two lamps) or triplets (by turning on three lamps). This gives a lower bound of approximately $\frac{2K}{5}$. I don't have an opinion on whether this is optimal.

-