Two new combinatorial problems involving dominating sets for lottery schemes
Werner R. Grundlingh · SUNScholar (Stellenbosch University) · 2004
I, the undersigned, hereby declare that the work contained in this dissertation is my own original work and that I have not previously in its entirety or in part submitted it at any university for a degree. Signature: Date: Suppose a lottery scheme consists of randomly selecting an unordered winning n{subset from a universal set of m numbers, while a player participates in the scheme by purchasing a playing set of any number of unordered n{subsets from the same universal set prior to a winning draw, and is awarded a prize if k or more numbers in the winning n{set match those of at least one of the player's n{sets in his/her playing set (k n m). Such a prize is called a k{prize. A player may wish to construct a smallest playing set for which he/she is at least 100 % sure of winning a k{prize (0 < 1). From a dif-ferent perspective, a player may wish to construct a playing set of specied cardinality in such a way that the probability of winning a k{prize is maximised, regardless of the winning n{set. These situa-tions lead to the following two related combinatorial problems: (i) the incomplete lottery problem and (ii) the resource utilisation problem. The questions posed in these problems are: (i) What is the smallest possible cardinality of a playing set for which the probability of winning a k{prize is at least ? and