A Conjecture by Erdos and Lemke

Let d be a divisor of n and suppose we have d divisors of n, not necessarily distinct, which we write as {a_i/ i = 1, 2,...d}. It is obvious that one can find a non-empty subset S of {1, 2,... d} such that the sum of the a_i's having index in S is a multiple of d. Erdos and Lemke (1987) framed the question: can one always find such a multiple that is at most n? In particular, one can consider the case d = n, in which the question becomes: Given d divisors of d, not necessarily distinct, can one always find a subset of them that sums to d? This was the problem first considered by Lemke in 1987.

A proof for the Conjecture

Lemke and Kleitman (1989) proved the following result to prove the problem of Erdos and Lemke:

Result (1989): Given a positive integer d and integers a₁, a₂, ... a_d, there exists a non-empty set Q ⊆ {1,2,..., d} such that d | ∑ {a_i} and , ∑ {gcd( a_i, d)} ≤ d.

Alternate method

The Pebbling game, first suggested by Lagarias and Saks, to give more intuitive proof for the above result.

The following theorem turns out to be an immediate consequence of some stronger and more general results that lead to an alternative proof for the above result (due to Lemke and Kleitman through a different method).

Chung's brilliance

Throrem (1989). For any distribution of 2ⁿ pebbles to vertices of the n-cube, one pebble can be moved to any specified vertex.

Chung proved the above theorem using pebbling game which was introduced by Lagarias and Saks. Chung successfully used this tool to give alternate proof which is shorter than the proof of Lemke and Kleitman. In doing so she introduced pebbling to the literature. Independently, Guzman also solved the same problem by a different proof.

So, the graph pebbling model was born as a method for solving a combinatorial number theory conjecture of Erdos and Lemke and has since been applied to problems in combinatorial group theory and p-adic diophantine equations. Related pebbling models have found applications in computational complexity, compiler theory, graph searching, sparse matrix factorization, and computational geometry. The subject has grown in the last three decades into a network optimization model for the transportation of consumable resources. For more information about its applications, Kindly click Applications section of this page.