Virtual Math Circle: Summer 2021 Research Projects

Grab your closest dictionary. Choose a random three-letter word. We seek to know the probability that the word you chose is a palindrome, begins with the letter A, and has other characteristics. In fact, what’s the probability you chose “any”?

The elementary questions in this experiment will reduce to finding the probability of getting words of different types of length 3 from among the words of length 3 in the dictionary. If we consider all possibilities of 3-letter strings of letters, what’s the probability we receive a word from the dictionary? Once these questions are addressed, we will examine making a model of this experiment as a game. Once the basic model is established, we will try to optimize it: for the player, against the player and as a fair game. The basics of expectation in probability will be needed, as well as discrete probability.

Choose a random integer from the set of integers. The probability that you chose any specific number, say 5, is zero. However, if you happened to pick 5 just now, you’re probably wondering how this was possible if the probability of doing so is zero.

In this project, we examine the probabilities of getting integers from different number sets when choosing an integer randomly from the entire integers. We plan to examine this in both a limit context and a group theory context. Introductory questions that will be answered by this experiment include: What is the probability that a randomly generated integer is prime? What probabilities on the set of integers have positive value (i.e., a non-zero probability)? Can this experiment be treated as a variable in a group setting, and if so, does there exist an eloquent proof, not using the context of measure theory, to prove the variables are equivalent (or at least identically distributed) in the traditional sense? What real-life game is similar to our experiment (in a finite integer set case), and can we extend the game properly to an infinite number of integers?

We will develop an algorithm to use a fair coin to select from three mutually disjoint events with equal probability. We then hope to extend this result to the case of $n$ pairwise disjoint events, developing an algorithm so that, using a (two-sided) fair coin, each event has probability $1/n$.

If this can be achieved, we seek to generalize further by considering the case where the coin is no longer fair; that is, for some $p\in(0,1)$, we have $$P(\text{heads})=p,\qquad P(\text{tails})=1-p.$$

Under this modification, is it still possible to choose from among $n$ pairwise disjoint events so that each would occur with equal probability?

Possible extension:

Given an $n \times n$ square, can we fill it up with multiple non-overlapping squares, all with integer side lengths? For example, for $n=3$, we can use a $2\times2$ square and five $ 1\times1$ squares. But what's the fewest number of squares we need to fill the big square?

If $n$ is even, then clearly, the answer is 4. If $n > 3$ is an odd multiple of 3, then the answer is 9. In general, if $n$'s smallest prime factor is $p$, then the answer is at most $p^2$. But when is it smaller than $p^2$? And in particular, when $n$ is prime, what is the smallest number of squares?

Note: This would be a good problem for students with a little programming experience, who might be able to write some code to test out some cases and look for patterns.

The $stack$ $number$ of a graph $G$ is the smallest number $k$ such that $G$ has $k$ stacks where no two edges in the same stack cross. Is the stack number bounded by the queue number?

For this research project, we will explore this question through investigative methods. The main goals of this project would be to introduce students to graph theory and proof-based mathematics. In particular, this project would serve as an excellent introduction to research mathematics since extending known results to different structures is an excellent way to understand how to conduct research without starting entirely from scratch.