Merry Christmath

MATLAB:

x = -4:.01:4;
a = 1.5;
p = @(x) (1+abs(x)./x)/2;
tree = {@(x) (10-a*abs(x)).*p(x+2).*p(2-x)
         @(x) 7*p(x-.6).*p(2-x) + 7*p(x+2).*p(-.6-x)
         @(x) (8-a*abs(x)).*p(x+3).*p(3-x).*(1-p(-x+1/a).*p(1/a+x))
         @(x) (6-a*abs(x)).*p(x+4).*p(4-x).*(1-p(1.7-x).*p(1.7+x))
         @(x) 3.5*p(x-1.7).*p(3-x) + 3.5*p(-x-1.7).*p(3+x)
         @(x) 0
         @(x) p(x+1.1).*p(-x+1.1).*(5*abs(x)-5.5).*(p(x-.9)+p(-x-.9))
         @(x) (p(x-1)-1).*p(x+1)};
hold on
for i = 1:length(tree)
   plot(x,tree{i}(x),'g.');
end
red_ornaments = [1 2 4 5 2 3 6 9 4 3 2 2 1];
cyan_ornaments = [1 .2 3 7.5 5 .5 6 1 .6 4 1];
plot(linspace(-3,3,length(red_ornaments)),red_ornaments, 'ro');
plot(linspace(-3,3,length(red_ornaments)),red_ornaments, 'r*');
plot(linspace(-3,3,length(cyan_ornaments)),cyan_ornaments, 'co');
plot(linspace(-3,3,length(cyan_ornaments)),cyan_ornaments, 'c*');
hold off
axis([-6, 6, -2, 10]);


There are certainly easier ways to plot this. I just wanted to have fun with absolute values.

Cayley Tables!

Long ago I posted about a mathematical structure called a group. In particular I described the group S₃. If you would like a refresher, read this post. This post picks up where that one left off.

S₃ can be thought of as the set of rotations and reflections on equilateral triangle. Doing that gives the following table called a Cayley Table:

*	I	R1	R2	F1	F2	F3
I	I	R1	R2	F1	F2	F3
R1	R1	R2	I	F2	F3	F1
R2	R2	I	R1	F3	F1	F2
F1	F1	F3	F2	I	R2	R1
F2	F2	F1	F3	R1	I	R2
F3	F3	F2	F1	R2	R1	I

Here's the thing though: This table is too busy to read. Sure, if you wanted to know what R1*F1 was, you could look it up (F2), but it's hard to take in all this information at once. Basically, it's hard to see. 

But you know what's easy to see? Color!

*	I	R1	R2	F1	F2	F3
I	I	R1	R2	F1	F2	F3
R1	R1	R2	I	F2	F3	F1
R2	R2	I	R1	F3	F1	F2
F1	F1	F3	F2	I	R2	R1
F2	F2	F1	F3	R1	I	R2
F3	F3	F2	F1	R2	R1	I

Two simplifications are in order: First, the top row and far left column are redundant, so we can dispense with them. Secondly, the labels are more distracting than helpful, so lets dispense with them as well. This leaves us with just a square grid:

The Cayley Table for S₃

This allows us to more easily see symmetries (the whites are symmetrical along the main diagonal) as well as asymmetries (notice the pattern of blues, greens and purples in the top right corner vs the same colors in bottom left). 

As I mentioned, the group we have been considering is called S₃. There are other groups too:

The Cayley Table for S₄

The Cayley Table for S₅

The Cayley Table for S₆

All of the pictures above are of what mathematicians call Symmetric Groups. But not all groups are symmetric groups. For example, there are the Alternating groups:

The Cayley Table for A₄

The Cayley Table for A₅

The Cayley Table for A₆

And the Cyclic groups:

The Cayley Table for Z₆₀

The Cayley Table for Z₆₀ with the elements arranged by their order

Hopefully I will post some explanations of these groups soon. In the mean time, try your luck with Wikipedia.

The groups are generated by a Python script I wrote. The Pictures are generated by Processing. The list of all possible ways four people can stand in line was generated by Matlab. Altogether there's about 450 lines of code going into these pictures. Anyone who wants access to this code is welcome to leave a comment.

Myth of the Right Answer Redux

Part 1 here.

A classmate brought this riddle to a study group I'm in:

You have eight pills. One of them is poisonous. The poisonous pill weighs slightly more than the others, but otherwise they appear to be identical. You have access to a scale, but you may only use the scale twice (for some reason). How do you determine which pill is the poisonous one?

The solution produced by our group (four undergraduate math majors) is as follows:

Satisfied with this solution, the other members of my study group were ready to move on. This is the myth of the right answer.

We are programmed since elementary school to find "the" answer and move on to our next assignment. Each quiz, riddle, puzzle, and problem is simply an obstacle to overcome in the ongoing mission to meet our teachers', principals', parents', and professors' approval. Why should the authority figure determine when our problem is solved?

So it's great that we found the algorithm to solve this problem with two weighs. But why stop there? Some related questions:

• Given n pills, what is the minimum number of weighs required to finding the poison pill?
• Given n pills that can be weighed with w weighs, is there an alternate weighing scheme that can find the poison pill  in exactly w weighs?
• What if we don't know if the poison pill is heavier or lighter (only that it weighs a different amount)?
• What if every pill weighs a different amount, but the poison pill is still heavier than all the others?
• What if there are two poisoned pills
• Given n pills, m of which are poisoned, how many weighs are required to find the poisoned pills?
• What if the scale can only hold two or fewer pills at a  time?
• Given n pills, one of which is poisoned, and a scale that can only hold k or fewer pills, how many weighs does it take to find the poisoned pill?
• Given n pills, m of which are poisoned, and a scale that can only hold k or fewer pills, how many weighs does it take to find the poisoned pills?
• Given n pills, m of which are poisoned, and a scale that can only hold exactly k pills, how many weighs does it take to find the poisoned pills?
• Suppose we would settle for knowing which is the poisoned pill with probability p, what is the minimum number of weighs?

None of my classmates asked these questions, they were satisfied with just having the answer. To be clear: my classmates are not stupid. In fact, they're all quite bright. But they (we) have been programmed to find the answer, to report the answer, then to forget the question. Somewhere in all of this answer-fetishism we have forgotten how to ask questions. We have lost our curiosity.

A good question is more interesting than a satisfying answer. Why then do we let other people ask all the questions? 

First World Problems

That is one really ugly red car.

Three Page Comic

I really hope I caught all the spelling errors. I probably didn't.