Ryan's Repository of Random Reflections

The topic of today's blog post is an interesting twist on the classical rock paper scissors game. Alice and Bob agree to play rock paper scissors (best of 1).  If Alice loses, she loses gracefully and accepts defeat.  If Bob loses, he will insist on playing best of 3.  If he loses yet again, he will insist on playing best of 5, and so on and so forth. What is Alice's probability of winning this game if she is willing to agree to Bob's request $k$ times (best of up to $K=2k+1$)? Let's begin by working out the formula for $k=1$, which is perhaps the most realistic scenario.  How much does Alice give up by agreeing to Bob's request once?  The probability of Alice winning a given round is $1/2$, and same for Bob (a round is consists of a sequence of ties followed by exactly one non-tie).  Here are the possible sequence of events, along with their probabilities, with A/B denoting that Alice/Bob wins the given round respectively. B - 0.5 - Bob wins in 1 turn AA -...

In this blog post, I will share a technique I have used in the past to evaluate linear recurrence relations efficiently using a little bit of linear algebra. As a motivating example, assume you have a sequence of numbers that you want to know more about: 1, 2, 3, 7, 24, 100, 448, 2051, 9444, 43549, 200889, 926770, 4275598, 19725314, 91002117, 419835526. Can you spot a pattern (hint: it's a 3rd order linear recurrence relation with constant term and a dependence on \( n \), the index into the sequence)? Once you figure it out, check out my other blog post on  finding recurrence relations from integer sequences to see if you came up with the same recurrence relation. By this point, you have figured out \( f(0) = 1 \), \( f(1) = 2 \), \( f(2) = 3 \), and \( f(n) = 5 f(n-1) - 2f(n-2) + f(n-3) - 2n + 1 \) for \( n \geq 3 \). Now let's say I want top compute the last \( 8 \) digits of \( f(10^{18}) \). A naive solution would be to write a for loop, but that would many orders...

In a lot of the recreational math and computer science problems I solve, I try to derive a recurrence relation that describes the situation. These recurrence relations pop up pretty often in counting problems (how many ways can you tile a 2xn grid with 2x1 tiles?) In some cases, I am unable to derive a recurrence relation directly from the problem statement, but still suspect that there exists some recurrence relation. In these cases, I end up solving the problem usin g brute force methods for small input sizes and analyzing/extrapolating the pattern. However, when the relation is obscure, it becomes hard to find. In order to make this process easier in the future, I created a program that can automatically find recurrence relations for arbitrary integer sequences. To use it, simply type in the first few terms of a sequence you are interested in, and it will try to find a recurrence relation for that sequence. There are some constraints on the allowable inputs/outputs which I di...