Electoral College Shenanigans

Given the division of Riddler Township into 10 unevenly populated shire, what is the lowest popular vote total that a winning candidate can achieve?
First, let's note that there are a total of $(3 + 4 + \dots + 12) = 75$ electors, so the winning candidate must amass at least $38$ electors.
If shire $k$ has population $P_k$, the lowest popular vote within shire $k$ for a winning candidate is achieved by receiving $\frac{P_k+1}{2}$ votes if shire $k$ is won and $0$ if shire $k$ is lost by that candidate.
Let $x_k \in \{0,1\}$ with $x_k=1$ denoting ``candidate wins shire $k$''. Then the minimal number of votes to achieve the outcome $x = (x_1, \dots, x_{10}) \in \{0,1\}^{10}$ is $$c(x) = \sum_{k=1}^{10} \frac{P_k+1}{2} x_k = \sum_{k=1}^{10} (5k+1) x_k.$$ Additionally, the formula for the number of electors achieved by the outcome $x$ is $E(x) = \sum_{k=1}^{10} (2+k) x_k.$
This electoral problem can be recast as the following knapsack problem:
$$\min \left\{ c(x) = \sum_{k=1}^{10} (5k+1) x_k : E(x) = \sum_{k=1}^{10} (2+k) x_k \geq 38, x \in \{0,1\}^{10} \right\}.$$ Solving this knapsack problem, we see that if a candidate wins $1-$, $2-$, $3-$, $4-$, $7-$, and $9-$shires with the minimal number of votes, then they would receive $38$ electors based on $136$ votes, or just $24.3\%$ of the popular vote.

The Indianapolis F(t)

Can the Hare Beat the Tortoise? Given his ability to outpace Tortoise by $25\%$, the mathematically minded Hare wants to minimize his margin of victory over his longtime foe. The magical racetrack expands proportionally by 10 miles instantaneously at each minute. Based on the magically expanding track length, Hare wants to know:
How long after the race has begun should Hare wait so that both Tortoise and Hare will cross the finish line at the same exact moment?
First, we will figure out how long it will take Tortoise to finish. To do so, since the total length is dynamic but expands proportionally, we will instead focus on the ratio of the track completed at time $t$. The total track length is $$F(t) = 10 (1 + \lfloor t \rfloor).$$ Thus, while the Tortoise's speed may be fixed at $60$ mph with respect to a fixed vantage point, Tortoise's closing speed with respect to the track length is $$v_T(t) = \frac{ 1 \,\,\text{miles / minute} }{ F(t)\,\, \text{miles / track}} = \frac{1}{10 (1 + \lfloor t \rfloor)}\,\, \text{track / minute}.$$ Tortoise will then finish the track at time $\tau$ such that $$\int_0^\tau v_T(t) \,dt = \sum_{k=0}^{\lfloor \tau \rfloor} \frac{1}{10(k+1)} + \frac{\tau - \lfloor \tau \rfloor}{10 (1 + \lceil\tau \rceil)} = 1.$$ Ignoring the ceilings and floors, gives us roughly $\frac{1}{10} H_{\tau+1} \approx \frac{ \ln (\tau+1) + \gamma }{10} = 1,$ so $\tau \approx \lceil e^{10 - \gamma} \rceil - 1 = 12366$ where $\gamma=0.57721....$ is the Euler-Mascheroni constant. Root solving further gives $\tau = 12365.4681....$

Knowing when Tortoise will complete the track allows our very mathematically inclined Hare to back into when he should start. Hare's relative velocity is $$v_H(t) = \frac{3}{2(1+\lfloor t\rfloor)},$$ if $t \geq t_0$ and $v_H(t) = 0$ if $t \leq t_0.$ So then we need to find $t_0$ such that \begin{align*}\int_0^\tau v_H(t) \, dt &= \int_{t_0}^\tau v_H(t) \,dt \\&= \frac{ 3(\lceil t_0 \rceil - t_0) }{20 (1 + \lfloor t_0 \rfloor)} + \sum_{k=\lceil t_0 \rceil}^{\lfloor \tau \rfloor} \frac{3}{20(k+1)} + \frac{3(\tau - \lfloor \tau \rfloor)}{20(1 + \lceil \tau \rceil)} = 1.\end{align*} If we ignore the first and last terms then we have approximately $\frac{3}{20} \ln \frac{\tau}{t_0} \approx 1,$ which should give $t_0 \approx \tau e^{-20/3} \approx 15.$ Root solving further gives $$\mathbf{t_0 = 15.2416....} \,\, \textbf{minutes}.$$

The many, many, many stars and a pinch of stripes for good measure

In the "Huh, that's neat ... I guess" category of number theory, the preamble to this week's Riddler Classic notes that the current number of states satisfies that $N$ is double a square and that $N+1$ is a centered pentagonal number.

After $50,$ what is the next integer $N$ with these properties?

After looking up the definition of a centered pentagonal number, it appears that they are of the form $$1 + \sum_{k=1}^n 5k = 1 + 5 \frac{n(n+1)}{2}.$$ So the question states find the minimal $N$ such that there exists integers $n$ and $m$ with \[ N = 2n^2 \,\, \text{and} \,\, N+1 = 5\frac{m(m+1)}{2} + 1.\] In particular, then we would have $$m^2 + m - \frac{4}{5} n^2 = 0$$ for some integers $m, n \in \mathbb{N}.$ Solving for $m$ in terms of $n$ we get $$m = \frac{-1 \pm \sqrt{1 + \frac{16}{5} n^2 }}{2}.$$ In order for $m$ to be an integer we would need $\sqrt{1 + \frac{16}{5}n^2}$ to be an odd integer, so in particular, we require that $5 \mid n.$

So we can brute force check whether the conditions hold for each multiple of $5$, until arriving at $n = 90,$ which gives $\sqrt{1 + \frac{16}{5} n^2} = 161$ and a grand total of $N = 2(90)^2 = 16,200$. This seems like either we would need much bigger flags, or much smaller states to accommodate a flag with those specifications. And at what point on our walk from $51$-ish states to $16,200$ would we reconsider the convention of only having 13 stripes for the original colonies?

Polly Gawn's Dot Connector

What is the greatest possible number of unique hexagons Polly can draw using six points?

For any 6 vertices $v_1, \dots, v_6$ and any permutation $\sigma \in S_6,$ we can draw an edge from $v_{\sigma_i}$ to $v_{\sigma_{i+1}}$ for $i = 1, \dots, 6.$ Polly would need to check that the edges do not intersect one another (besides at shared vertices) in order to verify that $\sigma$ defines a hexagon.

Line segments $\ell_1 = PQ$ and $\ell_2 = RS$ intersect if and only if $$((Q_2-P_2)(R_1-P_1)-(Q_1-P_1)(R_2-P_2)) ((Q_2-P_2)(S_1-P_1)-(Q_1-P_1)(S_2-P_2)) < 0$$ and $$((S_2-R_2)(P_1-R_1)-(S_1-R_1)(P_2-R_2)) ((S_2-R_2)(Q_1-R_1)-(S_1-R_1)(Q_2-R_2)) < 0.$$
Luckily Polly has chosen a reasonably small number of dots to connect, so that she can brute force the solution. There are $|S_6| = 6! = 720$ possible permutations, though each possible hexagon is described by $12$ such permutations: $6$ labels for vertex with largest $y$-value and two orientations (clockwise and counterclockwise).

Polly spun up the old Monte Carlo simulator and generated $N=10,000$ random sets of $6$ vertices, checked whether each of the $720$ possible permutations defined a hexagon, then divided by $12.$ The maximum number of unique hexagons was 29. This particular configuration involves two nested, but not concentric triangles, e.g., $$v_1 = (3.933833017, 2.610569057), v_2 = (9.739640057, 8.188125177), v_3 = (2.408262249, 7.450428529),$$ $$v_4 = (0.795494503, 9.711307153), v_5 = (4.004793527, 4.769703033), v_6 = (5.950340459, 7.124276426).$$

R. classicum ...? More like R. catalanii

The R. classicum reproductive behavior leads to some familiar combinatorial behavior involving the Catalan numbers. I'm not totally sure how to get the made up scientific nomenclature of a non-existent bacteria changed ... but I think we should look into it.

First the setup:
R. classicum either splits into two copies (with probability $p$) or dies (with probability $1-p$). If you start with a single R. classicum bacterium, what is the probability that it will lead to an everlasting colony (i.e., the colony will theoretically persist for an infinite amount of time)?

Theorem. The probability that a single R. classicum bacteria leads to an everlasting colony is \[E(p) = \max \left\{ 2 - \frac{1}{p}, 0 \right\}.\] In addition to the colony population at time $t$, $N_t,$ let's additionally catalog the history of a bacteria colony by tracking two quantities: $R_t$ and $D_t$, the number of reproductions/doublings and deaths that have occurred up until time $t.$ For consistency, let's define $R_0=D_0=0.$

Proposition. For each $t \geq 0,$ \[N_t = R_t - D_t + 1.\]
Proof. We will proceed by induction. The base case of $t = 0$ satisfies the equation.
Assume that for some time $t = \tau \geq 0$ that the formula holds, that is, $N_\tau = R_\tau - D_\tau + 1.$
Mechanically we see that $N_{\tau+1}$ is equal to twice the number of bacteria that reproduced at time $t = \tau+1$, so in particular \[R_{\tau+1} = \frac{N_{\tau+1}}{2} + R_\tau.\] Additionally, the remainder of the population at time $t=\tau$ that did not reproduce must have died, we have \[D_{\tau+1} = \left(N_\tau - \frac{N_{\tau+1}}{2}\right) + D_\tau.\] If we subtract the deaths equation from the reproductions, we get \[R_{\tau+1} - D_{\tau+1} = N_{\tau+1} - N_\tau + R_\tau - D_\tau.\] From the inductive hypothesis we have, $N_\tau = R_\tau - D_\tau + 1,$ so we can substitute above and get \[R_{\tau+1} - D_{\tau+1} = N_{\tau+1} - (R_\tau - D_\tau + 1) + R_\tau -D_\tau = N_{\tau+1} - 1,\] or equivalently $N_{\tau+1} = R_{\tau+1} - D_{\tau+1} + 1.$ Thus, by simple induction, the proposition holds for all time steps $t \geq 0.$

The corollary follows immediately.

Corollary. The colony population collapses if and only if there is some step $t > 0$ for which $D_t = R_t + 1.$

Using the corollary, we can then proceed with the proof of the main Theorem.

Proof. Let's calculate $1 - E(p),$ which is the the probability that the R. classicum colony eventually collapses. From the corollary, this means that there is some $t>0$ for which $D_t = R_t + 1.$ We see that the probability of a colony history with, say $k$ reproductions and $k+1$ deaths is $p^k (1-p)^{k+1}.$ Let $C_k$ denote the number of distinct colony histories that end in collapse after $k$ reproductions and $k+1$ deaths.
Then the probability of that the colony eventually collapses is \[1 - E(p) = \sum_{k=0}^\infty C_k p^k (1-p)^{k+1}.\] Now the only thing that remains to show is to find out what $C_k$ is (though I imagine you've already gathered where I'm going with this...). Since a population collapse needs to end it at least one death, the remaining $k$ reproductions and $k$ deaths can be ordered in any way such that the cumulative number of deaths is never more than the cumulative number of reproductions. Thus there is a simple bijection between colony histories with $k$ reproductions and $k+1$ deaths and nonnegative Dyck paths of length $2k$ (for instance set reproductions to ``up'' steps and deaths to ``down'' steps), of which there are \[C_k = \frac{1}{k+1} \binom{2k}{k},\] that is, the $k$th Catalan number, such paths.
Using the generating function for the Catalan numbers, \[c(x) = \sum_{n=0}^\infty C_n x^n = \frac{1 - \sqrt{1-4x}}{2x}\] we get that the probability of eventual colony collapse is \begin{align}1 - E(p) &= \sum_{k=0}^\infty C_k p^k (1-p)^{k+1}\\ &= (1-p) c\Big( p(1-p) \Big)\\ &= (1-p) \frac{ 1 - \sqrt{1 - 4p(1-p)}}{2p(1-p)} \\ &= \frac{1 - \sqrt{1-4p+4p^2}}{2p} = \frac{1 - |1-2p|}{2p}.\end{align} So, for $p > 0.5,$ we have \[E(p) = 1 - \frac{1-|1-2p|}{2p} = 1 - \frac{ 1 - (2p-1) }{2p} = 1 - \frac{2(1-p)}{2p} = 2 - \frac{1}{p};\] whereas for $p \leq 0.5,$ we have \[E(p) = 1 - \frac{1-|1-2p|}{2p} = 1 - \frac{1 - (1-2p)}{2p} = 1 - \frac{2p}{2p} = 0.\] Altogether, the formula $E(p) = \max\{ 2 - \frac{1}{p}, 0 \}$ is proved.

Editor's Note: I actually solved this brute force in Excel by setting up several steps of the process, seeing the when $p=0.8$ that the probability of having a zero population quickly to $0.25$. Varying the input value of $p$ quickly showed that the probability of having a zero population was $\min\{1,(1-p)/p\}$. However, I was convinced that there was a theoretical solution and was pleasantly surprised that it led solidly back to my undergraduate research in enumerative combinatorics with Prof. Ira Gessel at Brandeis University (cf. this sloppy arXiv article).

Editor's Note 2: This seems like a really convoluted way of proving that if the expected population of the colony decreases to zero over time (that is, when $p < 0.5$), that population collapse is almost certain. I suppose it is a roughly serviceable level of convolution for showing almost sure population collapse when the expected value is constant (that is, when $p=0.5$).