Math Fact #2: Cleveland to Cincinnati

If you travel from Cleveland to Cincinnati on one day, and from Cincinnati to Cleveland on another day, taking the same road, there must be a time at which you were in the same spot both days.

In other words, if you drive from Cleveland to Cincinnati on e.g. Monday and back on Tuesday, there will always be a time, say 4:14, where you’re in the same spot — at 4:14 Monday and at 4:14 Tuesday, your car is in the same exact place on the highway.

It’s not terribly hard to imagine why this is intuitively. Let’s superimpose the two days. Say you have a twin who drives from Cincinnati to Cleveland taking the same route while you drive from Cleveland to Cincinnati. Clearly, you’re going to pass each other at some point.

But let’s look at this mathematically — how can we logically prove that the two of you pass? Well, for that we need to make two assumptions. The first is our former assumption that you have to drive along the same route — in other words, your position along the journey can be expressed completely in terms of a function giving how far (fractionally) you are along the route at a given time, in one dimension. The second assumption is that you move continuously, i.e. you can’t teleport or drive infinitely past either end. We can now express your travel there and back as two functions f1(t) and f2(t), which map the time as a fraction of the day to your position as a fraction of the path. For instance, if you’re 1/3 of the way to Cincinnati at 12:00 noon on Monday, this corresponds to f1(1/2) = 1/3. (Note that we measure the path from Cleveland to Cincinnati on both days; in other words, f1(t) goes from 0 to 1, while f2(t) goes from 1 to 0.)

What we can now do is take a look at the difference between these two functions, as a new function g(t) = f1(t) - f2(t). We can now say the following about g(t):

  • g(0) = -1. At the start of the day, f1(0) = 0 for Cleveland, and f2(0) = 1 for Cincinnati.
  • g(1) = 1. At the end of the day, f1(1) = 1 for Cincinnati, and f2(1) = 0 for Cleveland.
  • g is a continuous function from real numbers to real numbers; this is very important! This is intuitively the “no teleportation” assumption; more formally, it means that at any time t on the journey, if we pick any distance d, there’s an interval of time around t in which you’re within distance d of where you are at time t.

What we can now do is apply the intermediate value theorem. This states that for such a function g, we can pick any value x from g(0) to g(1), and there’s a t between 0 and 1 where g(t) = x. In our case, we pick x = 0, which is between g(0) = -1 and g(1) = 1. Then at some time t we have g(t) = 0; in other words, at some time of day, the distance between your position on day 1 and on day 2 is 0, i.e. you’re in the same place.

The intermediate value theorem only works because the real numbers are a complete set. This means that if we have an infinite sequence of real numbers that get closer and closer to each other, they also get closer to some real number (which may not be in the sequence). This isn’t true of many structures, such as the rational numbers; for instance, the sequence 3, 3.1, 3.14, 3.141, 3.1415, 3.14159, … contains only rational numbers (because all of the decimal expansions terminate) that clearly get closer to each other as you go, but they don’t approach any rational number (they approach π, which is irrational). Similarly, we could start our sequence with 1 and define the pattern that every term of the sequence is the previous term over 2 plus 1 over the previous term; then the sequence contains rational numbers approaching the square root of 2, which is again irrational. The fact that the real numbers are a complete set is very important to their structure (more on that another time).

This proof is what’s known as an existence proof or non-constructive proof; it tells us that something exists, but it gives little to no help in finding it. A lot of these proofs involve the Intermediate Value Theorem, and some of them have pretty interesting applications, particularly in areas such as topology. For instance, one of the most interestingly named results in mathematics is the hairy ball theorem: if a sphere is covered with hair, we can’t comb the hair flat without creating a cowlick. This may seem like a frivolous concept, but it means for instance that there is always a spot on the planet where any wind that exists is pointing directly up or down (or there is no wind at all). This wouldn’t necessarily be true on a donut-shaped planet, by the way, meaning that if Earth were shaped like a donut, there could be a cycle of constant wind.

Math Fact #1: Facebook Friends

This is the first of a series of posts I’m going to make, hopefully every Saturday. In each one, I’m going to give a mathematical fact and proof, attempting to be accessible and interesting to the general population and give an idea of what math is really about (hint: there’s not a whole lot of trigonometry once you’re through high school). So, let’s get started!

Pick any six people on Facebook. However you pick, there will be three people of the six who either are all friends with each other or aren’t friends with each other.

To see why this is the case, let’s assume we’ve picked six people. Take a look at the friends list of one of them — we’ll call him Jim. Of the other five people, Jim could be friends with all of them, or none of them. However, note that the number of friends and non-friends has to add to 5 (clearly), and if two whole numbers add to 5, one of them has to be 3 or higher. (Try a few pairs of numbers if you’re not sure why this is.) So we can always find three of the other five that Jim is either friends with or not friends with.

To simplify things, we’re only going to look in depth at one of these cases. However, we need to clarify why we can do this. Picture a mirror universe where all friendships are inverted — two people who are friends in our universe aren’t in the other universe, and vice versa. So if Jim isn’t friends with three of the others, Mirror-Jim — Mij, if you will — is friends with those three. Then we can show that Mij and his friends form a triangle of friends or non-friends, and this will correspond to a triangle of non-friends or friends in Jim’s world.

So, either Jim or Mij has three friends of the six. We’ll call these three people Anne, Bob, and Carly. If any two of those three are also friends with each other, we have a triangle of friends. But if none of the three are friends, this makes a triangle of non-friends. So we form a triangle in either case.

As a demonstration that 6 is indeed the minimum, consider a ring of five people, where each is friends with the two adjacent people. The non-friends then form another cycle, this one shaped like a five-pointed star. There is no group of three friends or non-friends.

The result does indeed generalize to higher numbers: for any number of mutual friends or non-friends we want, we’ll eventually find this pattern by considering more and more people. The bounds get very large: nobody knows exactly how many people we need to consider for e.g. ten of them to all be friends or non-friends, but it could be over 20,000.

This result is known as Ramsey’s theorem, and it’s an important theorem in the field known as Ramsey theory. The main idea of Ramsey theory is that a complex enough structure is bound to have patterns somewhere in it, no matter how hard we try to prevent this from happening. Ramsey theory has a variety of applications in geometry and computer science.

Website move

As you may be able to tell from the fact that it no longer loads, my website is in the process of being moved to www.whirligig231.tk. Once the domain registration gets through the pipes, I’ll see you there!

Web ads

I apologize to anyone who went to my website recently and found a bunch of annoying ads. I figured it was the product of either a) the hosting service pulling crap on me and saying “HAHAHA, THIS IS WHY IT’S FREE!” or b) h4x0rs. Turns out it’s the hosting service, but they only do it if you haven’t managed your website in a while. Shows you how much time I dedicate to it. In any case, it should be fine now, so take a look!

Dyadic Intervals Theorem

Proof I came up with some weeks ago. If a ruler covers the entire line and has marks at the dyadic rationals (multiples of a power of 2) that are larger if the power of 2 involved is higher, then any open interval has exactly one mark bigger than all of the others.

My twitch.tv channel

So for those of you who didn’t see the big link above this text, I got a channel on twitch.tv! I’ll mostly be using it to stream The Binding of Isaac for now, but I’ll most likely be playing some other games on there as well, so check it out!

Sequential Discontinuity

I just proved a couple of interesting theorems relating to a concept I’ve defined and call the sequential discontinuity. Anyone who has studied calculus knows of three or four types of discontinuity. The first is the removable discontinuity, where a function is undefined or “wrongly” defined at a single point. The second is the jump discontinuity, where a function approaches a different value from either side of the discontinuity. The third type is the essential discontinuity, which is basically anything else, so teachers tend to further subdivide it into vertical asymptotes (which make up the vast majority of essential discontinuities) and oscillating discontinuities such as the discontinuity of sin(1/x) at x = 0 (even if the function is altered such that f(0) = 0). However, not all essential discontinuities fall into this category.

Consider the following function: f(x) = 0 for all x such that log(x) is not an integer and is undefined otherwise. (This is the base 10 logarithm). This function has obvious removable discontinuities at x = 10^k for integer k, but it also has a discontinuity at x = 0. This is because the formal definition of the limit requires an open interval of x-values around 0 where all f(x) except possibly f(0) are undefined, and no such interval exists. In layman’s terms, you can’t put a mark anywhere past 0 on the number line without a power of ten between 0 and the mark, no matter how close it is to 0. This discontinuity is not an asymptote and does not involve oscillation (the value of f(x) never changes where it exists).

A sequential discontinuity exists in two cases: at the limit of a convergent sequence of x-values where the function is undefined, and at the limit of a convergent sequence of x-values where the sequence of the corresponding function values is unbounded. Note that the second case especially can be a different kind of discontinuity as well; for instance, the discontinuity at x = 0 for f(x) = 1/x is sequential, as we can define the sequence x = 1, 1/2, 1/3, …, which converges to 0 and has function values that increase without bound. It is also a vertical asymptote, a simpler case.

The interesting thing about sequential discontinuities is that sometimes they are “removable” in the sense that the function containing them could be made continuous by changing countably many values (strangely not including the value at the discontinuity). However, they have undefined limits and as such are not removable.

I have here a link to a PDF proof and more formal definition. One small lemma is required for the second case but is not proven, so I will prove it here. An unbounded sequence has for every real number k and natural number M a value m > M such that a_m > k. To prove this, choose i such that a_i > k. If a_i > M, then m = i. If a_i <= M, then let K be the maximum of a_1, a_2, …, a_M. We are guaranteed K >= a_i > k. Then there must be a j such that a_j > K, and j must be greater than M (otherwise K would not be the maximum), so let m = j and a_m > k.


Whirligig Studios website is now LIVE!

So I decided yesterday to get my own website! I’ll post the finished versions of all of my games there, as well as more info about myself, etc. Check it out!

Stoichios 1.0 Out!

Yes, another game release within the span of a few weeks. As it turns out, this is a game I started in 2011. It was up to release candidate 3, but then I lost access to Windows computers in general. No worries; I’ve been able to work out the last few bugs and get the game out.

The game is a card game based on the classical/Greek elements (earth, air, fire, and water) and otherwise plays similarly to Mau Mau or Uno. Single-player and multiplayer modes are included (both local and online). There is also AI. Overall, it’s a pretty fun game, and it has what I consider some of my best music in it as well.

The game is a standalone .exe in a .zip archive; make sure to unzip it first in order to get the DLL files out. The soundtrack .mp3s are included if you want it in iTunes. Let me know if anything goes wrong.

Download: https://www.dropbox.com/s/5m3u90n7e38lu8k/Stoichios_100.zip

Resonance 1.0 Out!

What you see above is both the logo of my newest game, called Resonance, and every possible screenshot from within the game. If it doesn’t look like it’s loaded yet, it probably has. The game takes place in complete darkness.

Resonance is a game about solving puzzles without the luxury of sight. The game takes place in a maze on a standard tile grid (tiles are around 4’ wide in my mind). Instead of being able to see the maze around you, you can hear what’s in front of you, represented as pitches relative to a base of 440 Hz. Distance corresponds to the pitch and volume of each sound, and object type corresponds to the timbre.

The game has 50 levels ranging from pretty difficult to infuriatingly difficult. Headphones and graph paper are both recommended.

In theory, a blind person could play this game without being hindered (as long as he or she could find the control keys). A deaf person, on the other hand, would know absolutely nothing about the state of the game.

Download links: