Over a million developers have joined DZone.

How Many Lights Can You Turn On?

DZone's Guide to

How Many Lights Can You Turn On?

· Big Data Zone ·
Free Resource

The open source HPCC Systems platform is a proven, easy to use solution for managing data at scale. Visit our Easy Guide to learn more about this completely free platform, test drive some code in the online Playground, and get started today.

Suppose you have a large n × n grid of lights, some turned on and some turned off. Along the side of each row is a switch that can toggle the lights in that row, turning on lights that were originally off and vice versa. There are similar switches along the top that can toggle the lights in each column. How many lights can you turn on?

The answer depends on the initial configuration. If they’re all on initially, for example, then you don’t need to do anything! But in the worst case, how well can you do?

Let aij be +1 or -1 depending on whether the light in the ith row and jth column is initially turned on or off. Let xi be +1 or -1 depending on whether the lights in the ith row are toggled, and let yjbe +1 or -1 depending on whether the lights in the jth column are toggled. It is always possible to choose the values of xi and yj so that

\sum_{i=1}^n \sum_{j=1}^n a_{ij} x_i y_j \geq \left(\sqrt{2/\pi} + o(1)\right) n^{3/2}

Here o(1) means a term that goes to zero as n increases. More on this notation here.

A light that is turned on contributes a +1 to the sum and a light that is turned off contributes a -1, so the sum tells us # lights on – # lights off. Of course # lights on + # lights off = n2, so the number of lights on is

\frac{n^2}{2} + \left(\sqrt{1/2\pi} + o(1)\right) n^{3/2}

(Note that o(1)/2 = o(1): half of an expression going to zero is still an expression going to zero.)

The proof takes about a page in The Probabilistic Method. The idea is to pick the yj randomly and then select the xi to maximize the sum. The lower bound comes from the expected value over the choices of the y‘s. Since the lower bound is the expected value, there must be some choice of y‘s that exceed or at least meet that value.

The theme of The Probabilistic Method is using probability to prove theorems that have nothing to do with probability. For example, sometimes the easiest way to prove an object with a certain property exists is to prove that the probability of selecting such an object at random is positive. As one of my professors used to say, some things are so hard to find that the best way to find them is to look randomly. Sometimes the thing you’re looking for has high probability, particularly in a limit, but your intuition is drawn to low probability exceptions.

Managing data at scale doesn’t have to be hard. Find out how the completely free, open source HPCC Systems platform makes it easier to update, easier to program, easier to integrate data, and easier to manage clusters. Download and get started today.


Published at DZone with permission of

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}