CODEWITHSUNDEEP
algorithm
Straightfw
Straightfw

Reputation: 2211

Finding subsets being used at most k times

Every now and then I read all those conspiracy theories about Lotto-based games being controlled and a computer browsing through the combinations chosen by the players and determining the non-used subset. It got me thinking - how would such algorithm have to work in order to determine such subsets really efficiently? Finding non-used numbers is definitely crossed out as is finding the least used because it's not necesserily providing us with a solution. Also, going deeper, how could an algorithm efficiently choose such a subset that it was used some k times by the players? Saying more formally:

We are given a set of 50 numbers 1 to 50. In the draw 6 numbers are picked.

INPUT: m subsets each consisting of 6 distinct numbers 1 to 50 each, integer k (0<=k) being the maximum players having all of their 6 numbers correct.

OUTPUT: Subsets which make not more than k players win the jackpot ('winning' means all the numbers they chose were picked in the draw).

Is there any efficient algorithm which could calculate this without using a terrabyte HDD to store all the encounters of every possible 50!/(44!*6!) in the pessimistic case? Honestly, I can't think of any.

Upvotes: 1

Views: 135

Answers (3)

mcdowella
mcdowella

Reputation: 19621

If I wanted to run such a conspirancy I would first of all acquire the list of submissions by players. Then I would generate random lottery selections and see how many winners would be produced by each such selection. Then just choose the random lottery selection most attractive to me. There is little point doing anything more sophisticated, because that is probably already powerful enough to be noticed by staticians.

If you want to corrupt the lottery it would probably be easier and safer to select a few competitors you favour and have them win the lottery. In (the book) "1984" I think the state simply announced imaginary lottery winners, with the announcement in each area announcing somebody outside the area. One of the ideas in "The Beckoning Lady" by Margery Allingham is of a gang who attempt to set up a racecourse so they can rig races to allow them to disguise bribes as winnings.

Upvotes: 3

Irit Katriel
Irit Katriel

Reputation: 3564

If the number within each subset are sorted, then you can treat your subsets as strings - sort them in lexicographical order, then it is easy to count how many players selected each subset (and which subsets were not selected at all). So the time is proportional to the number of players and not the number of numbers in the lottery.

Upvotes: 1

ElKamina
ElKamina

Reputation: 7817

First of all, the total number of combinations (choosing 6 from 50) is not very large. It is about 16 million which can be easily handled.

For each combination keep a count of number of people who played it. While declaring a winner choose the combination that has less than k plays.

Upvotes: 3

Related Questions