Lottery probabilty - graph problem

[andreass]

I have a problem, but don't know which way to try to solve it.


There is lottery: 3 numbers will be drawn out of 14. Each ticket with 2 correct numbers win.
If 5-8-14 will be drawn, I'll be winning also with my ticket 5-8-13 or 1-8-14 etc.

Total possible tickets = 364 (combin[14,3]). Total winning pairs = 91 (combin[14,2]).
1 ticket covers 3 pairs, that means I need not less (but maybe more) 91/3 = 31 ticket to have a guaranteed win.
What is the minimum number of tickets needed?

Hypergeometric distribution isn't exact thing needed (but maybe it can be used)



I think it could be also viewed as a graph problem.
We have complete graph, each ticket is 3-clique. Each pair of numbers is one edge.
What is the smallest number of triangles needed, to get full graph (Edges can overlap)

for ex.
K4 needs 3 traingles, to cover.
[URL]http://upload.wikimedia.org/wikipedia/commons/b/be/3-simplex_graph.svg[/URL]

K5 needs 4 triangles
[URL]http://upload.wikimedia.org/wikipedia/commons/2/2d/4-simplex_graph.svg[/URL]

K6 needs 6 triangles
[URL]http://upload.wikimedia.org/wikipedia/commons/e/e9/5-simplex_graph.svg[/URL]



Anyway - I don't need exact solution, just advice for right approach.

 

[mathman]

Since there are 273 losing tickets, you need 274 to guarantee a win.

 

[andreass]

Since there are 273 losing tickets, you need 274 to guarantee a win.

I think I didn't write clear enough :)
It is possible to have 273 different combinations (lottery tickets) if draw 3 out of 14.
But I win if at least 2 of 3 numbers are correct.
What is the minimum number of tickets that I need to buy, to be sure I'll win?

91 is the number of doubles that can win. Each ticket contains 3 such doubles.
That means I need at least CEIL(91/3) = 31 tickets.
That is bottom limit, but it doesn't mean it's the minimum tickets needed.

Example - if there was lottery 3 out of 4 (and 2 correct numbers also win), then I would need minimum 3 tickets (like 1-2-3, 1-3-4 and 2-3-4) to have a guaranteed win.

 

[mathman]

To guarantee a win, calculate the number of losing tickets and add 1.

 

[andreass]

To guarantee a win, calculate the number of losing tickets and add 1.

Your advice is not much of a help.
In the first post I stated that I don't know how to calculate minimum tickets needed and with which numbers should they be filled.

So if I fill all the tickets needed with respectively needed combinations, there will be no loosing tickets.

 

[mathman]

Since you don't know in advance what the winning numbers will be, you simply need to calculate how many possible tickets there are (364) and how many are winners (my count is 34, but I could be wrong), so the minimum needed is the difference + 1 = 331.

I got 34 as 33 with 2 correct and 1 with all 3.