Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site asgb.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxn!ihnp4!qantel!lll-crg!seismo!hao!asgb!gupta
From: gupta@asgb.UUCP (Yogesh K Gupta)
Newsgroups: net.puzzle
Subject: Re: Winning 1/3 of the Lottery (*CORRECT AND SPOILER*)
Message-ID: <826@asgb.UUCP>
Date: Wed, 27-Nov-85 14:00:13 EST
Article-I.D.: asgb.826
Posted: Wed Nov 27 14:00:13 1985
Date-Received: Fri, 29-Nov-85 21:39:29 EST
References: <25@bbncc5.UUCP> <523@harvard.UUCP>
Reply-To: gupta@asgb.UUCP (Yogesh K Gupta)
Organization: Burroughs Corp. ASG, Boulder Colo.
Lines: 44

Q. What is the minimum number of tickets that one needs to buy, such
   that there are at least two matching numbers.

Assumption ASS0: The numbers on a ticket are distinct.

Assumption ASS1: The numbers on the tickets are not ordered (in ascending
	         or descending order).

Assumption ASS2: The number of matches does not depend on the position of
	         a number on the list. e.g. for the winning set {A1, A2, A3,
                 A4, A5, A6} the ticket: B1 B2 A1 B4 A5 B6 has TWO matches.
                                               ^^    ^^
Soln:
	a. First, the number of tickets that have no match:
		30*29*28*27*26*25 = 427518000 (na)

	b. The number of tickets that have EXACTLY one match:
		(30*29*28*27*26) * (6*6) = 615625920 (nb)
	   the expression in the first parenthesis is the ways in which
	   five numbers can be chosen that are not in the winning set,
	   and the second expression is the number of ways in which a
	   correct number can be chosen and where it is on the ticket.
	
	 .
	. . number of tickets you may have to buy before you are sure
	  of getting at least two correct numbers:
	    na + nb + 1 = 1043143921

	If ASS2 is dropped (but ASS0 and ASS1 hold), then the solution
	posted by a previous poster (sorry, I do not remember your name)
	is correct (41*35**5).

	If only ASS1 is dropped, the problem becomes quite interesting as
	certain numbers can not occur in the certain positions. e.g., if
	the numbers on a ticket are in ascending order, 32 can never occur
	in the first position. Also, if 31 was in the first position, the
	rest of the numbers would be determined as well.

-- 
Yogesh Gupta                           Advanced Systems Group,
{sdcrdcf, sdcsvax}!bmcg!asgb!gupta     Burroughs Corp., Boulder, CO.
--------------------------------------------------------------------
	All opinions contained in this message are my own and do not
	reflect those of my employer or the plant on my desk.