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












Make your own free website on Tripod.com