Ian Short

How quickly can a number of people, each with an unlit candle, light their candles from a single lit candle? This problem presented itself during a service in St. Mary’s Church in Maynooth, Ireland, to which I was kindly invited on Holy Saturday (3 April 2010). The congregation were seated in a block, and each person had an unlit candle. A single large lit candle sat in front of us and from this candle an altar girl lit her own portable candle. She then walked round the outside of the block of people lighting their candles one by one. Once a person’s candle was lit, they could light the candles of their neighbours. Soon everybody’s candles were lit. The situation is modelled in the diagram below.

The grey circles represent members of the congregation with their unlit candles. The altar girl is the circle at the front with a yellow (lit) candle. The altar girl proceeded clockwise around the block of candles, and they were lit as suggested by the following figure. (There were not actually eight rows of eight people; I don’t know how many people there really were.)

This can be considered as a discrete optimisation problem. The task is to light all the candles in the smallest possible time. At each stage of the model, each static member of the congregation can light the candle of one of the at most eight people directly surrounding them. Likewise the mobile altar girl can also light the candle of any one of the at most three people directly surrounding her, but she can also walk round the congregation block. Let us say that she can walk five steps up, down, left, or right during the time it takes to light a neighbour’s candle. What strategy should the congregation employ to light their candles as quickly as possible?

Let us ignore the altar girl for the moment, and suppose simply that the static person in the top right corner begins with his candle lit. He lights the candle of a neighbour, then he and the neighbour light the candles of a neighbour each, and so forth. So we see that on the kth stage, no more than 2^k candles can be lit. Thus, given a block of n by n people, it will take at least 2log₂(n) stages for all their candles to be lit. Since we have the constraint that a person can only light the candles of his or her neighbours, it is unlikely that this bound can be achieved. In fact, I think the optimal (fewest) number of stages is n+1, which is achieved using the strategy indicated by the next figure.

I doubt this bound can be beaten – at least, not by more than 1 – even if we adjust the person who initially has his or her candle lit. For an m by n group of people, I conjecture that the optimal number of steps is, in general, max(m,n)+1.

Introducing the altar girl increases the difficulty of the problem. Perhaps she should light the candle of one person, person A, near the centre of a side, and then walk all the way round to the other side and light the candle of the person directly opposite person A. I have yet to consider the problem in depth.