[seqfan] Re: game series

Peter Pein petsie at dordos.net
Sat Jan 29 00:20:53 CET 2011


On 28.01.2011 17:06, Robert Israel wrote:
>
>
> On Fri, 28 Jan 2011, Peter Pein wrote:
>
>> On 28.01.2011 10:10, Dmitry Kamenetsky wrote:
>>> Hello Sequence Fans,
>>>
>>> Recently I have been looking at the following problem. There is a 
>>> series of
>>> n games played between two teams. The outcome of each game is either 
>>> a win
>>> or a loss (no draws).
>>> A team wins the whole series if it wins k=floor(n/2)+1 games or 
>>> more. Now if
>>> a team reaches the magic number of k wins then the games that follow 
>>> (if
>>> there are any) are
>>> dead games, because their outcome cannot affect the outcome of the 
>>> series.
>>> So a natural question arises: out of all the possible 2^n series how 
>>> many of
>>> them will have
>>> at least one dead game? This forms the sequence 
>>> 0,0,4,4,20,24,88,116,372,...
>>> This sequence is not in the OEIS and neither is its version for all 
>>> odd n.
>> Hi Dimitry,
>>
>> what did I do wrong while trying to reconstruct the sequence 
>> {0,0,4,4,20,24,88..} ?
>>
>> I tried to find those sequences of wins/losses which contain a 
>> sequence of wins/losses of length >= Floor[n/2]+1 followed by at 
>> least one "dead" game:
>>
>> In[1]:= 
>> f[n_]:=Count[Tuples[{0,1},{n}],({___,0,s:1..,0,__}|{___,1,s:0..,1,__})/;Length[{s}]>=Floor[n/2]+1]
>> In[3]:= f/@Range[20]
>> Out[3]= 
>> {0,0,0,0,0,0,4,4,20,20,68,68,196,196,516,516,1284,1284,3076,3076}
>>
>> Did I misunderstand your definition? Please enlighten me!
>>
>> Cheers,
>>  Peter
>
> The last game is "alive" if and only if the result of the first n-1 games
> is either
> (if n is odd) (n-1)/2 wins for both teams, or
> (if n is even) n/2 wins for one and n/2-1 for the other.
> So if n is odd the number of series with at least one dead game is
> 2^n - 2 (n-1 choose (n-1)/2)
> and if n is even it is 2^n - 4 (n-1 choose n/2).
> This gives me 0, 0, 4, 4, 20, 24, 88, 116, 372, 520, 1544, 2248, 6344, 
> 9520, 25904, ...
> agreeing with Dmitry.
>
> Robert Israel                                israel at math.ubc.ca
> Department of Mathematics        http://www.math.ubc.ca/~israel 
> University of British Columbia            Vancouver, BC, Canada
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
Oh well, my counting has been too simple.
Thanks,
Peter




More information about the SeqFan mailing list