My question is purely about mathematics, but I think that a programming approach would also be relevant...
I'm wondering what's the minimal number of lottery tickets I need to buy to be sure that at least one of my tickets has N correct numbers.
For example, in a lottery game, we have to choose 5 numbers from 1 to 50. If they are the right 5 numbers, we win a big prize. If there are only 4, or 3, or 2 right numbers, we win a smaller prize. How many tickets do I have to buy, to have at least one ticket with 2 correct numbers? or 3 correct numbers? or 4 correct numbers?
Is there a smart way to generate this shortest list of combinations?
Here's my approach (for N = 2):
There are 1225 different pairs of numbers in the interval [1, 50] (the pairs 1+2, 1+3, ..., 1+50, 2+3, 2+4, ..., 48+49, 48+50, 49+50)
Every time I play a ticket, it covers 10 of these pairs (if I play 1-2-3-4-5, it represents the pairs 1+2, 1+3, 1+4, 1+5, 2+3, 2+4, 2+5, 3+4, 3+5 and 4+5)
So, it may be possible, with 123 well-chosen tickets, to cover every pair of numbers (if there's no overlap).
But all these tickets will contain all the 10 correct pairs of numbers. But I just need to find one good pair, not all of them. So maybe even less tickets will be enough.
I tried many computations but I couldn't figure out what is this minimal number of tickets to play, or how to generate them.
Are there existing theories or theorems on this subject? Is it possible to generalize it to 3, or 4 correct numbers?
Thanks for your help, or your ideas!