Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: When are subset sums equidistributed modulo m? | When are subset sums equidistributed modulo m Stan Wagon1 Macalester College St. Paul MN 55105 wagon@ and Herbert S. Wilf2 University of Pennsylvania Philadelphia PA 19104 wilf@ January 30 1994 Abstract. For a triple n t m of positive integers we attach to each t-subset S a1 . atg c 1 . ng the sum f S a1 at modulo m . We ask for which triples n t m are the n values of f S uniformly distributed in the residue classes mod m The obvious necessary condition that m divides n is not sufficient but a q-analogue of that condition is both necessary and sufficient namely qm - 1 q - 1 divides the Gaussian polynomial C We show that this condition is equivalent to for each divisor d 1 of m we have t mod d n mod d. Two proofs are given one by generating functions and another via a bijection. We study the analogous question on the full power set of n given n m when are the 2n subset sums modulo m equidistributed into the residue classes Finally we obtain some asymptotic information about the distribution when it is not uniform and discuss some open questions. 1 Until July 1994 P. O. Box 1782 Silverthorne CO 80498 2 Supported by the Office of Naval Research THE ELECTRONIC JOURNAL OF COMBINATORICS 1 1994 R3 2 1. Introduction While working on a problem related to lotteries Larry Carter of IBM and the hrst author were led to the question of the title. Positive integers n t and m are given. By a t-ticket we mean a subset of 1 2 . ng of size t. The value of a t-ticket is the modulo-m sum of its entries. Our question is for which triples n t m are the values of the t-tickets equally distributed among the m residue classes Let us call a triple uniform if equidistribution holds. There is an obvious necessary condition namely that n be divisible by m but this is not sufficient as the example n t m 5 2 2 shows. A special case of this question was considered by Snevily 4 . In this paper we will describe some of the experimentation .
