The Amazing Mathemagician

I came across this in a feed from HowStuffWorks.com. It's a performance by Arthur Benjamin where he showcases his fairly ridiculous ability to quickly calculate 3, 4, and even 5-digit squares in his head.

Ok, so it might be a little geeky, but I still think it's impressive and entertaining. Click here or the image below to watch the vid.

Pi Day 2008

I can't believe I forgot about Pi Day.

As if the general lack of posts wasn't enough of an indicator of how busy I really am, I completely forgot what today was until TLM reminded 10 minutes ago. The sad thing is I spent a good portion of the day today backing up data from our servers, and must've typed in today's date at least 3 or 14 times. Doh.

Yes, I am a math enthusiast and I am excited by the idea of irrational numbers and the fact that pi has been calculated to over a trillion places after the decimal. I like the official Pi Day site, too, and I think the graphic on the top is a nice touch (expand your window and it just keeps giving you decimals...).

Happy Pi Day!
 

McCain: How is 35% enough?

How is it that right now, at 9:20pm Tuesday night, I'm listening to John McCain give a victory speech and sites are already giving him New Hampshire with only 35% of the precincts reporting? Where is the math to back this up? Might not the other 65% of the state vote differently?
 

Game Trees

Back in high school (not that many years ago, I'd like to think), I was in a programming competition that pitted a program I wrote to play a 2-player game against those of all of my classmates in a single-elimination tournament. I made it to the finals and eventually won, though after discussion with the other finalist we both realized that based on our PASCAL code (ok, that many years ago) the winner would have been the program that went first. More importantly, both of us wrote very shortsighted code; that is, we set up a series of rules like "look for a winning move first" and "look for a block second". It was only a matter of time before I learned the more traditional computer science approach to creating algorithms for 2-player games: game trees.

A game tree is a symbolic representation of all the possible outcomes of a game where nodes are the "states" of the game at a given time and the connecting arrows are the possible "moves" (called "plys" in game theory). Think of it as an inverted tree where the root node represents the start of the game and all its branches representing a player's first turn.


The common example for explaining game trees is the well-known game of tic-tac-toe. Player 1 starts out with a blank grid and 9 possible squares to click in. After a spot is chosen (and an "X" is placed), there are 8 other squares from which player 2 can choose (and place an "O"), which then leaves 7 squares for Player 1, and then 6 for Player 2, and so on. You can guess that even a game as simple as tic-tac-toe, guaranteed to be over in 9 moves, can have a pretty large number of possible ways it can be played. At first glance you may even calculate the number of nodes in the game tree to be 9! (362,880), though luckily there are several factors we can use to trim this number down (to 26,830 nodes, in fact).

The first way to trim a game tree is to consider all of the branches that never make it to ply number 9 because the game has already finished. For example, imagine Player 1 winning with 3 spots still on the grid (however unlikely, it's still possible); the last 3 plys for that branch never need to be calculated. Another important way to "prune" the trees is to recognize any kind of symmetry (rotation, reflection) across branches and represent each by one and only one branch. For example, if Player 1's first move is to a corner, any corner, our game tree only needs to have one branch as each of the other 3 nodes where Player 1's first move is a corner can be rotated to look like the first. The same is true of Player 1's first move if to a side spot. Add in the branch that stems from Player 1's first move to the center spot and you now have 3 branches coming out of the root node, not 9...now that's some good and efficient pruning.

In the project below, I've recreated the commonly seen 2-ply game tree for a tic-tac-toe game. Playing with this visual and interactive model may give you a better understanding of how game trees are constructed. The sitemap of the workBench project is what the (beginning of the) game tree would look like. Look at the number of branches each node spawns and see if you can figure out why none of the 2nd-tier nodes spawn 8 branches. Also, there are lots of other, more sophisticated ways of pruning game trees if you are interested, but they are beyond the scope of this post.



So why are game trees important anyway? Why would knowing about them have changed how I made that program all those years ago? The answer is simple: if you can make a model of all possible outcomes, you can choose the path that helps you the most. In a 2-player game tree, this can be done in a variety of ways, though an easy example is to "rate" each node, started from the end of each branch, or leaf nodes. If a node gives Player 1 a win, assign a rating of 1 to that node. If it gives Player 2 a win, rate it -1, and if it is a tie, rate it 0 (this is how I was taught, though you can use any rating system you'd like, such as colors or shapes). Once all of the leaf nodes have been rated, the nodes in the ply above them can be rated as well, all the way up to the top using the following rules:

1. For each node X on ply Z, look at the parent node Y one level up on ply (Z-1).
2. If all of node Y's children are rated the same way, give node Y that rating.
3. If any of node Y's children are rated as a win for the player whose turn is on ply Z, rate node Y a win for that player.
4. If neither condition applies, rate node Y a tie.

This may seem hard to understand, but in a nutshell all it means is that if you have to choose between a bunch of moves, all of which have ratings already, you don't want to choose one that has at least one outcome where your opponent wins, assuming your opponent will see that opportunity and take it (that's the crux of step 3).

If you are an educator and involved in anything that revolves around game theory, recursion in programming, or even symmetry in high school Geometry, constructing (or filling in already started) game trees for simple 2 player games may be a fun and productive activity.

It may even be the key to you winning a programming tournament in your high school computer class...
 

Yellow Pig's Day

How could I forget this one. Happy Yellow Pig's Day, in recognition of the Yellow Pig and the number 17.

Flatland the Movie

Ah, Flatland...the 19th century essay about life in a 2-dimensional world and the subject of many a middle school math class across the globe (hopefully minus the slightly sexist undertones). Written in 1884 by Edwin A. Abbott (whose middle name also happens to be Abbott!), the essay is an exposition on the notion of extra dimensions as well as a "satire on the social hierarchy of Victorian society", as it describes a world whose inhabitants are squares, triangles, pentagons and other 2-dimensional figures whose place in society is rigidly defined by the number of sides they have and how regular they are (that is, how closely their sides are in length to each other).

Well, now there's going to be a movie (wuhooo!). Due for release in June of this year, the main character, A. Sqaure, will be voiced by Martin Sheen, and the trailer actually looks pretty compelling. The website for the movie is pretty slick, too.

If you haven't read Flatland yet and are interested in reading the actual essay, you can download it from Project Gutenberg for free.

Now all I have to do is convince TLM to go see this with me...

Pi Day 2007

Another 3-14, another Pi Day. Last year's post featured that Zoom! parody about wizards, womanizing, and of course, pi.

This year's Pi Day post will feature none other than Pi. That number, again? Nay, I speak of none other than Piao Sam, a.k.a. Pi from the CW's third installment of "Beauty and the Geek". Billed as the "only kissed one girl" geek, he and his partner Sheree (the "former Hooters waitress" beauty) were promptly the second couple sent home.

Oh, if only we could have seen more of you throwing down your Pi-like gang sign, Pi.

"Internet surfing, karaoke and poker. I almost got trampled standing in line for Playstation 3." - Paio Sam

Impossible Ranking Systems

I should start by saying I've never been a fan of college football. Check that: I like the actual football, but I can't stand the system by which the bowl games are "calculated". That's right, rankings.

Even when approached with seemingly the most scientific methods, college football ranking systems have always seemed vague and completely subjective to me (and the end of the year awards presented to individuals too for that matter). Science News recently had an article outlining how such systems' ability to produce "reasonable results" are inherently impossible.

In a paper published in a recent issue of SIAM Review, Paul K. Newton and Kamran Aslam of the University of Southern California argue against the widespread belief that it is possible, with just the right tweaking, to come up with a ranking system that yields reasonable results and eliminates logical inconsistencies—and, hence, settles all arguments, leaving everyone satisfied.

At the heart of the argument is the challenge of assumptions made when coming up with the various ranking systems. Highlighted is the assumption that "when team A is ranked higher than team B, and team B is ranked higher than team C, then team A is ranked higher than team C...seems like a reasonable requirement". This assumption is shown to be faulty, particularly when votes are part of the process.

So how do the bowl games get determined, if not by some ranking process? That's the million dollar question (not that the collegiate atheletes get any of it, at least not legally...). Well, unless another option is presented, science be damned (uh?), as the current system is what we have that works best so far.

Tangentially, this reminded me of a (not-so-recent) post on InsomniousPolitico where there was an attempt to classify various popular dichotomies (the term is used loosely) into two distinct groups; an attempt met with many vociferous comments as the ultimate goal seemed to be grouping logic, men, and conservatism against emotion, women, and liberalism (go see and decide for yourself). In this Science News article, the aforementioned faulty assumption and the example they chose to illustrate it (the selection of the top men's tennis player in 2002) is also exactly why Jaz's attempt to make two mutually exclusive groups won't work.

Let's say you have 3 groups of 2 instead of 3 individuals, groups A, B, and C. Group A may match up with group B in a particular way, and group B may match up with group C in a particular way, but that does not say anything about the relationship between group A and group C, which must be handled seperatly (particularly when the matching up of groups is as subjective as was outlined in the post). As in the tennis example, it is possible to have, even in a sample space as small as 3, a circular state of relation between the groups. Consider the following pairings:

Pairing 1		Pairing 2		Pairing 3
A1	A2	B1	B2	A1	A2
B1	B2	C1	C2	C2	C1

There are only eight possible ways the three groups can be grouped together, and all of them will go against how we defined the group pairings above in exactly one way.

Potential Group	Bad Because of
A1, B1, C1	Pairing 3
A1, B1, C2	Pairing 2
A1, B2, C1	Pairing 1
A1, B2, C2	Pairing 1
A2, B1, C1	Pairing 1
A2, B1, C2	Pairing 1
A2, B2, C1	Pairing 2
A2, B2, C2	Pairing 3

Well, you can't blame a guy for trying (to equate conservatism with logic). Anyway, sorry for what was I'm sure way too much information...I have occasional relapses into math education background. And I miss making tables.

Mini-math: Flash Mind Reader

So here's one for all you algebra 1 buffs / students. Why does this "Flash Mind Reader" work? After being wowed a couple of times (or not), try to find a pattern in the numbers you end up with then an explaination and proof to solve it.

I put a solution in the comments, if you want to see if you are right (or you're just lazy).

01:02:03:04:05:06

How am I not gonna point this out...

Three seconds after 1:02 this morning, the time+date read- 01:02:03, 04/05/06. Some people even will recognize this twice today, once in the AM and again in the PM.

Wow...I haven't had this much fun since about 5 years ago, say around 6:00 early in March.

Pi Day 2006

So yesterday (3/14) was Pi Day. Ah, pi...usually the first number people are exposed to that has no ending and no repeating pattern inside. Fun for middle schoolers everywhere...

This is a (weird) vid from at least 20 years ago that I guess tries to get kids excited about pi. Really it's more trippy than educational. Who the hell are these monotoned wizard types and why are they killing the happy children? What does that have to do with pi? Who came up with this?

I swear at one point, while we are passing through a television being cradled by a masked wrestler type, we hear somebody say "Yo I know this pi shit backwards and forwards", followed by a rap which starts out "I did three chicks then I pointed at the door..." How kid-appropriate is this, anyway? Or maybe things were just a bit more lax in the 70's.

ADIOS, or Language Math

I thought this interesting enough to post:

ADIOS, or Automatic Distillation of Structure

This raises questions about language, and (very) indirectly, about how one thinks. People have been in search of patterns to how we think about things for centuries; how far away from that are patterns to how we communicate with each other?

Giga-bullshyte

Weak.

I get this Lacie external firewire drive labelled as 160 GB, bring it home, and lo and behold it comes up as having only 149.01 GB available. What's the deal? Where'd the other 11GB go?

Well, after checking the Lacie site to see what the problem might be, I find some lame explaination about how manufacturers apparently use a different definition of GIGABYTE than computers do. makes a lot of sense, eh?

So in math world, giga- means 10^9, so a gigameter is 1,000,000,000 meters (like kilemeter means 1,000 meters). For computers everything is base-2, of course, and so the closest power of 2 to 1000 is 1024, or 2^30. Ordinarily, people don't ever need to do this conversion, as when one looks at the size of a file, drive, or folder the result is usually presented in the computer-defined format (i.e. you have 59.4 GB available). So while I thought I was buying 160 GB, or 171,798,691,840 bytes, I was really buying 149.01 GB, or 160,000,000,000 bytes.

Why then would the number on the box be calculated with a different number than what is actually important to the computer? Easy answer...people think they're getting more, and manufacturers are getting away with it. Sounds like false advertising to me...

Byte me.