Subsequence of Integers

When I was an undergraduate, a buddy, Wally Shook, (who passed away too young) posed the following problem to me in a milk bar (he was not the original author of the problem).

Given any sequence of n integers, positive or negative, not necessarily all different, some consecutive subsequence has the property that the sum of the members of the subsequence is a multiple of n.

I was totally unable to solve this problem, try as I might. Later, as a graduate student, privileged to be in the presence of the world renowned mathematician Hans Zassenhaus, I picked up a copy of a text on group theory he wrote when he was only 18. There, as an exercise, appeared the same problem phrased for arbitrary finite groups.

Given any sequence of n elements of a group of order n, some consecutive subsequence has the property that the product of the members of the subsequence, in sequence order, is the identity element of the group.

Somehow, this abstraction freed me from the wrong turns I had taken trying to solve the original problem. Number theory was irrelevant; the solution is more simple than I had imagined. I came up with the standard proof.

(Back to integers) Let a_i, i = 1, ..., n, be the given sequence. For i = 1,... ,n, define s_i as the sum of the first i integers of the sequence. If any one of the s_i are congruent 0 modulo n, then we are done. Otherwise, some pair of the s_i, say s_j and s_k, k > j, have the same nonzero remainder when divided by n. Hence the difference, s_k - s_j = a_j+1 + ... + a_k, the sum of a consecutive subsequence, is congruent 0 modulo n, equivalently, a multiple of n.

Let H be an n-element subset of a group G. Suppose that for every sequence of n elements from H, some consecutive subsequence has the property that the product of its elements is the identity of G. Then H is a subgroup of G.

I struggled with this problem, made some partial progress, and then enlisted a fellow graduate student Eugene V. Martin to join me in a search for a solution, counterexample or a proof.

Together we made more progress, we both becoming more convinced the problem statement was true, but no complete solution emerged. Eugene gave up his attempt for a phd in mathematics and turned to helping those less fortunate than himself. I continued plodding toward the phd.

Eventually I completed the degree requirements and went to work for the University of British Columbia. Homesickness dominated the loss in salary when I chose to return to Ohio State, where the presence of Zassenhaus spurred me to complete a solution of the problem. In spite of my feeling that I had solved a useless problem, I communicated it to Zassenhaus, thinking he might enjoy what I did with his exercise. Surprisingly, he insisted that I publish the result in the Illinois Journal of Mathematics (he made sure it was accepted).

I attached Eugene's name as a coauthor because he had contributed so much to the final solution (a very crude solution cleaned up beautifully by the referee).

When the paper appeared in the journal, Eugene called me to express his thanks. He was proud that his dream of being a mathematician was not a total loss; he has at least one published paper now, something few mathematicians can claim.

Speaking of sequences, there is a standard pigeonhole problem:

Given any sequence of mn + 1 real numbers, some subsequence of (m + 1) numbers is increasing or some subsequence of (n + 1) numbers is decreasing.

|Contact| |Front page| |Contents| |Up|

71546991