October 20th, 2009
It is rare for artists, magicians, and other professionals to let people see how they work. Mathematicians, too, rarely expose the thought processes that led them to a discovery – not necessarily because they want to keep this a closely guarded secret, but often just because they just don’t know what the process was (or find it very difficult to describe). Poincaré famously wrote about the mysterious mechanisms of mathematical discovery, emphasizing how letting the subconscious take over helps magical insights to reveal themselves. This is also manifest in how people tend to present proofs: in almost all cases, the argument is presented in the most elegant and slick way, which usually implies that the motivations, partial ideas, false turns and mistakes are well hidden from view.
Tim Gowers is one of very, very few world-class mathematicians who are both capable and willing to share the way they think about problems (the other one I know is Terry Tao). In a recent series of posts (starting here), Gowers explains his attempts to attack the problem of finding lower bounds for circuit complexity. They are fascinating both as a great way to understand the various negative results that were proved in this direction (Razborov-Rudich-style, on why certain natural approaches are doomed to fail), and as an opportunity to see how Gowers approaches the problem.
Posted in Math Circles | 1 Comment »
September 4th, 2009
Tags: Problem Solving
Posted in Math Circles | 6 Comments »
March 18th, 2009
This post contains a problem set that was used at the recent Julia Robinson Math Festival. I created this set after hearing about these problems from colleagues at Google. Enjoy!
In this problem set we will be flipping coins and using them to make various kinds of decisions. A bit of terminology:
- A fair coin is a coin you can flip and it comes up Heads (H) or Tail (T) with equal probability.
- A biased coin with bias
is a coin which comes up H with probability , and T with probability 
.
Problems:
- How can you use a fair coin to choose between 4 alternatives, uniformly at random? By “uniformly” we mean that you should give no special preference to any of the options. By “at random” we mean that you actually rely on the randomness provided by the coin to ensure that nobody can guess what your choice would be.
- How about 8 alternatives? 16?
- Suppose now you have a fair die, which comes up 1, 2, 3, 4, 5 or 6 with equal probabilities. It’s easy to use a die to choose between 6 alternatives, but how can you use it to choose uniformly between five alternatives?
- Back to the coin, how would you use a fair coin to choose uniformly between three alternatives?
- How many flips does your method take, on average? How many flips does it require in the worst case?
If you’ve solved the last part correctly, the next question will make sense.
- Is it possible to fix this worst case behavior? Can you choose among 3 alternatives with a fair coin using 1,000 flips in the worst case?
- Let’s say you only need to choose between two alternatives, uniformly at random, however the coin you have may be biased, and you don’t even know what the bias is. What would you do? Again, what’s the worst case behavior?
From now on, we will insist on having methods that only require a specific, finite number of flips. You get to choose how many flips you need but once you did, the method must always work and take no more than this number.
- Once again you need to choose between 3 alternatives. You may now use two coins rather than just one, and you are free to pick what biases you’d like each of the coins to have (they can be differently biased). In addition, there must be some specific number
such that your method never requires the coins to be flipped more than times.
- Now try to tackle 5 alternatives, again using a fixed number of flips and two coins – you can choose what biases you’d like them to have.
- How about 7 alternatives? 9? Again, you choose the coins, and you decide how many flips you need – but you can never take longer than that.
- How about 15?
- Can you do this in general? For every integer
, find a pair of biased coins such that you can choose between alternatives, uniformly at random, using a fixed number of flips of the two coins.
Now we’re going to raise the stakes…
- Let’s go back to the 3 alternatives. Can you uniformly choose between them with a single coin, and a fixed number of flips? Again, you get to choose which coin you want. (Hint: consider a general coin with bias $p$, and fix some small number of flips. What are the possible outcomes? Some of them have the same probability, and since you’re free to choose $p$ you can dictate a value for that probability. Which useful value would allow you to simulate the two coins you’ve used before?)
- How about 5 alternatives?
- How about the general case? Think of ways to simulate the two coins you used above with a single coin.
- In fact, show that given any finite distribution with rational values, there is a single coin with which you can simulate that distribution in a fixed number of flips.
If you solved these problems correctly, the biases you used were irrational numbers. This has to be the case:
- Suppose you have a p-coin with which you can choose between 2 alternatives in a fixed number of flips. Suppose that
. Prove that p must be irrational.
Posted in Julia Robinson Math Festival | No Comments »
January 27th, 2009
Consider four points in the plane, located at the corners of a square:
(The points are shown as slightly large circles just so you can see them better. Imagine those are actual points, with no width or height). The first question we’re going to ask is: How many distinct distances between pairs of points are there, in this arrangement?
Let’s see what this means, exactly. We have four points. Picking any two of them, we get a cetain distance separating the two. We look at those distances and count how many distinct or different ones there are. So how many are there?
In fact, there are two distinct distances here: one spans an edge of the square, and the other distance is a diagonal of the square. Now this is a fairly special property of arranging four points in this way: there are only 2 distinct distances. So our challenge question for the day is:
Apart from the corners of a square, can you find other ways of arranging four points in the plane, such that there are only two distinct distances between them?
This post is based on a talk I gave at the San Jose Math Circle on 10/1/2008 and at the Bay Area Circle for Teachers. Thanks to Tatiana Shubin, Josh Zucker and Tom Davis for inviting me to participate at the circles.
The images were created using GeoGebra. Try it, it’s great.
Tags: Math Circles, SJMC
Posted in Math Circles | No Comments »
of premises to a set 
of conclusions. Sometimes the road can be long – meaning the problem can be quite hard – even though there is another point 
in “idea space” such that the following peculiar circumstances are true: getting from 