On the lottery problem

Hanani, H. and Ornstein, D. and T. Sós, Vera (1964) On the lottery problem. A MAGYAR TUDOMÁNYOS AKADÉMIA MATEMATIKAI KUTATÓ INTÉZETÉNEK KÖZLEMÉNYEI, 9 (1-2). pp. 155-158.

Preview

Text cut_MATKUTINT_1964_1_-_2_pp155_-_158.pdf - Published Version Download (1MB) | Preview

Abstract

The general form of the lottery-game — as it is well known —is the following: On each lottery-ticket there are the integers 1, 2, . . ., n from which one has to select k numbers. After this l numbers are drawn out from 1, 2, . . ., n. If the set of numbers selected on a lottery ticket has exactly d common elements with the set of 1 numbers which have been drawn (d ≦ l ≦ k), we say, that we obtained a d-hit on the lottery-ticket. The so-called lottery-problem in question is the following: what is the minimal of lottery-tickets, so, that suitably selecting the 4 numbers on them, we can be sure to have at least one d-hit? (In the case of the lottery in Hungary n = 90, k = l = 5, l ≦ d ≦ 5). The general combinatorial problem according to this is the following: Let k, l, d, n be positive integers, 1 ≦ k ≦ n, 1 ≦ l ≦ n, 1 ≦ d ≦ min (k, l) and E a set with n elements. We call a subset of k elements of the set E a k-tuple of E. Let S be a system of k-tuples of E. We say, that S has property P, if to each l-tuple L of E there exists at least one k-tuple of E belonging to S, which has at least d common elements with L. (We can say, that the d-tuples of the k-tuples belonging to S represent all l-tuples of E.) Denote by N the number of k-tuples belonging to S. The problem is as follows: What is the minimum of N, depending on n, k, l, d? We call an S-system with property P a minimal-system S₀(n, k, l, d), if for this the value N₀(n, k, l, d) is the possible smallest. We give in this paper a lower bound for N₀ in case d = 2, and an asymptotic formula for it in case for fixed k, l, d = 2 and n → ∞. We can determine the exact value of N₀ and the minimal system S₀ only in the case k ≦ 5 d = 2 and for special values of n satisfying some congruences. (For example for the case n = 84 or n = 100 and k = 5). So we can consider the lottery-problem essentially solved only in the case, when we want to be sure of a 2-hit.

Actions (login required)

Edit Item