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+⋯+12)=75 electors, so the winning candidate must amass at least 38 electors.
If shire k has population Pk, the lowest popular vote within shire k for a winning candidate is achieved by receiving Pk+12 votes if shire k is won and 0 if shire k is lost by that candidate.
Let xk∈{0,1} with xk=1 denoting ``candidate wins shire k''. Then the minimal number of votes to achieve the outcome x=(x1,…,x10)∈{0,1}10 is c(x)=10∑k=1Pk+12xk=10∑k=1(5k+1)xk. Additionally, the formula for the number of electors achieved by the outcome x is E(x)=∑10k=1(2+k)xk.
This electoral problem can be recast as the following knapsack problem:
min
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)