Hangman

Hey!

Imagine a man is convicted of murder and is sentenced to death one Saturday. The judge states that the man will be hanged sometime the next week, but the date will be a surprise-- the man won't know what day he is hanged until the noon of that day.

When the prisoner returns to his cell, he is ecstatic. Think about it: it can't be on a Saturday, because it is the last day of the week that he could be hanged on and therefore not a surprise. And if it was on Friday, he could be sure it was that day because Saturday has already been ruled out and therefore makes Friday the last possible day. So on and so forth until no day can he be hanged.

However, on Thursday, he is informed that he will be hanged. This comes as a complete surprise to him, contrary to his logic.

Consider this carefully. Is it a true paradox?

~~~~~~~~~~~~

Sorry for the short post. I'll put up an answer sometime next week, along with another post. Honestly, it's been a bit hard to do the blog, mainly because I get one hour every day to use my computer-- including free time, a research project that I have to do, and the blog.

I'll get you next week!

Stay coolio,
John

NEXT WEEK: Something Different

Ramsey Theory

Consider this problem:

Let's say that there are some people in a room for which some of them know each other and others do not. How many people must there be to make sure that either 3 of them are strangers to each other, or 3 have all met each other?

Another way to consider this problem is:

There are some points in a space, each connected by line segments to all of the other points. If each segment is either blue or red, then how many points must there be to ensure that there is one full triangle (with vertices on the points) outlined by all blue or all red?

In theory, these problems are exactly the same. The points are obviously people, and the color of the lines represents whether they know each other. If one color forms a triangle, three people either know each other or are total strangers to one another. Simple, right?

Anyway, the answer is 6 people. This is called the Ramsey number for two-colored triangles, written as:
R(3,3)=6

Let's call a complete graph (where all points are connected) with n points Kn. For Ramsey notation, the number of values in the parentheses represent the number of colors; the values themselves signify the graphs that we're trying to force. So R(3,6)=18 would be two colored, either forcing a red triangle or a blue K6.

Here are the Ramsey numbers that we know for now:
3, 3 = 6
3, 3, 3 = 17
3, 4 = 9
3, 5 = 14
4, 4 = 18
3, 6 = 18
3, 7 = 23
3, 8 = 28
3, 9 = 36
4, 5 = 25
6, 7 = 298

But then there are the irregular graphs, like straight lines and bowties and things like that. Well, thank you, Stefan Burr!

Crafts Time (cont.)

Sorry, I just want to make a note on the last post I made, about the matchbox computer.

~~~~~~~~~~

Once upon a time, there was a guy named Donald Michie. When he was in WWII, he wanted to take Japanese and go fight on the Pacific front. Naturally, however, the class was full, and he did not sign up in time. However, he was not fazed in his war effort! He was recruited to help solve the enigmatic messages of the German army, and found that he was a natural in computer analysis. He began to work harder towards the study of artificial intelligence.

Within 20 years later, he invented the tic-tac-toe MENACE. MENACE was the Matchbox Educable Naughts And Crosses Engine, one of the first perfect-able robots to play the game of tic tac toe. He made the machine by diagramming all of the possible board states on 304 separate matchboxes. Although there are 19,683 possible board layouts*, Michie reduced this number to 304 by taking rotations, mirror images, and winning positions into account, thus reducing the number by over 98%.

*If you think about it, each of the 9 squares can be in one of three states: blank, X, or O. 3^9=19683.

~~~~~~~~~~~~

Stay coolio,
John

Crafts Time

IT'S FUN DAY MONDAY OMG SO EXCITED!!!!!!!

So I've been at the beach for 4 days now, and that of course means a lot of reading for those less inclined to enter the water. And so I learned something new:

~~~~~~~~~

How to Make a Hexapawn Educable Robot (HER)

Materials:

1) 24 Matchboxes or Similar Containers (Preferably blank)

2) 3-4 Bags of M&Ms

3) Paper

4) 4 Colored Sharpies (Orange, Blue, Green, Red, Brown, and/or Yellow)

5) 3 Pennies (or other coins)

6) 3 Dimes (or other coins)

Procedure:

1) Copy these diagrams onto the matchboxes:

2) On each of the diagrams, color all the arrows in each diagram differently.

3) Open the bags of M&Ms and sort them by color.

4) Eat the two colors of M&Ms whose corresponding Sharpie you do not have. For example, if you don't have a yellow or brown Sharpie, eat all the yellow and brown M&Ms.

5) Put an M&M in each box for the number and color of the arrows on it. For example, if there is a 

    red arrow on the box, put in a red M&M.

6) Draw a three-by-three grid and put the coins on opposite sides, like so:

You are now ready to face your computer in Hexapawn!

~~~~~~~~~~

How to Play Hexapawn:

Hexapawn is a one on one game that you play against HER in order to teach it how to win! To win, you must either:

1) Capture all of your opponent's pawns,

2) Get one of your pawns to the opposite side, or

3) Be the last player to be able to move.

Your pawns move the same way that they would in chess-- they can only move forward, except they must capture diagonally-- except there are no double moves and en-passants. Good luck!

~~~~~~~~~~

How to Operate your HER:

First, arrange the matchboxes as shown in the diagram above. This makes the game run smoother.

Then you can start the game. You make your move first.

Here's how you operate the robot:

1) Find the matchbox whose diagram is either the same as the current board position or a mirror image.

2) Shake the matchbox to mix the M&Ms.

3) With your eyes closed, open the matchbox and pick a random M&M.

4) Place the M&M on top of the matchbox and observe the color of the M&M.

5) Find the corresponding arrow for the color of the M&M.

6) Make the move as indicated by the arrow.

3.5*) If there are no M&Ms in the box, the robot automatically loses.

The education of the robot is based on a reward/punishment system. When the robot wins the game, the M&Ms that are on top of the boxes are placed back inside. When it loses, take away the M&M that represents the last move that the robot made; *if a box is empty, the HER loses and you take away the M&M on last move's box.

~~~~~~~~~~

How the HER Works

Imagine a huge probability tree that represents the outcomes of each game. Each splitting of branches represents the robot's decision-- and so the end of a branch is either a win or a loss for the robot. When you remove M&Ms, you are, in essence, cutting off the branches in which the robot loses. The robot has a big advantage by going second, and so it will eventually have the ability to win every game it plays.

~~~~~~~~~~~

Stay coolio,

John

NEXT WEEK: Ramsey Numbers

Hailstones (The Collatz Conjecture)

Hey guys, I'm back from camp with a TON of new ideas. I got a bunch of math books as a graduation present (which would be a really mean present if I wasn't myself), and I got some new topics to discuss.

~~~~~~~~~~

In the science of the hydrosphere, we all know that water molecules present in air all eventually return to the Earth in the form of precipitation. One of the forms thereof is hail, which forms in heavy storms when liquid rain freezes onto snow pellets and begins to form solid lumps.

Let's say that layers of the atmosphere are marked by numbers, starting with one as the ground. The goal of a hailstone is, obviously to reach one.

The process that determines the path of a hailstone is this:
1) If a hailstone reaches level n, and n is odd, then the hailstone is caught by a gust of wind and shoots up to level 3n+1.
2) If n is even, then there is no wind and the hailstone falls to n/2.
3) This process is continued upon itself until n reaches 1.
For any positive integer from which the hailstone (n) begins, does n reach 1?

This can also be stated as:

~~~~~~~~~~

FACTS:

1. The sequence always ends [...] 16, 8, 4, 2, 1.

2. The conjecture has been proved up to about 5476377146882523136.

3. The sequence always returns to one if n is a power of 2.

4. The recurrence is undecidable (it cannot be solved by an algorithm).

5. Once the hailstone reaches 16, the hailstone is set into an infinite loop around (4,2,1).

6. Most diagrams are created in reverse.

Up to 20 iterations. Ends with one in the center.

~~~~~~~~~~~~~

Hey guys! It's good to be back. From now on, I'm going to try to have one post every Monday. I have so much to talk about, but I don't want to waste all of my ideas now! We'll see what happens later, I guess.

Stay coolio,

John

NEXT WEEK: More on Game Theory