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.
Sunday, July 26, 2020
Sunday, July 19, 2020
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}.$$
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}.$$
Sunday, July 5, 2020
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?
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?
Subscribe to:
Posts (Atom)