Content deleted Content added
removed spurious math, simplified lead |
Football pools problem |
||
Line 25:
Rodemich’s bounds <math>K_q(n,1)\geq q^{n-1}/(n-1)</math> and <math>K_q(n,n-2)\geq q^2/(n-1)</math>.<ref>E.R. Rodemich, Covering by rook-domains, ''[[Journal of Combinatorial Theory]]'', 9 (1970), 117-128</ref>
The covering problem is closely related to the packing problem in <math>Q^n</math>, i.e. the determination of the maximal size of a ''q''-ary ''e''-[[Error detection and correction|error correcting]] code of length ''n''.
== Football pools problem ==
A particular case is the '''football pools problem''', based on [[football pool]] betting, where the aim is to predict the results of <math>n</math> football matches as a home win, draw or away win, or to at least predict <math>n-1</math> of them with multiple bets. So this looks for a trinary covering <math>K_3(n,1)</math>.
If <math>n=\tfrac12 (3^k-1)</math> then <math>3^{n-k}</math> are needed, so for <math>n=4, k=2</math>, 9 are needed; for <math>n=13, k=3</math>, 59049 are needed.<ref>http://alexandria.tue.nl/repository/freearticles/593454.pdf</ref> The best bounds known as of 2011<ref>http://www.sztaki.hu/~keri/codes/3_tables.pdf</ref> are
{| class="wikitable"
! ''n''
! | 1
! | 2
! | 3
! | 4
! | 5
! | 6
! | 7
! | 8
! | 9
! | 10
! | 11
! | 12
! | 13
! | 14
|-
! <math>K_3(n,1)</math>
| '''1'''
| '''3'''
| '''5'''
| '''9'''
| '''27'''
| 71-73
| 156-186
| 402-486
| 1060-1269
| 2854-3645
| 7832-9477
| 21531-27702
| '''59049'''
| 166610-177147
|}
== Applications ==
| |||