[seqfan] Re: No progress on the classic "Football pools" problem in 52 years
Rob Pratt
robert.william.pratt at gmail.com
Sun Jun 27 16:55:38 CEST 2021
Just prepend each of the 9 strings with 0, 1, or 2, yielding 27, as mentioned in the comments section.
> On Jun 27, 2021, at 10:47 AM, Robert McKone <r.p.mckone at gmail.com> wrote:
>
> I am interested in actual examples of these strings (for purely
> mathematical reasons and totally not to gambling use). So in the
> literature there is an example of a(4) is {0000, 0112, 0221, 1022, 1101,
> 1210, 2011, 2120, 2202}. However I cannot find an example for a(5).
>
>> On Sun, 27 Jun 2021 at 16:04, Tomasz Ordowski <tomaszordowski at gmail.com>
>> wrote:
>>
>> I do not have a good heuristic for my formula, except the intuition that if
>> the extreme upper case occurs in general, then it must immediately follow
>> the extreme lower case; because if not, when?
>> Scanty data double my intuition /;-)
>>
>> Tom
>>
>>
>> czw., 24 cze 2021 o 20:27 Benoît Jubin <benoit.jubin at gmail.com>
>> napisał(a):
>>
>>> On Thu, Jun 24, 2021 at 3:42 PM Tomasz Ordowski <
>> tomaszordowski at gmail.com>
>>> wrote:
>>>
>>>> Conjecture: a((3^n+1)/2) = 3^((3^n+1)/2 - n) for n > 0.
>>>>
>>>
>>> Can you explain your reasoning ? It's obviously an upper bound since
>>> trivially a(n+1) <= 3a(n), but that looks like a lot of overlap. Did you
>>> study the structure of the Hamming codes in dimension (3^m-1)/2 ? The
>>> problem is that it's possible that there exist perfect non-Hamming codes
>> ?
>>> Or it's also possible that none of the three "layers" are actually
>> covered
>>> by the balls centered in these layers ?
>>>
>>> Using the known lower and upper bounds and the existence of perfect
>> Hamming
>>> codes, we have
>>> ceil(3^n/(2n+1)) <= a(n) <= 3^(n-floor(log_3(2n+1))) for n>=0
>>> but beyond that, I'm stuck.
>>>
>>> Benoît
>>>
>>>
>>>
>>>>
>>>> T. Ordowski
>>>>
>>>>
>>>> czw., 24 cze 2021 o 12:21 Benoît Jubin <benoit.jubin at gmail.com>
>>>> napisał(a):
>>>>
>>>>> Thanks Neil for the reference, which readily answers the question.
>> On
>>>> page
>>>>> 286 of that book, section "11.1 Perfect linear codes over \F_q",
>>>> paragraph
>>>>> "Hamming codes", it says that Hamming codes exist in theses
>> dimensions
>>>> and
>>>>> are perfect, which is what we want ("perfect" means that the balls do
>>> not
>>>>> overlap). So you may add to the sequence page:
>>>>> DATA: a(0) = 1
>>>>> OFFSET: 0
>>>>> COMMENTS (or FORMULA ?): a((3^m-1)/2) = 3^((3^m-1)/2 - m) follows
>> from
>>>> the
>>>>> existence of Hamming codes in these dimensions (see page 286 of
>> [Cohen
>>> et
>>>>> al.]).
>>>>>
>>>>> There are also many lower and upper bounds and asymptotics in this
>>> book,
>>>>> and some of them probably apply to the current sequence. (I won't
>> have
>>>> time
>>>>> to look at them more closely at the moment, but anyone reading this
>> is
>>>>> encouraged to do so.) One caveat: the book calls "sphere" what is
>>>> actually
>>>>> a "ball"... very unusual and puzzling until you discover it.
>>>>>
>>>>> Best,
>>>>> Benoît
>>>>>
>>>>> On Wed, Jun 23, 2021 at 8:04 PM Neil Sloane <njasloane at gmail.com>
>>> wrote:
>>>>>
>>>>>> Hi Benoit, The book by Gerard Cohen et al on Covering Codes is
>> really
>>>>>> excellent. I have it downstairs, if you seriously want me to go
>>> look.
>>>>>> Hamming codes are certainly relevant.
>>>>>>
>>>>>> Best regards
>>>>>> Neil
>>>>>>
>>>>>> Neil J. A. Sloane, President, OEIS Foundation.
>>>>>> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
>>>>>> Also Visiting Scientist, Math. Dept., Rutgers University,
>> Piscataway,
>>>> NJ.
>>>>>> Phone: 732 828 6098; home page: http://NeilSloane.com
>>>>>> Email: njasloane at gmail.com
>>>>>>
>>>>>>
>>>>>>
>>>>>> On Wed, Jun 23, 2021 at 1:14 PM Benoît Jubin <
>> benoit.jubin at gmail.com
>>>>
>>>>>> wrote:
>>>>>>
>>>>>>> It looks like A004044(0) = 1 !
>>>>>>> In that case, the trivial lower bound is attained. Actually, in
>>> the
>>>>>> known
>>>>>>> cases where 3^n/(2n+1) is an integer, then that lower bound is
>>>>> attained.
>>>>>>> This means that there is a solution with no overlaps. If this is
>>>> true
>>>>> in
>>>>>>> general, this is probably well-known by people knowing Hamming
>>> codes
>>>>> (of
>>>>>>> which I am not). Or did I misinterpret the problem ?
>>>>>>> Best regards,
>>>>>>> Benoît
>>>>>>>
>>>>>>> On Mon, Jun 21, 2021 at 6:52 AM Neil Sloane <njasloane at gmail.com
>>>
>>>>> wrote:
>>>>>>>
>>>>>>>> I grew up in a country where many people played the football
>>> pools
>>>>>> every
>>>>>>>> week (trying to guess the winners of next week's games: you
>> know
>>>>>>> Manchester
>>>>>>>> United is going to beat Arsenal, but there are 13 games to
>>>> predict).
>>>>>>>>
>>>>>>>> The classical problem translates into finding the smallest
>>> covering
>>>>>> code
>>>>>>> in
>>>>>>>> {0,1,2}^n with covering radius 1. The sequence (A004044)
>> begins
>>>>>>>> 1,3,5,9,27, but even after 52 years, a(6) is still not known.
>>>>> Tonight
>>>>>> I
>>>>>>>> came across a lot of references, which I have added to A004044.
>>>> a(6)
>>>>>> is
>>>>>>>> known to be 71, 72, or 73.
>>>>>>>> If you can solve it, you might not make any money, but you will
>>>>>> probably
>>>>>>>> get your name in the science section of the newspaper.
>>>>>>>>
>>>>>>>> Good publicity for the OEIS too!
>>>>>>>>
>>>>>>>>
>>>>>>>> Best regards
>>>>>>>> Neil
>>>>>>>>
>>>>>>>> Neil J. A. Sloane, President, OEIS Foundation.
>>>>>>>> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
>>>>>>>> Also Visiting Scientist, Math. Dept., Rutgers University,
>>>> Piscataway,
>>>>>> NJ.
>>>>>>>> Phone: 732 828 6098; home page: http://NeilSloane.com
>>>>>>>> Email: njasloane at gmail.com
>>>>>>>>
>>>>>>>> --
>>>>>>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>>>>>>
>>>>>>>
>>>>>>> --
>>>>>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>>>>>
>>>>>>
>>>>>> --
>>>>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>>>>
>>>>>
>>>>> --
>>>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>>>
>>>>
>>>> --
>>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>>
>>>
>>> --
>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>
>>
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list