Skip to main content

Posts

Asteroids Algebra

Problem: Waldo is playing Asteroids. This game starts with 3 ships and you earn an extra ship for every 10000 points you score. At the end of his first game, Waldo noticed that he had the lowest score possible while averaging exactly 9000 points per ship. At the end of his second game, Waldo noticed that he had the highest score possible while averaging exactly 9000 points per ship. What were his two scores? Solution: Let the number of starting ships be \(S\), points for an extra ship be \(X\) and the player's average scoring rate be \(A\). Furthermore, let \(R = A/X\) and the number of bonus ships earned by the player during the game be \(B\). The number of bonus ships earned by the player during his game is the floor of his final score over the bonus value \(X\). Algebraically, we have \[ B = \lfloor (S+B)\cdot R \rfloor.\] Now let \[ (S+B)\cdot R = \lfloor (S+B)\cdot R \rfloor + f,\] where \( 0 \leq f < 1 \). This gives us \begin{aligned} (S+B)\cdot R &= B...

Interview Doubler

Problem: Find the smallest positive number that doubles when you move the last digit to the front. Solution: The answer is \( 105263157894736842 \), and the solution is similar to Twisty Temperature . Let this number be \[ x = x_{n}\cdot 10^{n-1} + ... + x_{1}\cdot 10^1 + x_{0} \] with \( 0 < x_{n} < 10 \), then after moving the last digit to the front we get \[ y = x_{0}\cdot 10^{n-1} + (x-x_{0})/10. \] We also have that \( y = 2 x \), so our equation becomes \[ 19\cdot x = x_0 \cdot (10^{n}-1). \] Now 10 is a primitive root modulo 19, and so it follows that \( x \) is integral if and only if \( n \) is of the form \( 18\cdot m \). Also note that we need \( 2 \le x_0 \le 9 \) since we require \( 0< x_{n} < 10\). When \( m=1 \) and \( x_0 = 2\) we get \( x  =105263157894736842 \); when \( m=2\) and \(x_0 = 2\) we get \[ 2 (10^{36}-1)/19 = 105263157894736842105263157894736842.\] That this number indeed doubles when you move the last digit to the front can be...

Twisty Temperature

Problem: When Waldo recently did a conversion of a positive integral Celsius temperature \( c = 275 \) to its Fahrenheit equivalent \( f \) (which turned out to be \( 527\) ), he noticed to his amazement that he could have simply moved the last digit of \( c \) to the front to obtain \( f \). Doing some intense calculations he failed to discover the next largest such example. Does one exist, and if so, what is it? Solution: Let \( c = x_{n}\cdot 10^{n-1} + ... + x_{1}\cdot 10^1 + x_{0} \) with \( x_{n} > 0 \), then \[ f = x_{0}\cdot 10^{n-1} + (c-x_{0})/10. \] We also have that \[ f = (9/5)\cdot c + 32. \] Notice that in order for \( f \) to be integral \( c \) must be divisible by 5; this implies that \( x_0=5 \) since it cannot equal 0 (since as a number \( f>c \)). Our equation then becomes \[ (9/5)\cdot c + 32 = 5\cdot 10^{n-1} + (c-5)/10 \] implies \[ c = 5\cdot (10^n - 65)/17. \] Now it turns out that 10 is a primitive root modulo 17, and so it follows that \( c \) ...

Lunchtime Sports Science: Introducing tanh5

As I mentioned in a previous article on ratings systems , the log5 estimate for participant 1 beating participant 2 given respective success probabilities \( p_1, p_2 \) is \begin{align} p &= \frac{p_1 q_2}{p_1 q_2+q_1 p_2}\\ &= \frac{p_1/q_1}{p_1/q_1+p_2/q_2}\\ \frac{p}{q} &= \frac{p_1}{q_1} \cdot \frac{q_2}{p_2} \end{align} where \( q_1=1-p_1, q_2=1-p_2, q=1-p \). Where does this come from? Assume that both participants each played average opposition. In a Bradley-Terry setting, this means \begin{align} p_1 &= \frac{R_1}{R_1 + 1}\\ p_2 &= \frac{R_2}{R_2 + 1}, \end{align} where \( R_1 \) and \( R_2 \) are the (latent) Bradley-Terry ratings; the \( 1 \) in the denominators is an estimate for the average rating of the participants they've played en route to achieving their respective success probabilities. In a Bradley-Terry setting, it's true that the product of the ratings in the entire pool is taken to equal 1. But participants don'...

Lunchtime Sports Science: Fitting a Bradley-Terry Model

Power rankings are game rankings that also allow you to estimate the likely outcome if two opponents were to face each other. One of the simplest of these models is known as the Bradley-Terry-Luce model (or commonly, Bradley-Terry). The idea is that each player \( i \) is assumed to have an unknown rating \( R_i \). If players \( i \) and \( j \) compete, the probability that \( i \) wins under this model is expected to be about \[ \frac{R_i}{R_i + R_j}. \] This model is very popular for hockey and other games; one commonly seen version is called KRACH . Let's fit a Bradley-Terry model to the current season of NCAA D1 men's hockey. The Frozen Four starts on Thursday, April 11, so you'll get to see how well your predictions do. You'll need to have R installed. Once R is installed, install the "BradleyTerry2" package that's freely available for R (thanks to Heather Turner and David Firth). To do this, start R and run the following command; you'll h...

Lunchtime Sports Science: Cracking a New Sport

This is the first and what will be a series of relatively short pieces on sports analytics. I'll be using a variety of sports for examples, including both team sports and single-player sports, and I'll also make my code available through my GitHub account . Here are my recommended tools. If you're unfamiliar with some of these, don't worry. You'll pick them up as you go along, and they form a powerful suite that will keep you on the cutting edge even as a professional data scientist. Hardware - Ideally you want at least 4GB of RAM for larger data sets, but you'll be able to do high-level analysis with almost any modern computing hardware. Linux operating system - You can certainly do top-notch data analysis using any operating system, but Linux is an excellent (and free) working environment. There are a variety of ways to install and use Linux, but I'd recommend  Ubuntu's Windows installer . This will allow you to easily install Ubuntu alongside W...

Solving Recurrences with Difference Equations

Here's an example from Robert Sedgewick's course on analytic combinatorics . Solve the recurrence \[ a_n = 3 a_{n−1} − 3 a_{n−2} + a_{n−3} \] for \( n>2 \) with \( a_0=a_1=0 \) and \( a_2=1 \). Let \( f(n) = a_n \); in the language of difference equations the above becomes simply \[ \frac{{\Delta^3} f}{{\Delta n}^3 } = 0 . \] Immediately, \[ f(n) = c_2 n^2 + c_1 n + c_0 . \] Applying the initial conditions we get \[ c_0 = 0, c_2 + c_1 = 0, 4 c_2 + 2 c_1 = 1, \] and so the solution is \( a_n =  \frac{1}{2} n^2 - \frac{1}{2} n \). Now what if the initial conditions are changed so \( a_1 = 1 \)?