================= RockNRodl submitted by Matthew Mullin at mdmullin@alumni.princeton.edu ================= ++ Please summarize the algorithm used by RockNRodl After thinking about it for a little while, I realized that to make winning lottery tickets for the 7,3 case, you could divide N into 3 approximately equal parts and make a 7,3 cover on each of those parts. Whatever the king's 7 numbers are, there has to be at least 1 parts that contains 3 of the king's numbers (pigeonhole principle). If we put a group of 7-sets on each of these 3 parts so that each 3-set in each part is contained by at least one 7-set, then at least one of these 7-sets will intersect with the king's 7 numbers in at least 3 points. After taking into account special cases for N<21 (when the parts will be smaller than 7), this appears to be basically the best way to do it. It is the method implied by a lower bound equation in [CRC]. So we now want to find good 7,3-coverings for the various N we want. There are many ways to build coverings; unfortunately, there is no single method that works well for all regions of N, and they are more ideal for finding good coverings using a lot of time, rather than finding a good covering in a limited amount of time. The main method I have used is a simple recursive method. Let the coverings we are looking for be (k,l,n) for a covering of n with sets of size k that cover all subsets of size l, and the size of a covering be C(k,l,n). Then the main equation is: C(k,l,n)<=C(k,l,n-m)+C(k-m,l-1,n-m) for m=1..min(k-l+1,n-k), plus boundary conditions: C(k,k,n)=binom(n,k) All k-subsets of 1..n C(k,1,n)=ceil(n/k) Subsets 1..k, k+1..2k, etc So the main procedure &cover uses the above equation recursively, finding the best value of m for each instance. The results of this are approximately N^3/80. After coverings were calculated, the actual &lottery routine was called. For small values of N, we check out not-quite-equal partition of N into 3 parts -- for the test case, N=25, an even division is 8,8,9, which gives a total of 12 tickets; an uneven divison of 7,9,9 gives 9 tickets (basically because the best covering for 8 is still inefficient). Running with this basic algorithm, we get an answer of 11088 for N=200. The improvements added for the final submission were: Using an affine geometry (15,7,3) for the covering for N=15 and using a projection of that (just dropping points 15 and 14) for N=13 and 14. We then run the &cover recursive algorithm from N=16 to N=25 to make use of these new improved estimates, which improves them by 13 (if I remember correctly) - the difference between the old and new values for C(7,3,15). For larger values of N (>25), we make use of an affine geometry AG(125,25,3), which has size 155. Then we 'induce' a covering for N by choosing a random set of N points from 1..125 and taking the intersection of this set with each set in AG(125,25,3). If the intersection is of size 2 or less, we discard it; if it is from 3 to 7 we stick it on a new list; and if it is 8 to 25 we put in a precomputing covering. Using these improvements, we get an answer of 7321 for N=200 (may vary since we are using random numbers). In all cases, after we make our coverings and combine them into a lottery solution, we relabel the points so that the most numerous is 1, the next is 2, etc... This way the sum of the numbers on the tickets will be minimized. While constructing the coverings with &cover, we keep track of elements that are 'garbage', i.e. unneccessary to actually cover anything. While finding what partition of N will give us the fewest tickets, we use the most garbage as a tiebreaker; the garbage elements are later set equal to 1, 2, etc in increasing order, to minimize their contribution to the total ticket sum. With these methods, we are able to match the best result for the test problem (9 tickets, ticket sum 669). NOTES: For 7,3 coverings such that we are interested in, the best general lower bound is given by Schonheim [SCH]: ceil(N/7*ceil((N-1)/6*ceil((N-2)/5))) For the N=200 case, using a partition of 66,66,67 we get a lower bound of 4029. For a general large N, we get asymptotically N^3/1890 for the lottery problem. Rodl [ROD] proved that for fixed k and l (7 and 3), the lower bound is approached asymptotically. Rodl's proof was non-constructive, but in [GKPS] there are given two methods that are asymptotically optimal. One is a variant on the lex code (order all the 7-sets and always pick the first one that covers the most new 3-sets), and one is the generalization of the 'induce' method that is used in my program. Allowed more time for the program to run, there are multiple other methods in [GKP]. ++ Do you have any good references to recommend? These are all references that I made some use of, either giving some method that I used, or letting me know I was on the right track. [CRC] CRC Handbook of Combinatorial Design. [SCH] J. Schonheim, "On Coverings", Pacific Journal of Mathematics, 14, 1964, pp 1405-1411. [ROD] V. Rodl, "On a Packing and Covering Problem", European Journal of Combinatorics, 5 (1) 1985, pp 69-78. [GKPS] D. Gordon, G. Kuperberg, O. Patashnik, J. Spencer, "Asymptotically Optimal Covering Designs", Journal of Combinatorial Theory, series A, 75 (2) 1996, pp 270-280 [GKP] D. Gordon, G. Kuperberg, O. Patashnik, "New Constructions for Covering Designs", http://sdcc12.ucsd.edu/~xm3dg/cover.ps also Journal of Combinatorial Design, vol. 3, pp 269-281. Plus many resources on combinatorics in general: The Handbook of Combinatorics, R. Graham, M Grotschel, L. Lovasz, ed. Introduction to Combinatorial Theory, R.C. Bose, B. Manvel A Course in Combinatorics, R.M. Wilson, J.H. Van Lint. The Electronic Journal of Combinatorics, http://www.combinatorics.org And in general, any books or articles dealing with combinatorics, graph and hypergraph theory, Turan numbers, design theory or finite geometry ++ If I had it to do all over - here's what I would try .... First I would find out about the contest sooner so as to not cram it into the last few weeks. There were multiple methods that could be used for different regions of N (and k and l) for coverings that I either didn't have enough time to implement, or make fast enough or make use reasonable space. The cases with k=3,4,5 and l=2 are nearly totally known and would improve the 7,3 case substantially. I might have tried to use C instead of Perl if I had had time to write some list manipulation routines. It seems that specially designed C should be faster than Perl, plus by the end of the contest, I was getting tired of $ and @ in Perl, and wrestling with when to use references and when to use real variables, [] vs \, etc. Plus I would have sent in my final submission before 11:55pm on the last day and would have carefully tested it before (hopefully it works as well as earlier submissions did). ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? COMPANY: University of Detroit School of Dentistry, Materials Managemant FUN: Reading, games and puzzles of all sorts, sports (watching) SECRET: is a secret even from me :) POTM: More of the games (CHOMP,BOXING) or NP-complete problems in disguise (AIMLESS,KNIGHTCRAWLER). Basically things that you can get an idea on how to proceed, but not a simple, fast solution.