On a problem concerning piles of counters

✍ Scribed by Keith Edwards

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 103 KB
• Volume: 156
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00050-7

✦ Synopsis

We show that a counter problem, originating from group theory, and due to R. Solomon, is NP-hard

I. Introduction

This paper concerns a problem which was raised by Cameron [1], and which originated with R. Solomon. It originates from a problem involving the lengths of chains of subgroups in classical simple groups. The problem is stated as follows:

Suppose that we have n counters divided into r non-empty piles, of sizes nl ..... n,. A move consists in replacing two piles of sizes ni and nj by a single pile of size ni + nj; the payoff for this move is 2 if nl = n j, and 1 otherwise. (It follows that after r -1 moves there is a single pile of size n.)

Cameron [1] asked (a) Is there a simple formula for the maximum total payoff which can be achieved? (b) If not, what is the complexity of calculating the maximum payoff?.

We will show that the answer to (b) is that the problem is NP-hard, at least in the case when the integers ni are given in binary. Although it might be more natural to insist that these integers are given in unary, since they represent numbers of counters, the NP-hardness in the binary case shows that the answer to (a) is almost certainly 'No'; i.e. that no simple formula is possible.

2. Proof of NP-hardness

We will prove that the following problem is NP-complete.