As always ... there are consolation awards. Some folks actually
try and win these things - perhaps YOU will find your entry wins
one of these in the next POTM! There are also References below
as well as excerpts from the battle for the Belgian Chocolates!
** The most coveted BEST NAME award to Neelkanth Natu for jabri_mamu
> Neelkanth explains: In my native language
> jabri = Fantastic and mamu is a short form for
> a very beautiful lady by the name of MAMTA KULKARNI.
(This contest was so long that I hope they're still talking!)
** The runner-up almost best name to TroubleWithTriples from Randy Saint
While I'm not sure if Randy or Marianne Saint came up with
the name, I'm partial to arcane Star Trek references ... surely
all you youngsters remember the "tribble" episode ...
** The "somebody always tries it" award for program name goes to
something_clever - this time from Don Dykes ... do not
be discouraged ... but better luck next time!
** The "Maybe Next Time" award to Phillip Straite for Jester
who managed to find a 341,701 ticket solution to the
N=25 system test problem. Jester filled up my file
system on the first run of the finals ... oh well ...
** The best compilation instructions for Blotto from Ken Bateman
/* Instructions: make it, then retreat to a safe distance. */
** The NEWBIE award goes to Beth Wilson for Lot_O_Tickets
/* Note from Sam Wilson: I submitted a previous entry called */
/* TicketToElbonia. This entry is from my 14 year old, 9th */
/* grade daughter, Beth. The only thing I've done to her */
/* code is to make it compile on a Unix machine. She wrote */
/* it using Turbo C++ on our home PC. */
** BEST CLAIM OF BEING AN EX-NEWBIE award to Peter Zsolt who wrote:
I'm a student at Eotvos Lorand University, Budapest, and
am a programmer for 10 years know, which is half of my
** BEST "Reason To Enter The POTM" from Susan Adams
Susan wrote " I really just entered this contest because
a friend of mine said it was a good place to meet decent men."
Susan (who can be reached at ButtGirl_69@yahoo.com) provided
some of the more interesting POTM email I received (next
to the SPAM). I'm trying to hook Susan up with Paul Banta
(SWAG) to see what happens! Ain't free email grand???
** BEST PASCAL ENTRY LGVNWINH from Tran Huu Hoang (I use a Pascal
to C translator and this was the first "real" entry to try
it out ... it worked pretty well!!)
** BEST PERL ENTRY: Hole_Lotto_Love from John Williams
** BEST JAVA ENTRY: shroud_of_Turan from Ted Alper
** BEST SHELL ENTRY: Bozo4_TM_So_Close from Susan Adams
(ummm ... the ONLY shell entry!)
** BEST .edu ENTRIES: CMU and Stanford share the honrs ... Ted
Alper for "shroud_of_Turan" and the team
of Hal Burch and Danny Sleator from CMU
** BEST .org ENTRY: Prairie_Dog_Weiner from Thad Smith
** BEST REFERENCE to John Linerman (PackUpYourTriples) who suggests:
"The Joy of Cooking has some great recipes."
** The REAL BEST REFERENCES from various folks and my explorations:
This one from the Happy Hacker - author of DuckAndCover:
(also recommended by Vincent Goffin and Ted Alper)
the La Jolla covering repository - deals with "complete"
coverings of sets rather than this specific problem, but
it's as close as anyone found out on the web!
Vince Goffin adds:
I used ideas from the article "New Constructions for
Covering Designs" by D. M. Gordon, G. Kuperberg and O. Patashnik.
I used some code from Art Owen's netlib "oa" package for
finite fields and orthogonal latin squares.
Matthew Mullin (RockNRodl) helped us out with the following:
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
homepage of Iliya Bluskov
a lottery oriented page that tracks coverings
looks like an interesting paper ...
** Best suggestion for torture from Vincent Goffin:
... I'd like to see Luc and Alfons be forced to eat
their large box of chocolates in one afternoon session
for suggesting there may be an exact formula!
** SOME ANONYMOUS EXCERPTS FROM THE BELGIAN CHOCOLATE CONTEST ..
which nobody even came close to winning!!!
In the interest in staking my claim on that box of chocolates,
it seems to me that minimum number of tickets to beat this
lottery is in general always one more than the number of
losing tickets, and that no clever strategy can improve upon that.
======> equation inserted here
No proof available yet. My justifications of this intuition
are only the vaguest kind of handwaving. I will work on a
proof this coming weekend.
Greetings. My friend and I are working on the current POTM
contest. We think we have developed a formula to compute
the minimum number of tickets given N, M, and K. No proof yet,
but here it is:
======> equation inserted here
I can send you our derivation of this if you like.
I was surprised to see that no one had solved this yet.
I thought this was a rather elementary statistics problem ...
it is a basic result in statistics that the number of
combinations of N distinct objects taken R at a time is ...
======> lotsa stuff inserted here
Do I get my choclates now?
I have found an equation which I believe, I havn't finished
any proof yet, is correct. I hope its readable.
======> equations inserted here
If you draw it on paper with the sigma symbol it should be
readable. I scratched down the equation last night, so it
may be possible to clean it up a bit. I haven't had the
time to look into it. I will send You the proof as soon
as I have made one.