In this article it explains to us the real ways that the Four Color Theorem came to be. In 1976, Kenneth Appel and Wolfgang Haken finally succeeded in approving the color theorem but were unable to prove to others how the Four Color Theorem works without suggesting to draw an infinite number of maps to prove it. The truth of the matter was that proving the Four Color Theorem would only be possible with the help of computers. They used the reductio ad absurdum (reduction to absurdity) method. This states that “If we want to prove that something is true, we instead assume that it is false and show that the rest of math goes bad. That is, by assuming falsity, we encounter contradictions to already known truths.” So, Appel and Haken used this idea along with a computer program to work on any map, assuming that there might’ve been a map out there that needed more than four colors. After the computer proved that no map needed more than four colors to complete the four color theorem became the first major mathematical theorem to be proved using a computer. Who knows if this could’ve ever been truly proven without the help of technology?
In July 1879, Alfred Bray Kempe found the proof for the four color conjecture, he submitted the theorem to the American Journal of Mathematics. Soon after, it was published at the end of that year.
In Kempe’s method, he used an argument known as Kempe Chains. If every region on a map is colored but one, then that point left over becomes X. In the end, if X is surrounded by all four colors, then there is a color left for X to become.
A year later, Percy John Heawood was able to prove Kempe wrong by publishing a paper on map coloring theorems. This proved that every map would be five-colored.
Thinking of all the history involved in Coloring theorems is crazy, years ago they started looking into this and everyone rejected peoples solutions, and then came a computer.
While it’s obvious that math is in all video games, between pixel designs and character stats, it’s also used when finding the best way to grab all of those pesky yet useful hidden items around a game map. While reading this link: https://arxiv.org/pdf/1608.06175.pdf, the Traveling Salesman Problem algorithm was found to be the best way to help players attain items that are scattered around games such as Pokemon, Legend of Zelda, and the game that was used in the experiment done in the article, Far Cry 3. Through using the algorithm, the best routes can be found, either based on time or distance, while also taking into account cut-scenes, obstacles such as drop-offs and climbing, and more video-game attributes that may get int the way of finding the fastest paths.
I found this to be really interesting, even if I’m not one for going on item hauls when I play video games. There are many people called “speed players” who are dedicated to cutting every corner to find the fastest ways to play their favorite games. Knowing just how rapid-fire the play, going into the minutes-range rather than finishing games in hours, they most likely use this algorithm to perfect their strategy. For anyone who likes to play on their XBox or Nintendo DS, do your math!
Two examples of interesting TSP Applications I came across:
The people in charge of creating routes for school buses and bus routes in general use the Traveling Salesman problem to drop off their passengers in the most optimal way possible while bringing the bus back to the original location.
Some Airlines like Southwest use TSP to schedule flight paths so that their crews fly to several different locations and come back to their home airport at the end of their shifts. Other airlines have their planes just fly back and forth between airports which results in a much simpler solution to bring the crew back to their home airport, but also is a less optimized use of resources.
According to this article, bees can solve the traveling salesman problem. THAT’S RIGHT! NOW THE BEES ARE GOING TO RULE THE WORLD! HIDE YO KIDS, HIDE YO WIFE CAUSE THE BEES ARE COMING TO STING YOU!!!
On a more serious note: this is actually interesting. Studies show that the flight of a bee becomes more efficient over time, and that they are continually optimizing their routes over time, becoming better navigators with each flight, changing route sequences to improve speed, and becoming adapt to their favorite flights.
Think about how long it took for us to figure out how long it would take for the current fastest supercomputer to brute force-figure out the shortest possible route. Now that was for 100 different locations. Now think about how many flowers there are, and how often bees travel to them. No wonder researchers also say that in the future when your GPS tells you to go left, you may have a bee to thank for that information.
While doing a little research on the Traveling Salesman Problem, I found a short article in a journal about evolutionary computation. In this specific issue, the author discussed how ants are capable of finding the shortest path from a food source to their nest.
The article explains how, at one point, an ant will have to choose between going right or left. They are ants, so obviously they choose randomly. However, this means that about half of the ants will choose correctly. If, for example, one path is on a downward slope and the other on an upward slope, it is probable that more ants will choose to go down.
Keep in mind, as each ant walks towards its’ food source, they are releasing pheromones on the ground. This leaves a trail for the other ants to follow, which is much like the line segments connecting the vertices in a traditional Traveling Salesman Problem. As each ant travels towards the food source, one of them will find the shortest path, given the number of ants per path.
With programs like Concorde TSP Solver we have ways to make the Traveling Salesman Problem irrelevant to our everyday lives. Maps like Google maps can already handle multiple locations and trying to give you the best route. Not to mention you can use any number of alternative map services.
In the larger context however, TSP still lives on as a big problem for mathematicians, to the extent to have considered what it would mean to truly solve the problem in the 2012 movje Traveling Salesman.
Meanwhile, although the problem has been made much easier, truckers delivery drivers still have to deal with the problem from day to day. And given how much it can drive a person crazy we should be thankful we have modern technology to help guide us through the easier version.
That said, if you want to truly kill the TSP then answer P vs. NP and collect your million dollars, here.
I began my google search with the simple “traveling salesman problem”, and after reading a few articles, I found this one to be rather interesting.
In this article, the author Joshi describes solving the TSP by using the top-down approach. This is the same approach we used in class, using the largest parts of the graph to find a solution.
Then, the author mentions trying the same problem, but instead with a bottom-up approach. Joshi calls this the “bottom-up dynamic programming approach”, which begins with the smallest possible subproblems and their solutions, then progresses upward to solve the more complicated subproblem. In the end, the bottom-up approach brought Joshi to an answer sooner than the top-down method.
Alright, we are going to talk about the Knight’s Tour, “getting the Knight to visit all 64 squares only once.” In this article I found written by Patrick JMT for the US Chess Federation, he mentions that Euler has found a way to create his own open and closed Knight’s Tour. To clarify for those who don’t know much about chess, such as myself, a closed tour is when the Knight is able to end on the space it started and continue to follow the same sequences to recreate a new tour again and again. For an open tour, it’s when the Knight has visited all spaces but wasn’t able to end where it started. Relating this to graph theory, this would be paths and circuits.
On the topic of graph theory, Patrick mentions how the squares can be vertices and the moves made would be edges, creating a complex map of how the Knight would move. That type of graph was shown to us in 3D printed form in class.
Also in the article there is a graph called a Bipartite graph that would represent 32 black/white tiles and since the “Knight always alternates the colors of the squares it visits: if the Knight stands on a black square, it can only travel to a white square and vice versa.” This makes the Bipartite graph connect to spaces of which the Knight can move from one white square to multiple black squares, in other words plots, where you can move from one space to another.
After discussing it in class, I decided to look more into Disney’s touring plan. This is one quote i liked about the challenges “The 21 attractions in the Magic Kingdom One-day Touring Plan for Adults have a staggering 51,090,942,171,709,440,000 possible touring plans. That’s over 51 billion billion combinations, or roughly six times as many as the estimated number of grains of sand on Earth.” This just goes to show how challenging it is to have a successful touring plan.