- #1
andreass
- 16
- 0
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.
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.
Last edited by a moderator: