Two combinatorial problems involving lottery schemes: Characterising solution set structures

Abstract

Consider a lottery scheme consisting 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 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). This is called a fc-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. One question considered in this paper is: In how many structurally different ways might the player achieve such a smallest possible playing set? Alternatively the player might only be able to purchase a playing set of cardinality l., in which case he may wish to construct his playing set so as to maximise the probability of winning a fc-prize. The other question addressed in this paper is: In how many structurally different ways might the player achieve this maximum resource utilisation? Both analytical arguments and computer searches are employed.