Professor Gasarch at the University of Maryland is challenging people to see if a solution exists to a Four Color problem. In his proposed problem, each site of a 17 by 17 grid is occupied by one of four colors. The challenge is to place a color on each site such that all the corners of any rectangle formed from the sites are not the same color. (See Details). He is offering a prize of $289 ($17x17) for a solution (if one even exists). What intrigues me is his lack of prize money for a proof that a solution exists. He want's something that would 'stand up in court'. Which makes me inclined to think he plans to use this for a patentable encryption algorithm. But I'm speculating.
I quickly coded up the problem to get an idea of the solution space and the difficulty of the problem. First off, brute force is out of the question. 4^289 is an incredibly large number and finding all solutions would take longer than the earths lifetime. There may be some branch cut methods to reduce the complexity, but I'm guessing it is still too large.
As a first step, I did a random search of 10,000 configurations and plotted a histogram of the number of solutions with a given number of conflicts. A conflict being the number of rectangles that have four corners of the same color. The plot is depicted below. In summary, we see that the probability of getting a solution with zero rectangles with same colored corners is nearly zero. So, solving this problem is certainly a difficult challenge. Especially with the uncertainty of the existence of a solution.
Thursday, December 3, 2009
Wednesday, November 18, 2009
An Inifinite Number of Primes
In 300 AD Euclid proved that there is an infinite number of primes. A prime number being an integer that is not divisible by any other numbers. The list of prime numbers starts like this: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 ...
A guy 1700 hundred years ago could prove that this list goes on forever. A colleague, Adam Straub, challenged me to re-derive this without any resources. Adam argued: a person in the 21st century should be able to recreate this simple proof. I was able, but it took some time while driving. I challenge any readers to prove that there is an infinite number of primes before reading the solution. It is a fun challenge that requires middle school level math.
Euclid's Proof:
If we have a list of consecutive primes, starting with 2, 3, 5, .... and so on. We can always prove there is one more prime by multiplying them all together and adding one. We know this knew number is not divisible by any of the primes in our original list. So, either the new number is prime, or it is divisible by a new prime not in our original list.
Example: 2 * 3 * 5 + 1 = 31
So, if we know there is always one more prime in a consecutive list of primes there is always more primes, on to infinity.
I tried to explain this proof as simply as possible, but you can look up Euclid's proof on many other sites or even his original book, Elements (Book IX, Proposition 20) published circa 300 AD.
A guy 1700 hundred years ago could prove that this list goes on forever. A colleague, Adam Straub, challenged me to re-derive this without any resources. Adam argued: a person in the 21st century should be able to recreate this simple proof. I was able, but it took some time while driving. I challenge any readers to prove that there is an infinite number of primes before reading the solution. It is a fun challenge that requires middle school level math.
Euclid's Proof:
If we have a list of consecutive primes, starting with 2, 3, 5, .... and so on. We can always prove there is one more prime by multiplying them all together and adding one. We know this knew number is not divisible by any of the primes in our original list. So, either the new number is prime, or it is divisible by a new prime not in our original list.
Example: 2 * 3 * 5 + 1 = 31
So, if we know there is always one more prime in a consecutive list of primes there is always more primes, on to infinity.
I tried to explain this proof as simply as possible, but you can look up Euclid's proof on many other sites or even his original book, Elements (Book IX, Proposition 20) published circa 300 AD.
Tuesday, August 18, 2009
Living Music – A Live Experience
I have an idea for a creative new form of poetic expression - a kind of real life, walking music video montage. It is nearly impossible to recreate the three dimensional sights, sounds, smells, and touches of the world around us. Even with sight arguably being the most sensational of these physical interactions, a movie falls short. It’s being able to look all directions, focus in on a subject, or squint into the sun.
I’d like to accompany this experience with music. It would be kind of like a walking tour but with music. A real living music video, where the person walks along an author’s predefined path listening to predefined music. The goal of the author would be to recreate the feelings he experienced or wants to experience during his walk.
We all have those moments. Our ears silenced to the outside world by the music playing into our heads. Observing the outside world can almost seem surreal as the music inspires self reflecting thought. This is especially true when the music matches our mood and surroundings. Although it’s hard to predict the mental state of the listener, the goal of the author should be to coerce the listener into a particular mood using sight and sound. Of course, this sounds precisely like a movie or music video, but I think by using the real world it can be much more.
In the end, like most of my ideas, I would like to see others pursue this thought more so than myself. Though I will try. The idea will go in the large scrambled queue that resides in my brain, notebook, and this blog.
I’d like to accompany this experience with music. It would be kind of like a walking tour but with music. A real living music video, where the person walks along an author’s predefined path listening to predefined music. The goal of the author would be to recreate the feelings he experienced or wants to experience during his walk.
We all have those moments. Our ears silenced to the outside world by the music playing into our heads. Observing the outside world can almost seem surreal as the music inspires self reflecting thought. This is especially true when the music matches our mood and surroundings. Although it’s hard to predict the mental state of the listener, the goal of the author should be to coerce the listener into a particular mood using sight and sound. Of course, this sounds precisely like a movie or music video, but I think by using the real world it can be much more.
In the end, like most of my ideas, I would like to see others pursue this thought more so than myself. Though I will try. The idea will go in the large scrambled queue that resides in my brain, notebook, and this blog.
Saturday, April 18, 2009
Visiting Carl Sagan
Sagan was one of many influential people who called Ithaca home. Reminders of his presence permeates Ithaca and Cornell's campus, which include his house on the Fall Creek Gorge and his final resting place at the Lakeview Cemetery. I recently paid tribute with two friends.
Locating Carl Sagan's grave is not too difficult, but it did take us half an hour. He is buried in Ithaca, New York at the Lakeview Cemetary. The cemetary entrance is gated at the top of a hill overlooking downtown Ithaca. Only a couple hundred feet after the gate, his gravestone is just off the road to the right. We found a multitude of placed stones which had been left by previous visitors. We arranged the colored stones in a line representing the planetary system ranging from the sun to pluto as shown below. I know, Pluto is debatibly a planet, but in Sagan's day it certainly was.
Wednesday, April 8, 2009
Million Monkeys Project
A finite but extremely large number of monkey's with typewriters act as my muse during my creation of large amounts of creative works. Copyrights last for a cumbersome duration and so it is a goal of this project to place everything I make in the public domain.
Here you will find an exhaustive list of creative works that are in a fixed and tangible form. For example, my first project is an enormous list of two word poems which I have independently created. In fact, you would be hard pressed to find a two word poem which I have not written (unless you include proper nouns).
For this day on, each of my creative works will forever be free (as in beer and speech) for anyone to copy. By placing my works in the public domain, I encourage anyone to use each work in anyway they wish without any attribution. That being said, I do retain the copyrights to the compilation of works, so do not redistribute my lists.
After writing poetry till my hands bled, I decided I should look to see what has already been written. Having only assumed that two word poetry might exist, it turns out I was correct. Below is some of the two word poetry others have written. Almost all of them can be found in the poetry lists I wrote independently wrote.
Muhammad Ali at Harvard College recited a now famous poem:
Me, we.
A great video behind this poem explains its origins. I also independently wrote this famous poem without any prior knowledge of its existence. It can be found in both the One Million List and One Billion Plus List.Tuesday, February 24, 2009
Clark Hall Radio
I successfully turned my advanced physics lab into a radio station. Cornell's only on-campus radio station broadcasted Modest Mouse at 103.9 FM for over two hours. The range was at least a half mile and the station was running at a fraction of its full capabilities. So, let be known that Clark Hall on Cornell's campus has a hidden radio station on the third floor, disguising its self as Lab station C-9.
[[Here is my lab report]]
Thursday, February 19, 2009
Nice Captcha Google
Thursday, February 5, 2009
Etymology: Manilla Envelope
What the hell is a manilla envelope? Sure, I know what it is, but why is it Manila? As a young and naive child I had the misconception that it was called a Vanilla Envelope, aptly named because of its vanilla colored appearance. However M is 8 letters away from V in the alphabet [See memorizing the alphabet], completely changing the adjective's meaning.
Well, its taken me many years to consult an answer box on this issue, but now its done. It's derived from the material used to make it: Manila Hemp. Manila hemp, also known as manilla, is a type of fiber obtained from the leaves of the abacá (Musa textilis), a relative of the banana. The name, 'Manila', refers to the capital of the Philippines, one of the main producers of abacá.
Well, its taken me many years to consult an answer box on this issue, but now its done. It's derived from the material used to make it: Manila Hemp. Manila hemp, also known as manilla, is a type of fiber obtained from the leaves of the abacá (Musa textilis), a relative of the banana. The name, 'Manila', refers to the capital of the Philippines, one of the main producers of abacá.
Thursday, January 29, 2009
The XKCD Effect
On Jan 21 XCKD, a very popular web comic, posted a comic referencing the Fujitsu Q2010 laptop:
Prior to this, due to a lack of search volume, Google Trends had no global search trend data. However, the day XKCD published a webcomic referencing the Q2010 there was a global traffic spike. Not only does this demonstrate the high volume of XKCD traffic, but it also tells us where the top readers are.
On Jan 23 XKCD posted a comic referencing skynet:
The impact of XKCD on skynet also had a noticeable impact on global search trends! The traffic spike on Jan 23 can be clearly seen in the United States search trends:
The XKCD effect is big and all comics are still released under the Creative Commons License. I wonder how much an XKCD shoutout costs? From the trends below, I suspect things might change.
Prior to this, due to a lack of search volume, Google Trends had no global search trend data. However, the day XKCD published a webcomic referencing the Q2010 there was a global traffic spike. Not only does this demonstrate the high volume of XKCD traffic, but it also tells us where the top readers are.
On Jan 23 XKCD posted a comic referencing skynet:
The impact of XKCD on skynet also had a noticeable impact on global search trends! The traffic spike on Jan 23 can be clearly seen in the United States search trends:
The XKCD effect is big and all comics are still released under the Creative Commons License. I wonder how much an XKCD shoutout costs? From the trends below, I suspect things might change.
Sunday, January 4, 2009
A New Equals Sign - Dot Equals
I think that mathematics could use a new commonly used character to describe certain types of equalities. Typically, the equals sign, = , is used to denote the equality of two quantities. A simple example of this would be
A lot of times, algebraic manipulations of expressions are made and the equals sign is also used. An example of this would be:
In this latter example, I think a unique equality character should be used to distinguish equalities made solely from mathematical manipulation.
So I propose the following a dot equals to denote equalities made solely from mathematical manipulation or evaluation. A simple example being:
Or
Although this symbol is available in unicode and Latex, if the character does not exist an equal with a period ( .= ) could be used. I must note that I have seen this to denote "in the limit of". I do not think this is a common use, and as an alternative a dot underneath the equals sign could be used or anything else similar to an equals sign. This symbol and many others exist in Unicode or Latex. For inspiration, check out all of the unicode symbols here.
A lot of times, algebraic manipulations of expressions are made and the equals sign is also used. An example of this would be:
In this latter example, I think a unique equality character should be used to distinguish equalities made solely from mathematical manipulation.
So I propose the following a dot equals to denote equalities made solely from mathematical manipulation or evaluation. A simple example being:
Or
Although this symbol is available in unicode and Latex, if the character does not exist an equal with a period ( .= ) could be used. I must note that I have seen this to denote "in the limit of". I do not think this is a common use, and as an alternative a dot underneath the equals sign could be used or anything else similar to an equals sign. This symbol and many others exist in Unicode or Latex. For inspiration, check out all of the unicode symbols here.
Subscribe to:
Posts (Atom)