Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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@macalstr.edu and Herbert S. Wilf2 University of Pennsylvania Philadelphia PA 19104 wilf@central.cis.upenn.edu 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 71043.3326Qcompuserve.com 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 .
