OFFSET
1,1
COMMENTS
Quidditch is a sport invented by author J. K. Rowling for her fantasy book series Harry Potter.
In quidditch, the match ends when the snitch is caught. The team which caught it is awarded 150 points. All other scoring events are worth 10 points, and occur when the quaffle is thrown through one of the hoops.
A game is, therefore, a list of +10s and -10s, with a final entry of either +150 or -150. Negative points are for the away team, positive points are for the home team.
A tieless game is one in which the teams never have the same score (except at the beginning, when no team has scored yet).
For n <= 15 and all odd n: a(n) = 2*A063886(n)
REFERENCES
J. K. Rowling, Harry Potter and the Philosopher's Stone, Chapter 10, Bloomsbury, 1997.
LINKS
Cameron Ford, Table of n, a(n) for n = 1..333
Wikipedia, Quidditch
FORMULA
A063886(n-1) gives the number of n-1 step walks on a line starting from the origin but not returning to it. This is equivalent to the number of quidditch games with n scoring events which are tieless after the first n-1 scores (all of which are +10 or -10). Therefore, as the last score can be +150 or -150, there are 2*A063886(n-1) quidditch games with n scoring events which are tieless after n-1 scores.
To be tied after n scores, one team must be 150 points ahead after n-1 scores and then the other team must catch the snitch. If n-1 is less than 15, this cannot happen. Additionally, if n is odd, then after n-1 scores the difference between the scores is an even multiple of 10, so cannot be 150.
Now, for even n greater than 15, we must subtract from 2*A063886(n-1) the number of games which are tieless after n-1 scores but tied after n scores. For this to be the case, supposing the away team catches the snitch, we must have the game starting with +10, ending with -150 and with a block of n-2 +10s and -10s in the middle such that the net score after n-1 scores is +150 and the cumulative number of -10s in the n-2 block is never more than the cumulative number of +10s.
Catalan's triangles, Catalan(m,k) gives the number of sequences of m +10s and k -10s such that the cumulative number of -10s is never greater than the cumulative number of +10s. We require m+k = n-2 and m = k+14. Solving this gives m = (n+12)/2 and k = (n-16)/2. Doubling, to count the games where the home team catches the snitch, we have the number of games which are tieless after n-1 scoring events but tied after the snitch catch is 2*Catalan((n+12)/2,(n-16)/2) hence giving the formula below.
Therefore, the total number of tieless quidditch games with n scoring events is:
2*A063886(n-1) if n is odd or n < 16.
EXAMPLE
a(3) = 4 because to avoid a tie after two scoring events, the same team must score the first two goals, i.e., the game starts (+10,+10) or (-10,-10). Then there are two options for who catches the snitch. So the tieless games with three scoring events are (-10,-10,-150), (-10,-10,+150), (+10,+10,-150) and (+10,+10,+150).
PROG
(Python)
def number_of_tieless_quidditch_games(n):
"""
Takes an integer n, and returns a list containing the number of tieless
quidditch games with 1, 2, 3 .... n scoring events.
Note, the last scoring event is always catching the snitch, which gives
+150 if the home team caught it, or -150 if the away team caught it.
All scoring events prior to the snitch being caught are worth +10 or -10.
"""
dictionary_of_scores = {0:1}
# The keys of this dictionary represent possible scores.
# The values represent the number of ways this score can be reached with
# the game being tieless.
list_to_return = []
for i in range(n):
# We have a dictionary of tieless games with i ten point scoring events.
# Check still tieless after snitch catch
number_of_tieless_games = 0
for score, number_of_ways in dictionary_of_scores.items():
if score != 150: # away team can catch snitch without a tie
number_of_tieless_games += number_of_ways
if score != -150: # home team can catch snitch without a tie
number_of_tieless_games += number_of_ways
list_to_return.append(number_of_tieless_games)
# Update dictionary to have one more ten point scoring event
old_dictionary = dictionary_of_scores
dictionary_of_scores = {}
for scoring_event in (-10, 10):
for score, number_of_ways in old_dictionary.items():
new_score = score + scoring_event
if score + scoring_event != 0:
dictionary_of_scores[new_score] =\
dictionary_of_scores.get(new_score, 0) + number_of_ways
return list_to_return
CROSSREFS
KEYWORD
nonn
AUTHOR
Cameron Ford, Jul 03 2020
STATUS
approved