Gauss' Problem

            This week's post will be covering a problem solved by Gauss, and how it can be applied to another problem. To start things off I want you to add all the digits, of all the numbers from one to a million. Notice how it’s not the numbers, but the digits of those numbers that are being added up. So its not twenty-five plus twenty-six, it is two plus five plus two plus six. Think about this, and I will get to it at the end of the post. First the history of Gauss will be covered in their post. Then his similar problem will be solved. Finally I will connect the two and give the solution to the first problem I presented.

            Johannes Carl Friedrich Gauss was born in southern Germany in the late 1700's. Though he is not as famous as Newton, Gauss is still considered to be a great contributor to world of mathematics. His works included developments in number theory, such as advances in algebra, and statistics. He we also know for some of with work in the world of physics, as many mathematicians where in his time. He died in the mid eighteen hundreds.

         While in his early years Gauss was known to be a child prodigy. He seemed to have a natural ability with mathematics, and often times astonished people. One day while still in his youth Gauss went to school as he normally would. However, the professor was especially grumpy that day. Many variations of the story say he was old, and cranky, and would beat kids with his cane, making him seem more menacing then he probably was. The grumpy professor walked into the one room classroom, and since he did not feel like putting up with the children, he told them to add all the numbers from one to a hundred. At this time there was not pens and paper, but instead the children had blackboard slates. Now seconds after the professor had challenged the boys, Gauss runs up and puts his slate face down on the teacher’s desk. Thus submitting his answer. At this point in time Gauss is not the oldest boy in the room, and many of the other older boys look down on him. They were said to be thinking, poor little gauss, he has gone with a guess. Well time goes on, and all the other boys start working out the problem, using addition, multiplication, subtractions, and division, anything to try to get done first. Once the boys finished the problem they did like Gauss had previously done, putting their slate face down on the teachers desk, stacking them up. Once the time was up, the professor walked up to the desk and flipped all of the slates over. Now all the slates were in order from first to last, with the answers facing upward. Sitting on top of the pile was Gauss' answer. Gauss' answer was the correct answer, which is 5050. 

         So how did Gauss do it? Gauss, then explained, that the problem needs to be looked at in a different way. The most brute force way would be to add one plus two plus three, all the way to one hundred. Instead of doing it like that Gauss looked at in a different way. If all the number one through hundred are laid out one a number line, then Gauss' method can be seen. If you take one and add it to one hundred the answer is one hundred and one. The answer is the same if you add two and ninety nine. The same would apply to all the pair of numbers that can be created, all the way down to fifty and fifty-one. All Gauss had to do was take one hundred and one, and multiple by the number of pairs. In this case that would be fifty, so the answer would be fifty times one hundred and one. Fifty times one hundred and one is 5050.

          Going back to the problem at the start of post. Using the same process, start by writing out all the numbers from one to a million. Now notice that if you add to one to 999,998 it equals 999,999. This process can be done again and again. This process is the same pairing process gauss used. So then i would take the sum of all the digits of 999,999 and multiple that by the number of pairs. If zero is included that would make 500,000 pars. So 54 times a half a million would be twenty seven million. Not forgetting the one in one million would make the solution to the original problem 27,000,001.

Sources http://planetmath.org/gausscarlfriedrich

                  https://www.youtube.com/watch?v=Dd81F6-Ar_0

The Eight Queen Problem

          In this week's installment of mathematical insight, the topic will focus on the eight-queen problem. The post will start off with a small history, and backstory to the problem. Followed with the problem itself paired with some information on the scale of the numbers used in the problem. 

          The problem was originally published by Max Bezzel in the mid eighteen hundreds. Bezzel was a both a mathematician, and a chess enthusiast. It took two years for solutions to appear. Franz Nauk released them. Nauk then went to continue the problem into a more generalized state of understanding. The problem was modified from having eight queens to having "N" number of queens. After changing the number of queens Nauk modified the dimensions of the board. Instead of the traditional eight by eight board, it became "N" by "N" boards. "N" is not only the length, and width, but also the number of queens on the board. Mathematicians such as Gauss and Gunther have since contributed to the problem. 

         Looking primarily at the standard value of eight for "N", this meaning the board is a standard eight by eight chessboard, and there are eight queens on the board. The problem asks, if possible can all "N" number of queens be on the board and not be threatened by another queen? Color of the queen does not matter in this case, and if it can be done, how many possible ways can it be done? A queen in chess is considered to be the single most powerful piece, as it is the most versatile piece to move around the board. It can move both horizontally, vertically, and across diagonals. This makes positioning eight of them without threatening another difficult on a confined space. There are solutions to the standard eight by eight board. Starting with the total possible ways that eight queens can be positioned on a eight by eight board is the first part. There are sixty-four tiles on a standard chessboard. That means there are sixty-four factorial possible tile positions. If eight of the positions are taken up with queens that leaves fifty-six factorial tile positions. Since the queens are interchangeable among their given positions eight factorial also comes into play. So to find the number of ways that eight queens can be positioned on a chessboard, the total, sixty-four factorial, would be divided by 56 factorial multiplied by eight factorial. A factorial refers to that number multiplied by every previous whole number before that number. For example six factorial would be six, times five, times four, times three, times two, times one. A factorial has the nice property of showing how many ways you can arrange a number of times. For example if you wanted to know how many ways to arrange three items, the answer would be three factorial, or six. That makes numbers such as sixty-four factorial an immensely large number. Same with respect to fifty-six factorial. The net calculation on the number of ways to arrange the eight queens is roughly around four billion. This includes all permutations, but without the restriction of non-intersection between queens. Factoring that in reduces the number down to 92, continuing the sifting of possible outcomes, by removing redundancies due to reflections and rotations, the number goes down to twelve. There are twelve possible solutions to the eight-queen problem.

          To put factorials into scale of how big these numbers are, fifty-two factorial is less then the number of possible tiles, sixty-four factorial, and the number on non queen tiles fifty six factorial. Fifty-two factorial is the number of possible ways a deck of cards can be arranged. This is chosen because there is rather nice statistic about fifty-two factorial, and it is smaller then some of the numbers used in this problem. To understand fifty-two factorial, first stand on the equator. Start playing solitaire with a deck of cards, assume every new game is a new deck, and you win every game. Every billion years take a step forward, which should allow for a couple trillion games every step. Every time you walk around the earth remove a drop from the Pacific Ocean. Once the ocean is empty start stacking pieces of paper on the bottom. Once you have reached the sun, roughly one hundred million miles away. Notice not all decks have been played yet, so remove the papers one at a time, and put the water back in the ocean drop by drop, and go to and from the sun a thousand more times. Now about a third of 52 factorial decks have been played. That is how big fifty-two factorial is.

Sources http://www.datagenetics.com/blog/august42012/

                https://www.youtube.com/watch?v=jPcBU0Z2Hj8

The Josephus Problem

This week’s mathematical installment of intellectual nourishment will be on the Josephus Problem. The Josephus Problem is not a rigorous problem, nor is it hard to solve, but it is a nice easy problem. This is to act as a break from the advanced problems that have been posted recently. Due to the format of the problem, and how it is set up, first the backstory of the problem will be covered, followed with the proving the problem, and finally a nice trick with binary.

The problem arises from a historical story. The scenario is there are Jewish soldiers that have been surrounded by the oncoming Roman army. The Jewish soldiers did not fancy capture, and would prefer death. A plan was devised that the Jewish solider would gather in a circle, and one solider, in what would referred to as position one in the circle would take his sword and kill the solider next to him, and the next living solider would kill the next living solider new to him. This process would continue until only one was remaining, and he was supposed to commit suicide. Josephus however was not a fan of dying, and would much prefer living. So the problem for Josephus is where does he stand in the circle to be the last one standing. In his case there were 41 soldiers in the circle.

To best illustrate the proof, lets start with a smaller circle. To best imagine this, the soldiers are standing in a circle the top of the circle is position one, and then it goes around just like a clock would.  In order to save time I have compiled the winning seat from a couple of circles. So if there is one individual, position one wins, with two people position one wins, with three people, number three wins, with four is one, five is three, six is five, seven is seven. From this small bit of information something can be derived already. The winning seat is always an odd number. This can be seen, because on the first pass through of killing all the even numbers go first. At this point is might seem like the pattern is 1,13,1357,13579,13579... but it is not. According to that pattern if there were thirteen soldiers, position one would win, but that is not the case, in fact position 11 would win. If you do not believe me try it for yourself. So if the pattern is not to go up by two each time, and then cycle back to one, what is? If you notice all the powers of two go to one. That can be easily proven if we know that all the evens go out in the first round. So if there is a power of two number of soldiers, it will get cut in half the first round, and position one will start the second round, and then will half, and half until it cannot be halved again. So the pattern would go 1,13,1357,13579(11)(13), 1...but how does that help us? We know that if there is a power of two number of solider at the beginning of a round then the first position wins. So if the biggest power of two is taken away from a number, the remainer would tell how many position to offset from one to get the winning position. For example, if there where seventeen soldiers that would be the same as sixteen plus one soldiers. So after one kill there is sixteen solider remaining and whoever's turn it is to kill would win the round. So whose turn is it? In the case of seventeen it would position three's turn. Going back to our data set, if there where five soldiers, or four plus one soldiers then three would also win. So if one is the remainder of one from our power of two subtraction, then three wins. So three times the remainder of the power of two, plus one would be the winning seat. Just to be sure lets try it if there were seven soldiers, since we already know the answer, it will allow us to confirm our results. The highest power of two that can be subtracted from seven is four, which would leave us with three. Three times two, plus one equals seven. This matches our results, and confirms it. Going back to the original problem, there were 41 soldiers, 32 is the greatest power of two that can be subtracted from 41 with remainder. 41 minus 31 is nine, nines times two is 18 add now is 19. Josephus should get in position nineteen of the circle.

Something that I will not prove, but might be interesting, if you take the number of soldiers and write in binary, to find the winning seat all you have to do is shift the leading number to the end, and reevaluate the binary.

Sources https://www.youtube.com/watch?v=uCsD3ZGzMgE
              http://www.geeksforgeeks.org/josephus-problem-set-1-a-on-solution/

The Four Color Problem

This week’s installment of mathematical problems is going to be about the four color problem. This problem has to with the involvement of filling in maps with different colors. The problem started with physical maps of countries and boundaries, and then shifted into a more abstract mathematical field. The problem will be covered first, followed up with a five color solution proof, and finally some history.

The four color problem is, if there is a map can all the countries or states can be filled in with four colors, in that no two same colors come into contact with each other. This was purposed in the mid 1800's and since then people have been filling in actual geographical maps with four colors. No matter the complexity of the geographical map, it will not require more than four colors to fill in all the boundaries. The map of the world can be done, the map of the Untied States can be done, and so can the map of the United Kingdom counties. All geographical maps fit these criteria. This is where the realm of mathematics steps in. Instead of using maps that already exist, can a map be created that can disprove this conjecture? This is because for the average person, it is a lot simpler to come up with a counter argument rather than proving it. So people started creating maps, and filling them in. There arose a problem of repeating maps being checked. Though two maps look different if the share the same type of relation between borders, then they are in essence the same map. So instead of filling areas on maps countries were represented with colored dots. If two countries touched reached other, they were connected with a line. This allowed for redundancy to be removed, and allowed for deeper analysis. This deeper analysis comes from the fact that the problem has been shifted from a coloring book problem, to a networking problem. In the 1970's this problem took off with the newfound interest in computer science, that arose in the time period. There is some rather useful insight about networking that comes in handy in solving the problem. If there is a country, call it country x, country x can be connected up to five other countries. Meaning in a given map every country can only connect with five other countries and still fit the parameters of a map. That is a very useful bit of information to have, because it allows the problem to simplified, and narrowed down. This will be apparent in the proof of at least five colors can be used.

In the last part it was mentioned that a country must have a network with anywhere from one to five connections in it. That part has its own proof, which was not covered. Going off of that information to prove five colors, start with seven colors, and work down to five. If there is a map with seven colors, assuming it is the smallest map with seven colors, there has to be one of those country x's that follows that networking rule. If that country is removed, or pulled from the map, then there is a smaller map. The smaller map would only require six colors then, and if the country x is put back into place, now there is an extra color that country x can now take, reducing the number of colors needed. This process can be done down to five, though five requires a tad more information and proofing, but can be done using the same logic.

In the mid 1800's a map creator was coloring in the counties of Great Britain. He tried to optimize his map by filling it in with as few colors as possible, without the same color touching. He worked at it, and did it with four colors. He assumed that four colors might be enough to fill any map then. He purposed the idea to his brother, who in turn passed the idea onto a mathematician by the name of Augustus De Morgan. Augustus is a famous mathematician, who is responsible for putting the problem together, and getting it some attention. The problem remained unsolved for one hundred and twenty five years after its proposal. Kenneth Appel and Wolfgang Aachen did not solve it until the 1970’s. There proof was controversial because it was the first mathematical proof to be done by the use of computer power. Which at the time was a not considered a guaranteed source.

Sources https://www.youtube.com/watch?v=NgbK43jB4rQ

                  http://www-groups.dcs.st-and.ac.uk/~history/Biographies/De_Morgan.html

                  https://www.youtube.com/watch?v=laMkuPrad3s&feature=youtu.be