Two Combinatorial Problems involving Lottery Schemes: Algorithmic Determination of Solution Sets

Abstract. Suppose a lottery scheme consists of randomly selecting a winning n{set from a universal m{set, while a player participates in the scheme by purchasing a playing set of any number of n{sets from the universal set prior to the winning draw, and is awarded a prize if k (or more) elements in the winning n{set match those of at least one of the player's n{sets in his playing set (1 k n m). Such a prize is called a k{prize. The player may wish to construct a smallest playing set for which the probability of winning a k{prize is at least (0 < 1), no matter which winning n{set is chosen from the universal set. Alternatively, the player might only be able to purchase a playing set of cardinality `, in which case he may wish to construct his playing set so as to maximise his chances of winning a k{prize. In this paper these two combinatorial optimisation problems are considered. The aim of the paper is twofold: (i) to derive growth properties of and establish bounds on solutions to these problems analytically, and (ii) to develop a number of algorithmic approaches toward nding respectively upper and lower bounds on the solutions to these problems numerically