A short essay on what the BEST solutions for various N were.
============================================================
The contest winner is the contest winner ... my intent is to
honor those runner-ups especially worthy of mention.
1. The choice of N=37, N=98, and N=153 were arbitrary -
designed only to provide three different modulos
base three since I was aware of the pigeonhole
theory. The "qualifying" rounds were necessitated
by the difficulty of checking "coverage" of the
solution sets (which took much more time than
actually computing the solutions!). I did NOT
anticipate that so few entries would progress
to the second round!!!
RECOGNITION AWARD 1: To "The Happy Hacker" for DuckAndCover
It is hard to dispute the efficacy of this entry.
DuckAndCover found the SMALLEST number of tickets
of all entries for all but four values up to N=96.
Unfortunately, DuckAndCover does not work for N>96!
Like several entries, DuckAndCover tries to find the
"best" division of the N tickets into three subsets,
and then finds a complete covering for each subset.
DuckAndCover used published coverings at the La Jolla
repository http://sdcc12.ucsd.edu/~xm3dg/cover.html
to accomplish this feat - unfortunately these only
cover up to M=32 and hence DuckAndCover only works up
to N=96. While this stretches the definition of
"precomputed solution" to its limits, I had previously
ruled that the program was legal since the data it
used did NOT solve the problem that was presented (even
though it was EXTREMELY useful when N less than 97!).
RECOGNITION AWARD 2: To Vincent Goffin for "ticketysplit"
ticketysplit did not make use of the LaJolla tables
in the program ... yet it managed to find about half
of the DuckAndCover solutions for N less than 96
and even managed to find BETTER ones in four cases!
Beyond N=96, nobody came close to ticketysplit's
solutions (of those I looked at). Unfortunately,
ticketysplit only found a 35 ticket solution for
the N=37 case and did not advance to the second round.
The following table has the best solutions that I
found by running some of the programs. NOTE - the
"coverage" for these cases was never checked for
any of these runs although the approaches seemed
to consistently cover at lower values of N.
These are (I think) the best solutions available from the entries
I looked at ... the starred solutions are from Vincent Goffin's
"ticketysplit" and the others (most N<96) are from DuckAndCover
from The Happy Hacker.
0 1 2 3 4 5 6 7 8 9
20 9 11 12 14 16
30 18 20 22 23 25 27 29 31 34 34
40 36 38 41 43 45 45 55 58 63 65
50 75 78 83 85 95 98 103 105 115 120
60 130 135 145 150 162 171 182 188 200 209
70 220 226 238 247 253* 258* 275* 292* 305 314
80 325 331 352 360 372 381 392 398 419 428
90 448 458 465 465 496 527 558 586* 614* 642*
100 669* 696* 723* 744* 765* 786* 821* 856* 891* 928*
110 965* 1002* 1039* 1076* 1113* 1150* 1187* 1224* 1261* 1298*
120 1335* 1375* 1415* 1455* 1495* 1535* 1575* 1577* 1579* 1581*
130 1599* 1617* 1635* 1647* 1659* 1671* 1696* 1721* 1746* 1761*
140 1776* 1791* 1813* 1835* 1857* 1865* 1873* 1881* 1892* 1903*
150 1914*
The table stopped at 150 only because I got tired of it all!
If you want more, the code for ticketysplit will be on the website.
=Fred