Monday, October 20, 2014

Problem of the year 5775

OK so it's 5775 according to the Hebrew calendar. Which means of course that it's Problem of the year time (well ok it's a bit late but so what).

5775 turns out to be kinda tough (or I'm being silly).

(5+7)/(7+5)=1 is pretty easy.
getting 5-sqrt(7+7-5)=2 took me quite a while.

I have at the time of writing no way to get 3.

5-(7/7)^5=4
5*((7/7)^5)=5
5+(7/7)^5=6

all sort of fit together. 

7 like 3 I don't have yet, although I've spent less time on it.

5+sqrt(7+7-5)=8

5-(7/7)+5=9
5*(7/7)+5=10
 5+(7/7)+5=11

 again fit into a nice group.

This is about where I stopped thinking about these (because 3 and 7 where incomplete).

 So naturally the point of this post is to see what people come up with for the 3,7 and things bigger than 11.  Enjoy!

Thursday, August 28, 2014

SATMO 2014

Last Saturday, the 3rd annual South African Tertiary Mathematics Olympiad was held. For US based readers think of an SA version of the Putnam contest.  Full results, questions and solutions,  can be found here.

Two of the questions (8 and 17) this year where submitted by me. Question 8 I first heard from Michael Lugo and question 17 I first heard from Pravesh Ranchod

A huge thank you for organizing the event goes out to Stephan Wagner of Stellenbosch Univesity, as does a huge congrats to the winners.


Monday, July 28, 2014

I've recently been involved in the formation of the Wits Undergrad Maths Society

This has involved going to a bunch of lectures and handing out sign up sheets. It's also involved a lot of talking to lecturers and other organizers to timetable this but I want to focus on the signup sheets.

Turns out that a fair number of students use there wits e-mail addresses and a fair number use something else (g-mail the most common). By inspection there seems to be a very very large correlation between what sheet you signed and which e-mail you put down. that is to say that some of the sheets are almost completely (or in some smaller cases completely) covered with students using there wits e-mail while others are almost devoid of student e-mails. 

Presumably students look at the first few people putting down a wits e-mail address and decide to copy or see the first few haven't and decide to use the non-wits address. Anyone have any thoughts on what causes this?

Friday, July 18, 2014

Hats

Dmytro Yeroshkin and myself have uploaded a paper to the archive here .
It's on a  hats game which is well described here by Tanya Khovanova, and originally proposed by Lionel Levine

There are a lot of opportunities for future work left. In particular the original problem with alot of wise men instead of the 2 player case described in our paper.

Friday, June 27, 2014

and the next line is...

An old puzzle today. this one is great for a blog format as it allows someone who has solved the puzzle to verify that they know the answer without giving away the answer to everyone
The problem is to find the next line. Enjoy and show the next line when you have it.

1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
3 1 2 2 1 1

Thursday, May 8, 2014

I'm thinking of a number...

Here is a game. You are presented with countably infinitely many boxes. Each containing a single real number, you're allowed to open as many boxes as you like and view the number inside the now opened box. However to end this game you need at some point in time to point to a specific box and before opening it guess the number inside it. Due to horribly unimaginative rules, you win if you guess right and lose if you guess wrong.

At first glance this seems like a game you're bound to lose all the time. However if you arm yourself with the axiom of choice it is possible to win with large probability. Your challenge is to find the optimal solution.

Hat tip to Zach Hamaker for showing me this problem which I believe originally comes from his advisor Peter Winkler

Saturday, April 5, 2014

Proofs from the book

I came across a really nice thread on Quora today. It asks about the most beautiful proofs in mathematics.

Alot of people gave alot of really nice answers. The thread is here. Anyone have any other good ones?

Saturday, March 29, 2014

Really really ridiculously cute

Apologies to Zoolander for the title. But if you're feeling down about the various things to feel down about in the world, then  Cuteoverload is really cute and cheer uppy.

Tuesday, March 25, 2014

Just a cool link today.

Ever wonder how many people are in space? At time of writing 3
http://www.howmanypeopleareinspacerightnow.com/

Monday, March 24, 2014

A puzzle of primes

This is a fairly old one I first saw in a high school, at one of the Stellenbosch university olympiad camps.  Enjoy.

It's possible to find a string of 1000 consecutive integers with no primes. For example
1001!+2,1001!+3,...,1001!+1001. Does there exist a string of consecutive integers with exactly 5 primes?

Sunday, March 16, 2014

Another powers of two post

I've been negelectign this blog of late.
To keep the posts flowing here is one of the internets great time sinkers.



Monday, March 3, 2014

Odin takes quizzo way too seriously

Recently I've  reread parts of Tales of the Norsemen by Roger Lancelyn Green. Who does an excellent job of describing various mythologies (there is a series).  Anyway one of the myths described is of Odin and the wise giant Valfthrudnir having a "quiz to the death".  As described in the link they agree to ask each other questions until someone gets one wrong and then the winner cuts off the loser's head and keeps it.

I've got a question about this. First up how do they decide weather a particular question is right assuming they disagree? In this tale they don't but what exactly stops a conversation like this happening?

Valf: Which Stallion draws the chariot of the moon?
Odin: It's called "Milky".
Valf: No it's called "Snowy" I get your head!!
Odin: No I'm pretty sure it's "Milky" so I get your head.
Valf: SNOWY!!!!!!
Odin: MILKY!!!!!!!!!

How do they go about judging this?


Tuesday, February 11, 2014

Chain Rule Intuition -Guest Post by Greg Henselman

My friend Greg Henselman has some really nice intuition about the chain rule. He put it on facebook and this is the thing reposted with some mild modifications. It was initially a reply to a student who didn't quite seem to get the chain rule. Anyway I thought this explanation was freaking awesome. In fact I wish someone had taken me aside when I was learning calculus and given me this or something like it. I spent a couple of years thinking of the chain rule as a formal thing rather than having anything remotely resembling intuition for it. When I got to the multivariate version I was even more confused.  Anyway this explanation would have saved me a few years worth of grief, so if you ever need to explain the chain rule to someone please give them this or something like it.

Anyway without further adieu here is Greg's post.

....

Imagine a long, narrow canal populated with a complex ecosystem of fish.  Because many of these live in schools, some parts of the canal have more fish than others.  Let g(y) be the number of fish living in the first y meters of the canal (measured from one end, let's assume it's the West end).  In this context g'(y) has a concrete meaning: it is the density (or, if you prefer, it is just the number) of fish living exactly y meters (no more, no less) from the West end of the canal.


Suppose a fishing boat has been hired to catch the fish and chop them into edible pieces for bigger fish being grown in a nearby lake.  It enters from the West and travels East.  If the boat's distance from the West end of the canal at time t is denoted f(t), then the boat's velocity at time t is f'(t).

Assuming the boat catches every fish it passes over, and that the unfortunate fish never get wise and swim East, then the total number of fish in the boat's chum barrels at time t is exactly the number of fish who lived Westward of the position of the boat at time t.  We can write this as g(f(t)) = (g \circ f)(t).  

What is the rate at which fish are being caught at time t?  Without using any calculus at all you can probably see that it is the boat's velocity times the number of fish living directly below it at time t.  The velocity at time t is f'(t), and since the boat's position at t is f(t), the number of fish living directly below it is g'(f(t)).

Putting these pieces together, and remembering that the rate at which fish are caught is the rate of change of (g \circ f)(t), i.e.(g \circ f)'(t), we see

\[(g \circ f)'(t) = f'(t)g'(f(t)), \]
which is exactly the Chain Rule!

Sunday, February 9, 2014

Ruler and compass constructions.

The ancient Greeks liked ruler and compass constructions.  Here is a web site which challenges you to find some of these. Go forth and conquer in the name of Zeus.

Sunday, February 2, 2014

Bad Math

One of my favorite internet black holes is sporcle.com

Here is a maths related quiz, which will either lower your opinion of humanity or make me wonder how low said opinion started off.

Enjoy

Thursday, January 30, 2014

Education the world over

So this isn't really a maths post. Anyway while internet/wiki browsing I came across the UN based "education index". I have no idea of the methodology and for some strange reason the wiki article lists the 2007 rankings.

Anyway here they are , Cuba and to a lesser extent  Kazakstan seem to be better than I'd have personally guessed.

Does anyone know either the methodology here or have access to more recent data?


Tuesday, January 21, 2014

Rubik's Cube 1-Guest Post by Matt Tai

My friend Matt Tai taught me to solve the Rubik's cube. So I asked him to give a series of guest posts on the subject. He threatened to send me a copy of  Henry VIII instead of that post. As the version of Henry VIII he sent me was the play by  William Shakespeare and not the genome sequence of the British King. I managed to convvince him to give us a post on the Rubik's cube today. Hopefully (though it's unlikely) he'll give us the genome sequence next time.

Stuff Matt actually wrote below
The Rubik's cube, invented by Erno Rubik, is a puzzle that has become a cultural icon, a puzzle whose difficulty is widely acknowledged.
The idea of the puzzle is not terribly complex. The cube is subdivided into 27 smaller "cubies", arranged 3 by 3 by 3. The basic action is to grab a 3 x 3 square of these cubies that make up a face of the larger cube, and twist the square around the center cubie; you can twist it a quarter of the way around, halfway around, or three-quarters of the way around. Twisting it four quarters is the same as not turning the face at all.
The cubies have stickers on them, generally in one of six colors; the puzzle is solved when the cubies are arranged such that the stickers form six 3 x 3 squares of the same color, i.e. when the big cube looks like it is solidly colored on each side. The puzzle is then to take a Rubik's cube where the cubies have been scrambled and, via twisting the faces, return the cube to the solved position.
Since the invention of the cube, a myriad of methods for getting from a scrambled position to the solved position have been created. Some are hard to learn, some are easy to learn; some are slow, some are fast. Most methods are hard to simply stumble upon by accident; usually to come up with a new method requires lots of experimentation, during which the cube gets scrambled, although hopefully not beyond the experimenter's ability to solve.
Most people who pick up a Rubik's cube have some success the first few times, perhaps getting a few stickers of the same color onto a single face, perhaps even getting an entire face just by exploration. But that's usually the stopping point. After all, once you've gone through all that effort to get a face together, you don't want to destroy that. But turning any of the faces next to the solved face will move some pieces into the wrong position, undoing your hard work; so you're stuck with only being able to turn the face you've solved and the opposite face. What can you do now?
The secret is that to get the freedom to fix the rest of the cube, you have to temporarily undo your solved parts in such a manner that you can fix them after you've used that temporary freedom, without undoing the new fixes that you've achieved. As you solve more and more of the cube, this gets trickier and trickier.
Thus we get to the second part of solving the cube: planning. This doesn't mean you have to know every single step to take before even turning a face (although there are people who can do this) but you need to have an idea of "I want to solve these pieces first, and then those piece next, and then the rest of the pieces afterward". While less essential than the first part, the temporary-controlled-scrambling for freedom trade-off, this allows you to keep track of what kind of scrambling you're allowing at each step, how much control you need over that scrambling. You could be purely opportunistic and just solve whatever piece is easiest to slot into place, but if your solved pieces are scattered randomly around the cube then they're blocking all sorts of possible moves and are hard to move out of the way.
So most methods can be broken up into these two pieces, which I'll call "algorithms" and "plans". An algorithm in this case is a specific set of twists (e.g. twist the top face a quarter turn, then the right face a half turn, etc) that moves some number of cubes around, while also having some other cubes end up in the same positions that they started in. The first bunch of cubes are the ones you're trying to put into place, the second bunch of cubes are the ones that are already solved and that you're trying not to screw up. A plan is a sequence of bunches of cubes, in order of which ones you'll solve first. For instance, one plan might say "pick a face, put the edge pieces for that face in place, then the corner pieces in place, and then the edges next to those corners, etc". At each step of the plan, the algorithms will tell you the exact set of twists needed to execute that step of the plan; which algoirthm to use will depend on which step of the plan you're on and the actual position of the cubes involved.
While plans are often malleable and often involve some on-the-spot thinking, algorithms are usually just memorized, since they are much less flexible. Substituting a half-turn for a quarter turn can lead you quite far from where you wanted to go, but solving one particular corner before another often isn't too much of a stretch. Algorithms are also less flexible in terms of what they can do; a given algorithm moves a specific set of cubes around in a specific way and keeps a specific other set of cubes in the same place, so if that isn't quite what you want, you'll need a new algorithm. Some methods require memorizing hundreds or thousands of algorithms for particular situations; in return, they get speed, in that the more specific algorithms are also often faster than more general ones. So if you want speed, then you need to have a good memory. You also need to be able to recognize what needs to be done quickly, not wasting time choosing which cubes to get into position next. Hence the need for good plans.
But methods aren't the only things that go into speed. You need dexterity as well. Speed cubers often use all of their fingers individually when solving, and their wrists, so that once a face has been twisted they can go to the next move without having to reposition their fingers or the cube in preparation. Perhaps surprisingly, a lot of effort is put into the physical cube as well. A cube that requires a lot of strength to turn is not going to be good for speed cubning, nor is a cube whose faces won't stop spinning if you tap it accidentally. A good speedcube will be easy to turn, but the faces will stay put until deliberately twisted, and will twist exactly (or almost) a quarter, half, or three-quarter turn, as if you turn a face somewhere in between the other faces will usually refuse to budge. Of course, some speedcubers have learned to take advantage even of this constraint.
Interestingly, the fastest speedcubing methods are not the shortest, in that although someone using these methods can solve the cube in a very short time, there are other methods which involve fewer overall twists. Using fewer twists does make for a shorter solving time, all other things being equal, but these methods with few twists require the solver to spend a lot of time analyzing the cube at each step to determine which twist to do next, while someone focusing on speed will simply keep turning without regard for whether they're taking the absolute shortest (measured in twists) path or not. By the way, the absolute shortest path, if we measure a quarter twist, a half twist, and a three-quarter twist each as a single move, is known to be at most 20 moves long. This was proved definitively in 2010 using a computer running a lot of calculations. Unfortunately, nobody knows how to figure out those 20 moves for a given scrambled position. The shortest known methods take about 50 moves, and involve tons of memorization without much pattern.
Next time I'll get a bit into the math of the Rubik's cube, but for now I'll just note that there are over 40,000,000,000,000,000,000 possible positions for a standard, solid-colors Rubik's cube to be in. That's 40 followed by 18 0s. So someone who knows a general method for solving a Rubik's cube knows how to get from any of those 40 million million million positions to the solved position reliably, and it is possible to do so in only 20 moves.

Sunday, January 19, 2014

2014 fields medals

I have no idea who is getting it. But ran into this during my internet travels. It's a poll for who will get it.

Any readers have opinions?

Google stalking reveals that  Alexei Borodin went to Penn for grad-school, I realize that group bias can be a horrible thing but yeah routing for his victory.

I saw Ben Green talk at Penn's Rademacher lectures and it was a really awesome talk. I'm mildly annoyed that I can't find a video of it, but it was on sets with few ordinary lines.


Wednesday, January 15, 2014

Sums and squares and cubes

Today I'm going to talk about the formula

(1+2+...+n)2=13+23+...+n3


It's a really really super awesome formula and if you disagree you're probably the kind of person who prefers kittens to puppies.
This formula is super cute and so are these puppies.
Typically this is proven by mathematical induction. If you haven't seen this proof then you probably haven't learned induction yet. It's either a very standard exercise or the 3-4 sources I learned induction from where atypical.

Anyway if you don't already know induction I recommend deriving the proof as a way to teach yourself the technique. You'll need to remember the formula for the sum of the first n integers and how differences of squares work. 

The proof by induction works nicely but it's not as pleasing (to me at least) as the formula itself. So we're left wondering vaguely if there isn't a better way to prove this. I've heard 2 proofs of this which I think of this as "better than the induction but worse than the formula".

I'll give them below and ask the readers to give me something which "feels right". Alternatively we can just collect as many proofs of this as there are puppies in that picture.

First proof (hat tip to Matt Tai for showing me this one).


The above pic clearly has area 13+23+...+n3





We draw it a line and swap the blue shaded areas with the red shaded ones. These are in spite of my terrible drawing skills the same size. So this new shape (including the red and excluding the blue) still has area 13+23+...+n3


On the other hand it's also a triangle so it's area is given by the formula for areas of triangles. Which works out to exactly what we want. 



Second proof (hat tip to David Lipsky for showing me this one).

For the second proof we begin with a square. Of side length 1+2+...+n. Yeah that's right the area is obviously the left side of the equation.



As seen above in badly executed MS paint.

Next we make further use of MS paint and colour this picture in.







If it's not obvious the giant purple part in the middle is the part isn't meant to be all 1 colour, the important thing is this nested way of drawing the picture. The claim is that the area shaded in colour n has area  n


This is actually not too hard to see. We have 1 nxn square with area n2 moving up we have an n*(n-1) rectangle. Which pairs nicely with the 1*n in the bottum left corner as having area n2. Moving up and in from this pair we find an n*(n-2) and a 2*n which give us our 3rd n2 area. We Then go up on the right hand side and right on the bottum row to get more pairs of rectangles with combined areas of n2 , turns out we have n total such areas.  Completing the proof. 
Personally this proof strikes me as nicer than the other 2 but still not quite as nice as the formula.
So please leave better solutions in the comments below.



Saturday, January 11, 2014

1000 creative islanders

The thousand islanders problem is a reasonably well known problem which goes like this.

On a certain island there live 1000 people, who follow a strange religion (possibly not as strange as some real world ones but still pretty strange). The two tenants of this religion are that everyone must attend the daily gathering  at noon in the village square and that should an adherent learn their own eye colour they must commit suicide at the next daily gathering in front of the whole village.

The result of this is of course that these islanders have no mirrors and that no one ever mentions anyone else's eye colour. As a further departure from reality in the world of the islanders everyone has either blue eyes or brown eyes (so for example no green eyes, yes it's an oversimplified world so that the puzzle works just go with it).

It's also common knowledge that everyone has one of these two eye colours. By common knowledge I mean everyone knows this, and everyone knows that everyone else knows, and everyone knows that everyone else knows that everyone else knows etc etc. As it happens exactly 100 of the 1000 islanders has blue eyes (for the innumerate readers who're probably on the wrong blog, this means the other 900 have brown eyes).

One day a stranger arrives on the island and being ignorant while being feasted (in the evening after the daily gathering but still in front of the whole island) makes the following remark "How interesting to see another blue eyed person in this part of the world".

The usual question is then  "Does anyone actually need to kill themself?" If you don't know the answer you might want to go think about things before reading any further.



Assuming the islanders are all perfectly logical and all know each other to be perfectly logical (and all know each other to know each other to be perfectly logical etc)  is that yeah they do need to kill themselves, those with blue eyes on day 100 and those with brown eyes on day 101.

I'll leave the reason why for the discussion (or google if you want, this post is going to be too long if I fill in details too carefully and I'm lazy). But here is an interesting extension: Suppose that some people secretly know that they are blue eyed (and have so far defied the order to commit suicide). If they commit suicide early can they save the rest of the village? What if these early suicides are from true believers who don't know there eye colour (i.e. some of them are brown)?  On a less nice variation can a single  villager with a machine gun save the village by shooting a few blue eyed people at the next gathering? What if a single person gores out there own eyes?? Or just loudly shouts at the stranger "I didn't hear that but you should try this particular desert."


Thursday, January 2, 2014

100 lights-puzzle

Another puzzle, because if you haven't figured it out I like puzzles.
Hat tip to Jason Bandlow for showing me this one.

100 lightbulbs are arranged in a 10 by 10 grid.

We have some switches to flip these bulbs. In particular we can flip any 3x3 square (9 lights) and any 5x5 square (25 lights). No wrap-around. Start from everything turned off (this doesn't matter but to keep notation consistent). Can you reach every possible state (any combination of off/on positions of the 100 lights) with these tools?



Thomas Edison made it possible to produce 100 light bulbs, so that you can solve puzzles.