How High Can the Count Count?

The Riddler for September 16, 2016 carried the first ever Riddler Express alongside the usual Riddler Classic. Both are worked below.

Riddler Express

Count Von Count, the counting count on “Sesame Street,” counts aloud on Twitter. If he counts up by one with each tweet, “One!” “Two!” “Three!” … “Five hundred thirty eight!” and so on, how high can he go before hitting the 140-character limit? The Count is enthusiastic and must end every tweet with an exclamation point.

The Riddler, FiveThirtyEight, September 16, 2016(original post)

Solution

There is no clever formula here; spelled-out number lengths do not grow smoothly. But one structural fact settles the problem and tells us exactly where to look. The Count counts in order, so he is stopped by the first number whose tweet exceeds 140 characters, and the answer is the number just before it.

Write each number in words with single spaces, no commas and no “and” (the convention the puzzle uses), and add one character for the closing “!”. The length of a number’s tweet depends only on which words appear, so the longest tweets come from numbers built out of the longest words.

Below a trillion the Count is always safe. Every number under $10^{12}$ is read as at most four three-digit groups (billions, millions, thousands, units) joined by the scale words. The wordiest a three-digit group can be is twenty-seven characters, as in “three hundred seventy three” or “seven hundred seventy seven”. Even the worst case, a number like $373{,}373{,}373{,}373$, spells out to $137$ characters including the “!”. That is under the limit, so the Count sails past every number below $10^{12}$ without ever being stopped.

The wall is in the trillions. Once he reaches $10^{12}$ the reading gains a leading “one trillion”, and now the longest tails do cross 140. Searching upward from $10^{12}$, every count still fits, the wordiest of them landing exactly on the 140-character limit, until he reaches $1{,}111{,}373{,}373{,}373$, read “one trillion one hundred eleven billion … seventy three!”, whose tweet is the first to need 141 characters. He cannot post it, so the highest number he ever completes is one less: $$\boxed{1{,}111{,}373{,}373{,}372}$$ read as “one trillion one hundred eleven billion three hundred seventy three million three hundred seventy three thousand three hundred seventy two!”, a tweet of exactly 139 characters. The jump that defeats him is tiny: changing the final “two” to “three” adds two letters and tips him over.

The computation

Encode the spelling rule, then simply count upward and watch for the first overflow. To make the search quick we confirm the two structural claims directly: the worst tweet below $10^{12}$, and the worst tweet over the whole band from $10^{12}$ up to the answer, both stay within 140, while the next number does not.

ones = ["","one","two","three","four","five","six","seven","eight","nine","ten",
 "eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen",
 "eighteen","nineteen"]
tens = ["","","twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety"]
def grp(n):                              # spell a three-digit group 0..999
    w = []
    if n >= 100: w += [ones[n//100], "hundred"]; n %= 100
    if n >= 20:
        w.append(tens[n//10]); n %= 10
        if n: w.append(ones[n])
    elif n > 0: w.append(ones[n])
    return w
scales = [(10**12,"trillion"),(10**9,"billion"),(10**6,"million"),(10**3,"thousand")]
def spell(n):
    w = []
    for v, nm in scales:
        if n >= v: w += grp(n//v) + [nm]; n %= v
    return " ".join(w + grp(n))
def tweet(n): return len(spell(n)) + 1   # +1 for the exclamation point

target = 1_111_373_373_372
print("answer spell :", spell(target))
print("tweet length :", tweet(target), " next:", tweet(target+1))

# worst tweet below 10**12 (longest three-digit group is 27 chars, e.g. 373)
g = max(range(1000), key=lambda k: len(" ".join(grp(k))))
print("worst < 1e12 :", tweet(g*10**9 + g*10**6 + g*10**3 + g))

# worst tweet anywhere in [1e12, target]: scan the billions group 0..111
worst = 0
for b in range(112):
    lo = 10**12 + b*10**9
    hi = min(lo + 999_999_999, target)
    for n in (lo, lo + g*10**6 + g*10**3 + g, hi):   # candidate long tails
        if n <= target: worst = max(worst, tweet(n))
print("worst in band:", worst, " (all <= 140, and target+1 needs 141)")
# answer spell : one trillion one hundred eleven billion three hundred seventy
#                three million three hundred seventy three thousand three hundred
#                seventy two
# tweet length : 139  next: 141
# worst < 1e12 : 137
# worst in band: 140  (all <= 140, and target+1 needs 141)

Riddler Classic

You are one of 30 team owners in a professional sports league. The league used to set its draft order by record, worst team first. To discourage teams from losing on purpose, it switches to a new rule: every team tosses a coin, the teams that call correctly form Group A and the rest form Group B, all of Group A drafts before all of Group B, and within each group the order is still worst-record-first. If your team would have picked 10th under the old rule, what is your expected draft position under the new one?

Extra credit: suppose each team is assigned at random to one of $T$ groups, which draft in order. What is the expected draft position of the team with the $N$th-best record?

The Riddler, FiveThirtyEight, September 16, 2016(original post)

Solution

Your draft position is one more than the number of teams that pick ahead of you, so we just need the expected size of that crowd. A team picks ahead of you in exactly two situations, and they are easy to count separately.

Group the picks by where each rival lands. With the coin toss there are two groups, each team independent and equally likely to be in either. Your old pick was 10th, so $9$ teams have worse records than you and $20$ have better.

Teams in the earlier-drafting group. Whatever group you end up in, any particular other team is in the group that drafts before yours with probability $\tfrac14$: it must both pick the other group from you and have that be the earlier one. With $29$ other teams, that contributes $29 \cdot \tfrac14 = 7.25$ picks ahead of you on average.

Worse teams in your own group. A team with a worse record that shares your group drafts ahead of you (your group keeps the worst-first order). Each of your $9$ worse-record rivals shares your group with probability $\tfrac12$, contributing $9 \cdot \tfrac12 = 4.5$.

Better-record teams in your own group draft behind you, and they are the reason the new rule helps: half your superiors, on average, now pick after you. Adding the two contributions and the $+1$ for your own pick, $$\mathbb{E}[\text{position}] = 1 + 7.25 + 4.5 = \boxed{12.75}.$$ Your expected slot slips from 10th to 12.75th. The randomness costs you, which is the point: there is no longer anything to gain by tanking.

Extra Credit

With $N$ teams split at random into $T$ ordered groups, what is the expected draft position of the team whose old-rule pick was $i$ (so $i-1$ teams are worse and $N-i$ are better)?

Solution

The same two counts generalise. With $T$ groups, another team lands in an earlier group than yours with probability $\tfrac{T-1}{2T}$, by symmetry: of the $T-1$ ways the two of you land in different groups, half put them ahead. A worse-record team shares your group with probability $\tfrac1T$. So with $i-1$ worse teams and $N-1$ others, $$\mathbb{E}[\text{position}] = 1 + (N-1)\,\frac{T-1}{2T} + (i-1)\,\frac1T .$$ Expanding $1 + \tfrac{(N-1)(T-1)}{2T} + \tfrac{i-1}{T}$ and collecting the two pieces over $2T$ gives the tidy form $$\boxed{\;\mathbb{E}[\text{position}] = \frac{i}{T} + \frac{(T-1)(N+1)}{2T}\;}.$$ For $N=30$, $T=2$, $i=10$ this reads $\tfrac{10}{2} + \tfrac{1 \cdot 31}{4} = 5 + 7.75 = 12.75$, recovering the headline. The first term is your record showing through, scaled by how finely the groups slice the field; the second is the average drift the grouping adds, the same for everyone.

The computation

Encode the draft itself: assign each team a random group, count who drafts ahead, and average. Confirm the $12.75$ figure and the general formula at several $(N, T, i)$.

import random
def expected_position(N, T, i, trials=400_000):
    rng = random.Random(0); total = 0
    worse, better = i - 1, N - i
    for _ in range(trials):
        my = rng.randrange(T)
        ahead = 0
        for _ in range(worse):                 # worse teams: earlier group or your group
            g = rng.randrange(T); ahead += (g <= my)
        for _ in range(better):                # better teams: only if earlier group
            g = rng.randrange(T); ahead += (g < my)
        total += ahead + 1
    return total / trials

for N, T, i in [(30,2,10), (30,3,10), (50,4,25), (30,2,1)]:
    formula = i/T + (T-1)*(N+1)/(2*T)
    print(f"N={N} T={T} i={i}: formula={formula:.4f}  sim={expected_position(N,T,i):.4f}")
# N=30 T=2 i=10: formula=12.7500  sim=12.7365
# N=30 T=3 i=10: formula=13.6667  sim=13.6796
# N=50 T=4 i=25: formula=25.3750  sim=25.3747
# N=30 T=2 i=1:  formula=8.2500   sim=8.2369