|
Daniel Skora
email: dskora (at) umich (dot) edu
|
I am a first-year computer science Ph.D. student at the University of Michigan working with Seth Pettie on combinatorial problems. More specifically, my current research involves pattern avoidance in 0-1 matrices. Before this, I was at Indiana University, where I completed my bachelor's in CS and math. During this time I also worked with Saúl Blanco on the enumeration of permutation classes. Additionally, in 2023 I spent the summer at the University of Maryland working on a computational geometry problem with Auguste Gezalyan, David Mount, and 3 other brilliant students.
Despite it being categorized as computer science, I often describe my research to people as math. I am generally interested in problems that are visual to some degree and easy to state. Such problems are satisfying because they are often surprisingly difficult to solve and require some creative insight.
Below is a list of my favorite puzzles I've encountered over the years. A strong background in math might help you solve them, but it's absolutely not required. In fact, the common theme is that the best solution is simple and elegant, so if you find yourself writing tedious equations, chances are you're barking up the wrong tree.
For some of these, the goal is to find some creative perspective that makes a messy problem almost trivial. For others, the goal is to show some paradoxical result. They don't really translate to advanced mathematics, but it's still valuable practice in problem solving. Most of them I was able to solve on my own, but for some I had to look up the answer. Try to see if you can solve them without cheating!
Show that for any two potatoes, you can draw the same closed loop on both of them.
There are actually infinitely many such loops. It's easier to think about how you would construct one.
Imagine the potatoes are holograms, and overlay them so their surfaces intersect. The intersection will be a closed loop or multiple closed loops.
An adversary writes down two distinct (real) numbers on a piece of paper. Then she flips a coin, but doesn't show you the outcome. If it's heads, she tells you the larger number, and if it's tails, she tells you the smaller number. Devise a strategy to correctly guess the outcome of the coin flip with greater than 50% probability.
Think I left out some details? I didn't. The numbers do not have to be bounded, and the adversary can choose them any way she pleases.
1. The adversary can read your mind and knows your strategy. This won't stop you.
2. The adversary can bring your probability of winning arbitrarily close to 50%, but never less than or equal to 50%.
3. If you get the larger number, you think it's the larger number with probability p. If you get the smaller number, you think it's the larger number with probability q. You need to find a strategy where p > q.
Choose a number from a Gaussian distribution. If it's smaller than the number the adversary gave you, guess heads. If it's larger than the number the adversary gave you, guess tails.
The distribution only has to have the following property: for any two numbers a < b the adversary could specify, the distribution assigns a nonzero probability to the interval [a,b].
100 people are boarding an airplane one by one. Each person has an assigned seat. The first person to board does not look at his ticket and sits in a uniformly random seat. Every subsequent person sits in his assigned seat if it's available and a uniformly random seat otherwise. What is the probability the last person to board sits in his own seat?
1. What seats can the last person actually end up sitting in?
2. The last person doesn't actually get to choose his seat. But any person whose seat was taken had no preference about the seat they chose among those still available.
Label the people 1 ... 100 in the order they board. Label the seats 1 ... 100 so that person i is assigned seat i.
Let i be in 2 ... 100. If seat i is taken when person i boards, then seats 2 ... i are exactly the seats taken. Writing out a brief example should convince you of this.
This implies that person 100 will always sit either in seat 1 or seat 100. But he does not get to choose. However, every previous person either sat deterministically in their own seat 2 ... 99, or they chose randomly among the seats available, which always included seats 1 and 100. So the last available seat is equally likely to be either 1 or 100, which makes the answer 50%.
100 ants are walking along a yardstick. Every ant walks at a rate of one foot per minute. They start off at random positions and facing random directions (left or right), and when two ants collide they each reverse their direction. Imagine the ants have no width (they are just points). When an ant reaches the end of the yardstick, it falls off. How much time must pass before you can guarantee every ant fell off the yardstick?
First just consider two ants. What happens when they collide? Is there an equivalent way to model this?
Imagine instead that the ants simply pass through eachother rather than colliding. This is the same problem besides the labeling of the ants, but that doesn't matter. Clearly the answer is 3 minutes, which is attained when one ant must cross the entire yardstick.
Two trains are travelling toward eachother, each at a speed of 10 miles per hour. Initially, they are 100 miles away. A bird starts at the first train and flies toward the second train at 25 miles per hour. When it reaches the second train, it turns around and flies back toward the first train at the same speed. The bird repeats this process until the trains collide. How far does the bird fly in total?
How long does it take for the trains to collide?
Clever Solution: The trains will take 5 hours to collide. In this time frame, the bird travels at a constant speed of 25 miles per hour. So in total, it travels 125 miles.
John von Neumann's Solution: Sum the infinite series.