Content deleted Content added
Iridescent 2 (talk | contribs) m →Covering problem: Cleanup and typo fixing, typo(s) fixed: ’s → 's |
tag with {{Bare URL PDF}} |
||
Line 1:
In [[coding theory]], a '''covering code''' is a set of elements (called ''codewords'') in a space, with the property that every element of the space is within a fixed distance of some codeword.
== Definition ==
Line 27:
== Football pools problem ==
A particular case is the '''football pools problem''', based on [[football pool]] betting, where the aim is to come up with a betting system over ''n'' football matches that, regardless of the outcome, has at most ''R'' 'misses'. Thus, for ''n'' matches with at most one 'miss', a ternary covering, ''K''<sub>3</sub>(''n'',1), is sought.
If <math>n=\tfrac12 (3^k-1)</math> then 3<sup>''n''-''k''</sup> are needed, so for ''n'' = 4, ''k'' = 2, 9 are needed; for ''n'' = 13, ''k'' = 3, 59049 are needed.<ref>http://alexandria.tue.nl/repository/freearticles/593454.pdf {{Bare URL PDF|date=March 2022}}</ref> The best bounds known as of 2011<ref>http://www.sztaki.hu/~keri/codes/3_tables.pdf {{Bare URL PDF|date=March 2022}}</ref> are
{| class="wikitable" style="text-align:center;"
| |||