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 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...

Finals week just ended for me so I'm hoping to post some new cool math problems in the next few days.  In this blog post, I present a math problem that is very easy to understand what it is asking, but not so easy to solve.  Regardless, I will present my solution, which yielded a very interesting result. You construct a sequence \( k_1, k_2, ..., k_m \) by randomly picking an integer from the set \( 0 \leq k_1 < n \).  After picking \( k_1 \), you repeat the process by picking \( k_2 \) randomly from \( 0 \leq k_2 < k_1 \) and repeat the process until you can no longer pick any numbers (when \( k_m = 0 \)).  Find a function for \( f(n) \), where \( f(n) \) is the expected value of the length of this sequence. Show/Hide Solution If \( n = 3 \), then the possible sequences are  \( \{ [0], [1,0], [2,0], [2,1,0] \} \), but these don't all occur with equal probability: \( P([0]) = \frac{1}{3}, P([1,0]) = \frac{1}{3}, P([2,0]) = \frac{1}{6}, P([2,1,0]) ...

In this blog post, I will discuss the solution to a very fascinating math problem that I came up with while pondering challenging math problems. The solution to this problem happens to be a really interesting combinatorics identity, and it can be used to describe some very interesting counting problems (including the number of ways to match parentheses). How many non-descending sequences of integers $ a_1, a_2, \dots, a_n $ are there such that $ 0 \leq a_i < i \: \forall \: i \leq n $? Show/Hide Solution If \( n = 1 \), the only possible sequence is \( a_1 = 0 \).  Similarly, for \( n = 2 \), the possible sequences are \( \{ [0,0], [0,1] \} \).  For \( n = 3 \), the possible sequences are \( \{ [0,0,0], [0,0,1], [0,0,2], [0,1,1], [0,1,2] \} \).  Let's let \( f(n) \) denote the number of valid sequences of length \( n \).  From these examples, it is clear that \( f(1) = 1, f(2) = 2, \) and \( f(3) = 5 \).  We would ideally like to get a nice combinat...