A Gale-Berlekamp permutation-switching problem

作者：Brualdi Richard A^*; Meyer Seth A

来源：European Journal of Combinatorics, 2015, 44: 43-56.

DOI：10.1016/j.ejc.2014.09.005

In the spirit of the light switching game of Gale and Berlekamp, we define a light switching game based on permutations. We consider the game over the integers modulo k, that is, with light bulbs in an n x n formation, having k different intensities cyclically switching from 0 (off) to (k - 1) (highest intensity) and then back to 0 (off). Under permutation switching, that is, adding a permutation matrix modulo k, given a particular initial pattern, we investigate both the smallest number R-n,R-k of on-lights (the covering radius of the code generated) and the smallest total intensity l(n,k) that can be attained. We obtain an explicit formula for l(n,k) when n is a multiple of k. We also determine R-n,R-k when k equals 2 and 3. In general, we obtain some bounds for R-n,R-k and l(n,k).

• 出版日期2015-2