If it is easy to verify whether a solution to a problem is correct, is the problem easy to solve? This question is posed as the P vs NP problem and is considered one of the most important unsolved problems in Mathematics. This post will be brief and forgo many technical details surrounding the question for the sake of accessibility.
This post will outline the paper Finding Adam in random growing trees by Bubeck, Devroye, and Lugosi. The main question examined in this paper is simply stated and relatively unstudied: given a tree, which has been generated under some attachment model, find the first vertex. “First” here meaning oldest. Think about the spread of a rumor, or disease. In these situations, the resulting distribution is known, but the starting point is not.
The triangle removal lemma shows that if a lot of edges must be removed to make a graph triangle-free, then there must have been a lot of triangles in the original graph. While this observation may not sound ground breaking, it is a very useful tool in combinatorics.
Posts on with high probability focus on topics in combinatorics, probability, and theoretical computer science. Most are mathematically accessible to anyone who’s curious enough to read them!
The overall goal of this post is to prove that every impartial game is equivalent to a game of nim. While this result is often called the Sprague-Grundy theorem, the theorem doesn’t actually say anything about this conclusion. After proving the theorem, I’ll explain why a game’s equivalence to nim immediately follows.
Nim is a simple game, in which 2 players take turns removing objects from piles until there are no more objects left. This post will define basic terms for combinatorial game theory, detail the rules of nim, and explain how to win the game.
Games are the perfect mix of chaos and strategy: they are dynamic, since players’ decisions affect them, but there often exists an optimal way to play. This post discusses
- why we can solve some games but not others.
- how we solve these games.
- different processes developed along the way.
The solvability of tic-tac-toe, set take-away, Connect 4, checkers, and chess will be examined in further detail.