So I cooked tonight!

My next goal is to figure out how to post pictures here. I cooked a great meal tonight: lemon curry salmon, wild rice, and green beans. I will start recording my good meals, because I want to remember them. I think the secret to my perfect salmon was the marinade: curry, salt, pepper, olive oil, and lemon juice. Simple enough to be perfect.

POD #4 will appear tomorrow night. I am still researching the weird result behind POD #3: There are in fact counterexamples to p^q where p,q are prime. I don't exactly know the correct answer yet, and I will only progress when I have another question to post. I just want to keep the quality up.

Do any of you coders out there switch into vi mode whenever you start typing? I just did; every once in a while I'll want to alter a paragraph above me and start jamming ESC-kkkkkkkkkkkkkkkkkkkkkkkk, wondering why in the hell the cursor is still in place. I remember a time when I hated vi with a passion. Now, I can't imagine writing code without at least gvim as an option.

Holy crap Lost just threw me for a loop. What a goddamned cliffhanger that was. But I still don't know where the polar bear came from, so I'm not completely satisfied. :) Night all.

Blogger keeps mucking up my posts...

Ugh. When it comes to math blogging, Blogger totally sucks right now (until I learn some MathML). I always have some formula mutilated. Anywho, I am recovering from a trip to Tigin for trivia night on Tuesdays. I had a blast, joined a team, and had some fun. Met some cool dudes and some cute ladies too... It was totally fun, and will repeat next week. :)

LHIRT POD #3 Solution

Here's the solution to LHIRT POD #3, again written white on white (highlight to read):

According to Catalan, _2NC_N = ∑_{I N}C­_I ². Since _N C ₀ = _N C _N = 1, there’s where our 2 comes from. It turns out that _N C _x where 1 < X < N. Therefore N C _I = 2 + ∑ _{1 N} C _I = 2 + (N * k) for some k. This means that the remainder will always be 2. As far as the converse, consider 343 as an example. ₆₈₆ C ₃₄₃ (mod 343) = 2, and yet 343=7 ³ and thus not prime.

One issue with this: I have yet to find a counterexample that isn’t in the form p^q where p and q are both prime. Interesting?

Cool problem huh? Anyone want to conjecture on that final form of the answer?

LHIRT POD #3

It's time for a little number theory for the POD:

Let _nC_r be the number of ways to choose r items from n objects (or "n choose r"). Assume p is prime. Determine what the remainder of _2pC_p divided by p is, and prove it. For extra credit, is the converse true?

This one may be a little tough if you don't see it off the bat, so I'll leave it up for a while. Besides, I'm not entirely sure about the converse part myself. :)

LHIRT POD #2 solution

Solution for POD #2 below (white on white below):

Let the point on the inner circle be T. Because PQ is perpendicular to OT, OTP is a right triangle. Therefore OP²=OT²+PT². Now, the true area of the doughnut is (π/2)(OP²-OT²)= (π/2)(OT²+PT²-OT²)=(π/2)(PQ/2)².

Amazing, huh? Of course the smart-ass answer is that because a formula must exist for this area based on the length of that tangent alone (or else the problem wouldn't have an answer). Since the radius of the inner circle does not matter, make it radius 0, and the area will stay the same or just the area of the remaining circle. In a non-authoritative setting this form of reasoning is invalid, because you can't be sure if the questioner is being honest in implying the existence of that formula.

Another problem will be posted tomorrow.

Ha ha

It seems that I can't keep up with a daily puzzle, it is a lot of work and my schedule prevents it. I will be instead doing a couple of PODs (Problems of Difficulty :P) a week. This will also allow me to vary my posts more. There is too much in my life going on just to flood it with daily puzzles, no matter how much fun they are.

There's a lot of cleaning in my life recently. Recently I sold my PS2 and all games. I've vastly reduced my diet. My activities are paired down to affordable basics. My theory is that the less I'm invested in, the more invested I am in those activities. Maybe it'll pan out, maybe not, but it's something to try.

LHIRT's POD #2

The problem derives itself from an old puzzle book that solves this problem in a very clever way. I am looking for the real solution, which isn't more difficult than the original method to solve it.

Take a pair of concentric circles, that share a center O. Take a point on the inner circle, and extend its tangent to its intersection with the outer circle at points P and Q. Given only the length of this chord PQ of the outer circle, calculate the area between the two concentric circles.

I will give both solutions in the morning, but I am looking for the one that does not assume that a formula exists in the first place.

Lack of acrimony...

Acrimony is the word of the day, and what's remarkable is its absence; it's amazing that even after all the stuff I've burroughed through in the last few days, that I have nothing sarcastic or cynical to think. My breakup with Dawn is prolonged and melancholy, but not sharp or critical. We just mostly avoid each other as she remains here until she moves in with a friend. Her boxes are piling up, the lacuna of her stuff more striking than the stuff itself. I just removed her from my Wii. I think that both of us are more than ready to have this over as soon as possible, but that doesn't mean we wanted it to happen in the first place.

The important thing to learn from all of this is that you have to be careful with whom you choose to live. What remarkable relationship you have with someone will be cast in a much different light once you share living quarters with that person, and no matter how great your link is with someone, no matter how much you love them and they share that love, you must accept the fact that some people cannot live with one another, and to do so will create great and miserable sadness that the love itself can not overcome. One should ease into these things slowly, carefully, and mindfully, knowing that some things are meant to be and some aren't, no matter how truthful that knowledge is.

Now that I've cleared my mind about said issue, I will speak of it no longer.

Answer to POD #1

The answer is in white on white below, highlight to verify your answer. Surprisingly this didn't take me much time, so I'll continue with my questions tomorrow. I will have to qualify by stating that I may pose a problem that I don't know the answer to, and may pass on the problem until I can research it further. This is all but an experimental exercise. :)
Here's how you figure out the expected number of complete rows: there are five possibilities to consider, because you can leave anywhere from 0 to 4 complete rows. You cannot leave 3 or 4 complete rows because of pigeonhole principle: 4 is impossible after removing one, and 3 is impossible after removing 4 (because you can remove an entire row and have one more to remove, destroying another row). So, in all C(12,4) possibilities there are 3 outcomes: leaving 0 rows, leaving 1 row, and leaving 2 rows.

Case 1: leaving 0 rows... you can do this by choosing 1 from each row, or 3*3*3*3 of 81 possibilities.

Case 2: leaving 2 rows... you can do this by first choosing the rows that are complete ( C(4,2) ) then finishing by choosing what to take within the rows that aren't complete ( C(6,4) ) leaving C(4,2)*C(6,4)=6*15=90 possibilities

Case 3: leaving 1 row. First, choose the complete row C(4,1) then choose which 4 of the 9 remaining to remove. But, be careful: of those C(9,4) you must exclude the ones that leave a full row which is [choose first the row remaining then the 4 from the 6 remaining, or C(3,1)*C(6,4)=3*15 or 45] so C(4,1)*(C(9,4)-45)=4*81=324.

To confirm: 81+90+324=495=11*5*9=12*11*10*9/4*3*2*1=C(12,4)

So, now that we have all the possibilities, let's calculate the expected value E=(81*0+90*1+324*2)/495=738/495=1.49090909... so the expected number of rows is about 1 1/2 rows. More likely than not, you'll have 1 complete row remaining.

I had a really fun time tonight, scoring 46 points in the brainmaster's competition at Tigin. I must look up this website; it sounds like a lot of fun. But, it makes for a long night, and your dear author is too tired to continue. Will write again tomorrow.

LHIRT's POD #1

As promised, here is the first problem of the day. This one was brought to me by Kyle, my sister's friend's brother whom I met at my sister's graduation last week:

Take 12 pennies, arranged in a rectangle of 4 rows and 3 columns. Next, randomly remove 4 of those pennies. What is the expected number of complete rows that remain?

I will post the answer to this puzzle later tonight. I may ROT13 it so that I don't spoil it for any readers.

(PS -- LHIRT is the acronym of my pseudonym)

A problem a day

I almost finished the book Flow, and the more I reread certain passages, I am just about convinced that Mihaly has found the essence of being happy. In my newly found solitude, I am in need of more challenge to prevent my descent into simplistic vices. I have thus decided to embark on my "problem of the day": a small logical/mathematical puzzle that I will post the solution for in the evening. I want to see how long I can keep it up.

Man, last week's Lost was utterly depressing, but now a lot of stuff makes a lot of sense. Can't wait for tomorrow's episode. That being said, I'm very close to giving up my normal cable service, and only having internet/phone connection. TV just sucks up too much psychic energy. More on this later.

New morning, long vacation

I had a very interesting vacation with my sister for her graduation. I don't want to go back to work today; the pile of things to do is enormous. However, my mind is so clear right now that I couldn't feel more at peace. I am totally ready to jump back into the grind.

I decided to write up at least one math problem a day to keep my abilities sharp in between blog carnival posts. I had a time relearning all the steps to the proof of Burnside's Lemma. It's been way too long since my learning of group theory, and a lot of my math is rusty.

Indeed, a lot of things are rusty that I have neglected to keep up. Time to correct that. :)

Woo hoo I did it!

I got my blog carnival post done, and it really was a lot of fun! I'm starting to realize that I've been doing a lot of things in my life that I don't make a point of appreciating or enjoying, and I mean to correct that. I'm currently in West Lafayette celebrating my sister's impending graduation and living it up. I am also almost finished with the book Flow, and it's amazing. My earlier posts on videogames are really coming into focus now. I really feel like I'm starting to enjoy living again, and what's even more surprising is that I don't feel guilty about it.

I wonder if I'm still drunk. :P

On Burnside's lemma and colorings of the cube

I’d like to discuss counting for my carnival post. Counting seems to be a trivial problem: it is the first math lesson anyone gets, because it is at the heart of what numbers are and how they connect with the real world. Surprisingly, this most basic use of mathematics is the most subtle, and there’s a whole branch of math that discusses not only counting but also other discrete (non-continuous) topics called combinatorics.

There are two main difficulties to counting, when you break it down: 1) distinguishing between distinct elements of a collection of things, and 2) enumerating them. This may seem trivial, yet both steps are crucial. There are simple examples of objects that are countable yet notoriously hard to distinguish (the set of unique graphs with N vertices up to isomorphism), and sets that have distinguishable elements yet cannot be enumerated (the set of unique real numbers). Mathematicians have numerous (yet countable :P) tools to deal with these issues. This article will discuss one of the most powerful in the toolkit.

I’ve been inspired by an earlier carnival post where there was a rather lengthy discussion of the permutations of the Rubik’s Cube, in which it is stated that there are 43,252,003,274,489,856,000 states of the cube. What I find more interesting than this ginormous number is the smaller number 12. That’s the number of different ‘kinds’ of cube, of which only one of these is actually solvable (if you ever had someone bust a cube in order to scramble it, you know what I mean).

Any time you ask how many ‘kinds’ of object there are, you invoke of my favorite results of combinatorics: Burnside’s lemma. Instead of answering the question “How many objects do I have?” Burnside’s lemma allows us to answer the question “How many kinds of object do I have?” I’ll attempt to break down for you why this lemma is important as simply as possible, how it is used, and how ubiquitous it is. While I won’t tackle the number 12 in this article (we’ll need Polya for that), I will tackle another interesting question that has puzzled me since I saw a beginner’s cube with only two colors in a toy store in New York: how many ‘kinds’ of solvable cube are there?

Let’s start with some history, because even using the name Burnside’s lemma is controversial. William Burnside published this lemma and its proof in 1897, but the technique existed before Burnside; Cauchy and Frobenius independently discovered this method on their own. Some mathematicians call it the orbit-counting theorem or the lemma that isn’t Burnside’s (as opposed to the many lemmas that were; Burnside was rather prolific in group theory). I’ll still use the term Burnside’s lemma, because that’s how I learned it, and in fact it really is a lemma, not a theorem. Heck, it’s even a corollary.

The problem domain we will be discussing will be the counting of finite objects, so the focus will be on the first half of counting discussed above: Distinction. It is a difficult problem because of the fact that two objects can be distinct and yet counted as two elements of the same ‘kind’ of object. There are two ways to look at this. One way is to make piles of items such that any two objects in a given pile are similar, and then just count the number of piles (I know that the Ace and Queen of Spades are the same suit, because if I change the A to a Q it’s still a spade, so let’s put them in the same pile and count all the piles later). The other way is to count the number of ways a pair of objects can be different, and see how many of those kinds are represented in the object set ( I know there are thirteen ranks in a deck of cards by scanning the deck and counting the different ranks I see as I come along them).

It’s interesting that when discussing distinction, we get into equivalence. This is in fact the pure genius behind the lemma that proves Burnside’s lemma: equivalence creates both 1) A collection of distinct piles of elements in the set called a partition and 2) a collection of symmetries for each object that each object seems immune to. The technical way of expressing this is to say that in the actions of a finite group upon a set, there is something like a one-to-one mapping between the orbits and the stabilizers. It’s called the orbit-stabilizer theorem and will make more sense later.

Let’s explain the terminology. Start with a set of objects that we want to count and call it X (for example the set of all possible states of 3x3x3 Rubik’s Cubes). There are ways of changing one object in X into another object in X. These are actions, literally injective functions from X to X. If these actions are reversible (no blowing up the Cube, drawing on stickers, or taking a hammer to it), then these injective functions are actually bijective, and by Cayley’s theorem, each bijective (reversible) action is actually a permutation of the elements of X. Therefore the set of all actions on X constitutes a finite group with composition as its operator.

This is where you ask the question “What is meant by ‘kind of’?” . If you take the cube and turn it around, is it the same cube? This depends on the type of question you’re trying to answer. If a cube is the same no matter its orientation, we must consider that a rotation of the cube is really a symmetry of the cube. The set of all symmetries is a subgroup of the set of all actions, and definition of this subgroup is crucial to defining the question. At this point, two objects in X are considered the ‘same kind of object’ if there is an action in this symmetry subgroup that transforms one object into the other. As a mental exercise, verify that ‘same kind of object’ is actually an equivalence relation: you’ll find that the laws of a group line up nicely with the properties of equivalence relations.

Call this symmetry subgroup G. It is important to know the relationship between X and G: X is the set of objects placed under the influence of actions in G, or G acts upon the elements of X. Take an action g in G and an object x in X. The action g turns object x into another object called gx, and x is considered to be the same kind of object as gx. There are three important concepts in this model to consider:

1) Take the set of all objects that are equivalent to x. This is called the orbit of x or Gx. The family of all orbits is called X/G.

2) Take the set of all actions upon an object that don’t do anything to that particular object. This is the set of stabilizers of x or G_x.

3) Take the set of objects such that a given action doesn’t change that object. This is the fixed set of g or X^g.

How are these related? If two objects have the same orbit, then there has to be some action turning one object into the other, meaning they are considered equivalent. If you take the set of all actions and apply each one to the same object, it generates all the elements of that orbit. In fact if you squint at this a little bit, you can imagine seeing that orbit of x, being driven from object to object in its tight circle by the whims of the actions of G. We discussed orbits before when talking about distinction. In fact, this partitioning of X into orbits is the disjoint family X/G, and the size of this family is the answer to our question.

So how do we count orbits? Recall that there are two points to distinguishing objects. Here’s the cool part: that stabilizer of that x whose orbit we were looking at? It’s a kernel of this mapping of G onto x, and the moment I say kernel, you should immediately be thinking of the quotient group formed by it. By calculating that quotient group G/G_x suddenly we have a collection of cosets. Each of these cosets is a collection of actions that will always translate x to a y and always that same y in that same orbit. This G/G_x becomes a way of saying that the elements of this orbit are different in the same way, and they match up one-to-one. This bijective mapping is the orbit-stabilizer theorem and it’s the lemma to Burnside’s lemma, because instead of counting the orbits, we can count the stabilizers instead and use the bijective mapping to get our answer.

So how do we count the stabilizers? Let’s look at the third concept above. Fixed sets are a really useful thing to look at: it’s relatively easy to count the size of a fixed set, because you’re looking at one symmetry at a time, and analyzing the effect of that symmetry. So how are fixed sets related to stabilizers? Well, fixed sets are to actions what stabilizers are to objects. If we made a big chart with actions g going down the left side, objects x written across the top, and a check mark everywhere gx=x, you could see that each row of checkmarks represents the fixed set of that action, and each column of check marks represents the stabilizer for that object. They’re two different ways of counting the same set of checkmarks:

∑_gX^g={(g,x) gx=x} = ∑_xG_x

Now we are getting somewhere. Instead of counting the stabilizers we’re counting the sum of the sizes of all the stabilizers. What’s the size of a stabilizer? This is where that orbit-stabilizer theorem comes in. Remember that the stabilizer is a kernel of that big mapping that finds orbits, and that the cosets of that kernel are representatives of each element in the orbit. Now use Lagrange’s theorem: the number of cosets times the size of any one coset (they’re all the same size) is the size of the group. The number of cosets is just the size of the order (by orbit-stabilizer theorem), so divide:

∑_gX^g={(g,x) gx=x} = ∑_xG_x=∑_xG/G_x

Pull G out of the summation, because it’s a constant. But now it looks like we’re adding up a bunch of fractions, the sum of the inverses of the size of each orbit. How is that supposed to be a whole number? Remember that if two objects are similar, they are part of the same orbit. Moreover, no two orbits can intersect. Why? Because if x in one orbit intersected with z in another orbit, there would be an object y in both orbits such that gx=y and hy=z thus (h*g)x=z and h*g would prove that x and z are in the same orbit. As discussed above, orbits partition the object space into distinct piles. So if there are 5 elements in an orbit, then that orbit will be counted 5 times for 1/5 each time, and volia we’re back to 1. So, this summation is really the count of the number of orbits or X/G, the very number we’re looking for:

∑_gX^g={(g,x) gx=x} = ∑_xG_x=∑_xG/G_x
=GX/G

Divide by G on both sides and we have Burnside’s lemma in the flesh:

X/G=(1/G)∑X_g

Or: The number of distinct orbits (read kinds of object) is equal to the average size of the fixed sets.

Now that we know why it’s true, how do we use it? A simple example should help here: say you have a strip of 5 red and green squares in a row. How many kinds of strips are there? Start with X: There are 5 choices of red or green or 25=32 different strips. But that over-counts: RGRGG and GGRGR are actually the same strip, just one is the other flipped over. The action to factor over is “flipping over the strip.”. Therefore the two actions in our symmetry group are e, which is leaving the strip alone, and f, which flips the strip over. By Burnside’s lemma:

X/G=(1/2)*(G_e+G_f)

G_e is the easier one to calculate: since nothing happens, everything is fixed by it, therefore 32. G_f is fixed if the first and fifth squares match, and the second and fourth squares match. Choosing the first, second, and third squares are sufficient to choose the pattern, so there are 23 or 8 such patterns. Therefore there are (1/2)(32+8) or 20 different patterns.

Burnside’s lemma gives us a striking derivation of the Mississippi formula, counting the number of permutations of a set of symbols with duplicates. The formula is P=(n!)/∏(r_i), where n is the number of symbols overall and r_i is the number of duplicates of symbol i. From the perspective of group theory, let X be all the different permutations of those symbols with duplicates numbered. There are X! of those permutations, and they are the objects. Let a_i,P be the action of rotating the duplicate i symbols using permutation P. For each symbol i there are r_i! permutations, and the action group is the direct product of those permutation subgroups, a group with ∏r_i! actions. Now, here’s the trick: only the identity action will fix any objects and there are n! of them. Therefore X/G=(1/G)∑X_g=(1/∏r_i)(n!+0+0+0+0+…)=n!/∏r_i!. Many times when using Burnside’s lemma, you have to set up the object set in such a way that the division by the action set is clean, like in the example above. When you do this, a lot of the problem’s contours come into sharp relief. In the example above, by numbering the duplicates, you first reduce the problem in a way that makes it easier to divide by the duplicates later.

By now you recognize the pattern in solving a “how many kinds of” Burnside’s lemma type of question:

1) Determine the population of your object set X

2) Calculate the permutations present in the symmetry you wish to factor out

3) Calculate all X_g for each permutation

4) Divide by the size of the action group to calculate the number of orbits

Now with Burnside’s lemma in grasp, we’ll tackle the question we started with… how many solvable cubes could they sell? First we know that there could be at most 6 colors (any more than that and one side would have to have two colors, violating solvability). Let’s assume that manufacturers will only retool the machines they already have, so that they can only produce the six colors on a normal cube, or red, yellow, blue, white, green and orange. Let’s label the sides 1-6. Then there are 6⁶ or 46656 different combinations of the cube. This is the population of our object set X.

Next, we calculate the actions on the faces of a cube. The easy way to count this is that any automorphism in R³ is a rotation around some axis, a flip across some plane, or a combination of the two. The nice thing for us is that we don’t have to worry about the flipping part, unless some of the audience is 4-dimensional. Therefore, it’s sufficient to analyze rotations. Furthermore, this line has to pass through the center of the cube. This limits us to three kinds of points that the rotation can happen: through a corner, the midpoint of an edge, or the centroid of a face. There are 3 pairs of faces that rotate three ways, 6 pairs of edges that rotate one way, and 4 pairs of corners that rotate two ways. That and the identity rotation are our (1+3*3+6*1+4*2)=24 rotations.

That’s still a lot of rotations. To simplify the rotation, we can group the rotations based upon their actions on the faces. For example the face rotation (1234) will do a similar action as the similar face action (1536) even though they are technically different rotations. When rearranged, we have 5 types of rotation: the identity, a 90-degree face rotation (abcd), a 180-degree face rotation(ac)(bd), an edge rotation(ab)(cd)(ef), and a corner rotation (abc)(def). Each cycle fixes to a single color, which makes this representation very fortunate.
Now we are ready to calculate the X_g. The identity obviously has 66 (everything fixes with the identity). The 90-face will only have 3 colors because the 4-cycle can only have one color so 6³. The 180 face has 4 cycles (2 2-cycles and 2 fixed points) so 6⁴. By similar logic the corner rotation has 6² and edge rotation has 6³. We now have all the pieces to calculate X/G:

X/G=(1/G)∑(X_g)=(1/24)( 6⁶+6*6³+3*6⁴+8*6²+6*6³)=2224.

So, let’s say that we want to figure out the answer for 7 colors instead of 6. Do we have to do all that work again? Nope. The only time 6 colors was used was in calculating the size of the fix points, and it was always raised to a constant power. We could have just as easily calculated for 2,9, or even k colors. For k colors the number of cubes is (1/24)( k⁶+6k³+3k⁴+8k²+6k³), and if you see enough of these you can recognize a particular symmetry by this formula. The special name for this form is called a cycle index.

Which brings me to my final question... why is Burnside’s lemma a lemma? A lemma is a step in a proof that leads to another result but isn’t really significant in its own right. The reason is because of these cycle indices. Polya took the idea of a cycle index a lot further by recognizing something rather brilliant: the cycle index is really a generating function for the counts of each of the rotations! By separating the cycles out instead of multiplying them all together, automating the process of producing the index, and coming up with a way to throw a weight function into the generating function, the Polya Enumeration Theorem was born which allows us to count more complicated symmetries and represent them in a much more elegant fashion. This is really what Burnside’s lemma is a lemma to, and it will be the topic of my next carnival post.

1050 stars...

Nothing special happens at 1000 stars. That's cool; I'm in the process of solving every puzzle, so I can get a time at the end of the game. That in and of itself will be satisfying. I'll let you know the total when it's available.

Yikes, last week really sucked. Major production problems, financial issues, and personal issues collided on the same week. Therefore, yesterday I became a weather vane and went into New York with no plan and it was everything I hoped it'd be.

Today I plan to write an article for the Carnival of Mathematics. I am following the lead of a post on The Happiness Project talking about tips to increase self esteem. I haven't written about math in a long time and I should come back to that.