Let's say, I am playing a lotto where, $6$ numbers are chosen from $6$ different urns. Each urn contains the numbers $1, 2, ..., 59$.

I need to pick a set of 6 numbers $(x_1, x_2, x_3, x_4, x_5, x_6)$

If $3$ of the numbers I chose, match $3$ of the numbers drawn from the urn, I win.

e.g. if the numbers chosen from the urn are: $(1,1,2,3,4,5)$

then I win if I chose $(59,1,1,2,10,11)$ but not if I chose $(1,2,10,11,12,13)$

How many sets of $6$ numbers do I need to have: $(x_1, x_2, x_3, x_4, x_5, x_6)_1, (x_1, x_2, x_3, x_4, x_5, x_6)_2, ...$

In order to guarantee a victory?

Edit: a suboptimal solution is to have all $59^6$ possible sets (of 6 numbers); what is the optimal solution?

  • $\begingroup$ @JMoravitz so for the numbers chosen from the urn there is replacement involved, i.e. the numbers from the urn can be $(1,1,1,1,1,1)$ and I can choose any set of 6 numbers to play with, so how sets (of $6$ numbers) do I need to guarantee $100$% chance of victory; i.e. a suboptimal solution is to have all $59^6$ possible sets; what is the optimal solution? $\endgroup$ – mlguy Jan 8 '16 at 15:39
  • $\begingroup$ If you chose $(1,2,3,4,5,6)$ and the numbers drawn are $(1,10,3,10,2,10)$, does that count as a win? $\endgroup$ – Marcus Andrews Jan 8 '16 at 15:41
  • $\begingroup$ @MarcusStuhr yes! Order does not matter $\endgroup$ – mlguy Jan 8 '16 at 15:42
  • $\begingroup$ I think selecting all numbers between $([1,30] $ makes tge probabilty to win more than $50\%$ $\endgroup$ – Archis Welankar Jan 8 '16 at 15:43
  • 2
    $\begingroup$ @lottoguy Sorry, I don't get it. In your answer to Marcus' comment you claim that order doesn't matter. On the other hand your formula $59^6$ suggests that order does matter. Furthermore it is not clear to me if the numbers you pick need to be different or not. I assume not but then it is more difficult to define a win (e.g. pick six times 1, chosen from lottery is (1, 2, 3, 4, 5, 6) - a win?!). Could you clarify please? $\endgroup$ – Dr_Be Jan 8 '16 at 16:26

0) Let $@a_1, a_2, a_3, a_4, a_5, a_6@$ denote a sequence of $6$ chosen numbers from the urn of $59$ distinct numbers (with repetitions). There are exactly ${59+6-1 \choose 6} = \frac{64!}{6! \cdot 58!}$ such distinct sequences, see: https://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition

I understand that:

1) there is some previously chosen sequence $@x_1, x_2, x_3, x_4, x_5, x_6@$ (I will call this sequence WT - Winning Ticket) of numbers from the set $\{1,2, \dots, 59\}$ such that the condition of winning the lottery is that at least $3$ numbers from one of our sequences need to match WT;

2) by buying each lottery ticket we can create sequence such that is distinct from all other previously created sequences (if we had not such opportunity there were no question - because only by buying infinite number of tickets the probability of winning would be equal to $1$);

3) after choosing each sequence we return the numbers we picked to the urns - otherwise we would need only $59$ tickets until all the numbers run out.

4) The worst case scenario is when WT is a sequence $@x, x, x, x, x, x@$ for some $x \in \{1,2, \dots, 59\}$. This is because the number of sequences we can match is equal to $1$. It is the sequence $@x,x,x@$. For example, suppose there are $3$ urns each with $4$ numbers from $1$ to $4$ and winning condition is that at least two numbers from the sequences we choose need to match. If WT $= @1,1,1@$ then there is only one sequence we can match, it is $@1,1@$. If WT $=@1,1,2@$ we can match either $@1,2@$ or $@1,1@$.

We will then assume the worst case scenario. By 0) it is clear that if the winning condition was to match ALL the numbers from WT we would need to create all the possible sequences, i.e. $\frac{64!}{6! \cdot 58!}$. But we need only $3$ numbers to match. That means, that (in the worst case scenario) in order to win we have to create sequence $@a_1, a_2, a_3, x, x, x@$, where each $a_1, a_2, a_3$ are arbitrary numbers from the set $\{1,2, \dots, 59\}$.

Because order does not matter, $@a_1, a_2, a_3, x, ,x ,x@ = @a_2, a_3, x, x, a_1, x@$ e.t.c. But there are exactly ${59+3-1 \choose 3} = \frac{61!}{3! \cdot 58!}$ combinations with repetitions of the sequences $@a_1, a_2, a_3, x, x, x@$, where $x$ is fixed (which we need to match) and each $a_1, a_2, a_3$ belongs to $\{1,2, \dots, 59\}$ (which are arbitrary). That means there are $\frac{61!}{3! \cdot 58!}$ sequences we can pick that match WT at at least $3$ numbers. That means we need to buy $\frac{64!}{6! \cdot 58!} - \frac{61!}{3! \cdot 58!} +1$ tickets to be 100% sure to win the lottery.

  • $\begingroup$ Firstly I misunderstood the question. Secondly I wrote the wrong answer. I'm pretty sure that the above is the correct one. $\endgroup$ – Wojciech Karwacki Jan 9 '16 at 11:00
  • 1
    $\begingroup$ Couldn't we save tickets by choosing @1,1,1,2,2,2@ instead of @1,1,1,x,x,x@ and @2,2,2,x,x,x@? I feel the problem is more complicated. $\endgroup$ – Gyro Gearloose Jan 9 '16 at 12:44
  • 1
    $\begingroup$ You are right, I haven't thought about that. My first guess is that the problem is actually easier then. As soon as I will have some time I will come back to this question and will try to think about a solution. $\endgroup$ – Wojciech Karwacki Jan 9 '16 at 13:03
  • 2
    $\begingroup$ math.stackexchange.com/questions/66498/… $\endgroup$ – Wojciech Karwacki Jan 10 '16 at 10:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.