[Math] How many ways can a row of lights be turned on and off

combinatorics

Say you have a row of 4 lights. Each light-bulb can be turned on/off independently. How many lighting combinations could you come up with?

My research:

Before asking this question I searched the forum to make sure this wasn't a duplicate. I found similar questions, but they had restrictions which I'm not imposing.

For example this question required that a number of lights always be left on, and this question imposed a lighting pattern.

I simply want to know without restrictions how many combinations there could be.

Reading the answers to the linked questions above I learned about Pascals triangle.

Studying the triangle it appeared to me that the number of combinations possible for N (the number of lights in a row) is the sum of all the numbers in the row of pascal's triangle that has the same amount of numbers as n+1.

For example if I had 1 light, there are 2 combinations, on or off.

Pascals second row (the number of lights + 1) the sum of that row adds up to 2. Thus representing the total number of combinations.

Is that correct, and if it is, is there a more formal algorithm to represent this sort of problem without having to draw out a pascal triangle for large data-sets?

Best Answer

Each light has two positions and is independent of the others. By the multiplication principle there are $2^4=16$ possibilities. The row of Pascal's triangle that goes $1-4-6-4-1$ shows that there is one possibility with no lights on, four with one light on and so on. The sum is duly $16$

Related Solutions

Combinatorics – Minimum Switches to Turn Off 10×10 Light Bulbs

The minimum number of switches required is $100$.

This puzzle can be turned into a linear algebra problem over ${\Bbb Z}/2{\Bbb Z}$ by letting the vector $v\in({\Bbb Z}/2{\Bbb Z})^{100}$ record which switches are pressed ($1$ if pressed, $0$ if not), the vector $w\in({\Bbb Z}/2{\Bbb Z})^{100}$ record which lights are initially on ($1$ if on, $0$ if off), and the $100$-by-$100$ matrix $M$ over ${\Bbb Z}/2{\Bbb Z}$ record which switches affect which lights. A given $v$ will then solve the puzzle iff $Mv=w$.

As the questioner points out, $v=(1,\dots,1)^T$ is a solution. To show that this is the only solution, it's enough to show that $M$ is invertible.

Suppose that we press all the switches which are either in row $r$ or in column $c$. If a light is not in row $r$ and not in column $c$, its state will be changed twice. If a light is in row $r$ but not in column $c$, its state will be changed $10$ times, and similarly for a light in column $c$ but not in row $r$. The light at $(r,c)$ will have its state changed $19$ times. Therefore, the only light whose state ends up changing is the one at $(r,c)$. Since any desired light can be toggled, this shows that any configuration of lights can be turned off, so $M$ has full range and so must be invertible.

This puzzle is similar to the electronic game Lights Out.

Lights Out Variant – Minimal Number of Moves Needed to Solve

What you're trying to do is find the vector in the solution space with the minimum Hamming weight. Unfortunately, this problem is equivalent to the minimum distance problem in coding theory, which has been proven to be NP-hard (http://people.math.umass.edu/~hajir/m499c/vardy-complexity.pdf). That said, the implementation you link to can be sped up greatly by using ints as bit arrays and using bitwise operations, effectively parallelizing many of the operations.
Here's the quick-and-dirty Java solution I wrote for the Google Foobar challenge, which runs reasonably quickly and works for n <= 15.

public class GridZero 
{
    public static int[][] returnn3()
    {
        final int[][] n3={{284}, {149}, {78}, {63}};
        return n3;
    }
    public static int[][] returnn5()
    {
        final int[][] n5= {{17284592}, {8659223}, {4329627}, {2164829}, {1082430}, {1015839}, {31775}, {1023}};
        return n5;
    }
    public static int[][] returnn7()
    {
        final int[][] n7={{-2130838537, 122816}, {1082196484, 4191}, {541098242, 2159}, {270549121, 1143}, {135274560, 66171}, {67637280,  33149}, {33818640, 16638}, {33292288, 127}, {260096, 127}, {2032, 127}, {15, 114815}, {0, 16383}};
        return n7;
    }
    public static int[][] returnn9()
    {
        final int[][] n9={{-2143297553, -134480386, 130816}, {1075843080, 67240192, 
              65919}, {537921540, 33620096, 33215}, {268960770, 16810048, 
                  16863}, {134480385, 8405024, 8687}, {67240192, -2143281136, 
                  4599}, {33620096, 1075843080, 2555}, {16810048, 537921540, 
                  1533}, {8405024, 268960770, 1022}, {8372224, 0, 511}, {16352, 0, 
                  511}, {31, -268435456, 511}, {0, 267911168, 511}, {0, 523264, 
                  511}, {0, 1022, 511}, {0, 1, 131071}};
        return n9;
    }
    public static int[][] returnn11()
    {
        final int[][] n11= {{-2146435585, -1074266369, -537133185, 31456256}, {1074266368, 
              537133184, 268566592, 1050111}, {537133184, 268566592, 134283296, 
                  526079}, {268566592, 134283296, 67141648, 264063}, {134283296, 
                  67141648, 33570824, 133055}, {67141648, 33570824, 16785412, 
                  67551}, {33570824, 16785412, 8392706, 34799}, {16785412, 8392706, 
                  4196353, 18423}, {8392706, 4196353, 2098176, 16787451}, {4196353, 
                  2098176, -2146434560, 8394749}, {2098176, -2146434560, 1074266368, 
                  4198398}, {2096128, 0, 0, 2047}, {1023, -2147483648, 0, 2047}, {0, 
                  2146435072, 0, 2047}, {0, 1048064, 0, 2047}, {0, 511, -1073741824, 
                  2047}, {0, 0, 1073217536, 2047}, {0, 0, 524032, 2047}, {0, 0, 255, 
                  29362175}, {0, 0, 0, 4194303}};
        return n11;
    }
    public static int[][] returnn13()
    {
        final int[][] n13={{-2147221537, -16779265, -1073872913, -8389633, -536936456, 
              0}, {1073872912, 8389632, 536936456, 4194816, 268468235, 
                  511}, {536936456, 4194816, 268468228, 2097408, 134234125, 
                  511}, {268468228, 2097408, 134234114, 1048704, 67117070, 
                  511}, {134234114, 1048704, 67117057, 524352, 33558543, 
                  255}, {67117057, 524352, 33558528, -2147221472, 16779279, 
                  383}, {33558528, -2147221472, 16779264, 1073872912, 8389647, 
                  447}, {16779264, 1073872912, 8389632, 536936456, 4194831, 
                  479}, {8389632, 536936456, 4194816, 268468228, 2097423, 
                  495}, {4194816, 268468228, 2097408, 134234114, 1048719, 
                  503}, {2097408, 134234114, 1048704, 67117057, 524367, 
                  507}, {1048704, 67117057, 524352, 33558528, -2147221457, 
                  509}, {524352, 33558528, -2147221472, 16779264, 1073872927, 
                  510}, {524224, 0, 0, 0, 15, 511}, {63, -33554432, 0, 0, 15, 
                  511}, {0, 33550336, 0, 0, 15, 511}, {0, 4095, -2147483648, 0, 15, 
                  511}, {0, 0, 2147221504, 0, 15, 511}, {0, 0, 262112, 0, 15, 
                  511}, {0, 0, 31, -16777216, 15, 511}, {0, 0, 0, 16775168, 15, 
                  511}, {0, 0, 0, 2047, -1073741809, 511}, {0, 0, 0, 0, 1073610767, 
                  511}, {0, 0, 0, 0, 131071, 511}};
        return n13;
    }
    public static int[][] returnn15()
    {
        final int[][] n15={{-2147418115, -262153, -1048609, -4194433, -16777729, -67110913,
            -268443648, 0}, {1073774593, 131076, 524304, 2097216, 8388864, 
                  33555456, 134230015, 1}, {536887296, -2147418110, 262152, 1048608, 
                  4194432, 16777728, 67123199, 1}, {268443648, 1073774593, 131076, 
                  524304, 2097216, 8388864, 33569791, 1}, {134221824, 
                  536887296, -2147418110, 262152, 1048608, 4194432, 16793087, 
                  1}, {67110912, 268443648, 1073774593, 131076, 524304, 2097216, 
                  8404735, 1}, {33555456, 134221824, 536887296, -2147418110, 262152, 
                  1048608, 4210559, 1}, {16777728, 67110912, 268443648, 1073774593, 
                  131076, 524304, 2113471, 1}, {8388864, 33555456, 134221824, 
                  536887296, -2147418110, 262152, 1064927, 1}, {4194432, 16777728, 
                  67110912, 268443648, 1073774593, 131076, 540655, 1}, {2097216, 
                  8388864, 33555456, 134221824, 536887296, -2147418110, 278519, 
                  1}, {1048608, 4194432, 16777728, 67110912, 268443648, 1073774593, 
                  147451, 1}, {524304, 2097216, 8388864, 33555456, 134221824, 
                  536887296, -2147401731, 1}, {262152, 1048608, 4194432, 16777728, 
                  67110912, 268443648, 1073790974, 1}, {131076, 524304, 2097216, 
                  8388864, 33555456, 134221824, 536903679, 0}, {131068, 0, 0, 0, 0, 0,
                   16383, 1}, {3, -524288, 0, 0, 0, 0, 16383, 1}, {0, 524272, 0, 0, 0,
                   0, 16383, 1}, {0, 15, -2097152, 0, 0, 0, 16383, 1}, {0, 0, 2097088,
                   0, 0, 0, 16383, 1}, {0, 0, 63, -8388608, 0, 0, 16383, 1}, {0, 0, 0,
                   8388352, 0, 0, 16383, 1}, {0, 0, 0, 255, -33554432, 0, 16383, 
                  1}, {0, 0, 0, 0, 33553408, 0, 16383, 1}, {0, 0, 0, 0, 
                  1023, -134217728, 16383, 1}, {0, 0, 0, 0, 0, 134213632, 16383, 
                  1}, {0, 0, 0, 0, 0, 4095, -536854529, 1}, {0, 0, 0, 0, 0, 0, 
                  536870911, 1}};
        return n15;
    }


    public static int answer(int[][] matrix)
    {
        int[][] tm = toggleGen(matrix.length,matrix);
        int[][] mat = rref(tm);
        int zeroRow = mat.length;
        for (int i = mat.length - 1; i >=0; i--)
        {
            int status = 0;
            for (int j = 0; j < mat[0].length - 1; j++)
            {
                if (mat[i][j] == 1)
                {
                    status = 1;
                    break;
                }
            }
            if (status == 1) 
            {
                zeroRow = i+1;
                break;
            }
            else if (mat[i][mat[0].length-1] == 0) continue;
            else return -1;
        }
            int offset = 0;
            int changecheck = 0;
            int zeroRowcopy = zeroRow;
            for (int r = 0; r < zeroRowcopy; r++)
            {
                if (mat[r][r+offset] == 1) continue;
                else
                {
                    changecheck = 1;
                    mat[zeroRow++][r + offset] = 1;
                    offset++;   
                }
            }
        if (changecheck == 1) mat = rref(mat);


        int len = mat.length/32 + 1;
        if (mat.length % 32 == 0) len--;
        final int[] sol = new int[len];
        int weight = 0;
        for (int i = 0; i < mat.length; i++)
        {
            int val = mat[i][mat[0].length-1];
            sol[i/32] = (sol[i/32] << 1) | val;
            weight += val;
        }


        if (matrix.length % 2 == 0) return weight;
        final int[][] kernel;
        switch (matrix.length)
        {
        case 3: kernel = returnn3();
                break;
        case 5: kernel = returnn5();
                break;
        case 7: kernel = returnn7();
                break;
        case 9: kernel = returnn9();
                break;
        case 11: kernel = returnn11();
                break;
        case 13: kernel = returnn13();
                break;
        case 15: kernel = returnn15();
                break;
        default:
            kernel = returnn3();
        }
        int max = 1 << (2*(matrix.length-1));

        int minweight = weight;
        int res[] = new int[sol.length];
        for (int i = 1; i < max; i++)
        {
            int hamming = basisweighter(kernel,i,sol,res);
            if (hamming < minweight)
            {
                minweight = hamming;
            }

        }



        return minweight;

    }
    public static int basisweighter(final int[][] kernel, int weights, final int[] sol, int[] res)
    {
        int changes = weights ^ (weights-1);
        int changeint;
        int i = 0;

        while ((changeint = (changes >> i)) > 0)
        {
            if ((changeint & 1) == 1)
            {
                for (int k = 0; k < res.length; k++)
                {
                    res[k] ^= kernel[i][k];

                }
            }
            i++;
        }
        int weight = 0;
        for (int j = 0; j < sol.length; j++)
        {
            weight += NumberOfSetBits(res[j]^sol[j]);
        }
        return weight;

    }
    public static int NumberOfSetBits(int i)
    {
         i = i - ((i >>> 1) & 0x55555555);
         i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
         return (((i + (i >>> 4)) & 0x0F0F0F0F) * 0x01010101) >>> 24;
    }
    public static int[][] toggleGen(int n, int[][] mat)
    {
        int[][] ret = new int[n*n][n*n+1];
        for (int i = 0; i < n*n; i++)
        {
            int[] row = new int[n*n+1];
            for (int j = 0; j <= n*n; j++)
            {
                if (j == n*n)
                    row[j] = mat[i/n][i%n];
                else if (i/n == j/n)
                    row[j] = 1;
                else if (i%n == j%n)
                    row[j] = 1;
                else
                    row[j] = 0;
            }
            ret[i] = row;
        }
        return ret;
    }
    public static int[][] rref(int[][] mat)
    {
        int[][] rref = new int[mat.length][mat[0].length];
        int startRow = 0;
        for (int r = 0; r < rref.length; ++r)
        {
            for (int c = 0; c < rref[r].length; ++c)
            {
                rref[r][c] = mat[r][c];
            }
        }

        for (int c = 0; c < rref[0].length; ++c)
        {
            int pivotRow = -1;
            for (int r = startRow; r < rref.length; ++r)
            {
                if (rref[r][c] == 1)
                {
                    pivotRow = r;
                    break;
                }
            }
            if (pivotRow == -1) continue;
            if (pivotRow != startRow)
            {
                int[] temp = rref[pivotRow];
                rref[pivotRow] = rref[startRow];
                rref[startRow] = temp;
            }
            for (int r = 0; r < rref.length; r++)
            {
                if (r == startRow) continue;
                if(rref[r][c] == 1)
                {
                    for (int i = 0; i < rref[0].length; i++)
                    {
                        rref[r][i] ^= rref[startRow][i];
                    }
                }
            }
            startRow++;


        }

        return rref;
    }

}

Best Answer

Related Solutions

Combinatorics – Minimum Switches to Turn Off 10×10 Light Bulbs

Lights Out Variant – Minimal Number of Moves Needed to Solve

Related Question