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 (12). pp. 155158.

Text
cut_MATKUTINT_1964_1__2_pp155__158.pdf  Published Version Download (1MB)  Preview 
Abstract
The general form of the lotterygame — as it is well known —is the following: On each lotteryticket 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 dhit on the lotteryticket. The socalled lotteryproblem in question is the following: what is the minimal of lotterytickets, so, that suitably selecting the 4 numbers on them, we can be sure to have at least one dhit? (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 ktuple of E. Let S be a system of ktuples of E. We say, that S has property P, if to each ltuple L of E there exists at least one ktuple of E belonging to S, which has at least d common elements with L. (We can say, that the dtuples of the ktuples belonging to S represent all ltuples of E.) Denote by N the number of ktuples belonging to S. The problem is as follows: What is the minimum of N, depending on n, k, l, d? We call an Ssystem with property P a minimalsystem 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 lotteryproblem essentially solved only in the case, when we want to be sure of a 2hit.
Item Type:  Article 

Subjects:  Q Science / természettudomány > QA Mathematics / matematika 
Depositing User:  János Boromisza 
Date Deposited:  27 Feb 2024 08:09 
Last Modified:  27 Feb 2024 08:14 
URI:  https://real.mtak.hu/id/eprint/189068 
Actions (login required)
Edit Item 