Showing posts with label math. Show all posts
Showing posts with label math. Show all posts
Partitioning
So, I have a few new puzzles in the bank now, so I need to get to blogging again to spend them. I guess I need to start with my solution to the number puzzle from last time.
So, we have a list of numbers L, with n elements, whose sum is S, and the sum is known to both people. Further, they have a product P and if you knew P, n, and S, the list is not uniquely specified. We want to find the list that has these properties with the smallest S possible. We are looking for two lists I will call L1 and L2.
Its easy to see that L must have more than 2 numbers, since if you adjust two numbers and keep their sum the same, the product must get larger for the list that has the numbers closer together (you maximize the area of a rectangle by making it more square). So the list will need at least 3 numbers. Further, if L1 and L2 have any numbers in common, we may as well delete the common numbers from both lists, as they will still have equal total sums and products after common numbers are deleted.
At the point it is basically a matter of playing around, the first solution I found was {2,2,10} and {1,5,8}, which was just playing around with the possible prime factorizations of numbers that seems like good canditates. I was quite certian this was the smallest solution, I am quite sure (but less than 100% sure) that there are no solutions with n=3 that have a smaller S, and I had assumed there wouldn't be a smaller S that used larger n, but then Ben told me he had a solution with S=12, so I had to go looking. Eventually I found it as {2,2,2,6} and {1,3,4,4}. Ben says he has proved with a computer that there are no smaller S solutions, but I am interested if there are any solutions out there with a smaller P, however I doubt it.
Anyway, thats all I got here.
Numbers In A Room
Guess its time for a new puzzle, so I can claim to post at least once a month. This is one Ben showed me, but I am rewording it heavily from the original:
Walking through a building, you overhear a conversation two people are having in a room: Person 1: I have written down a list of positive integers whose sum is the room number of this room. Person 2: If you were to tell me how many numbers were on the list and their total product, would I be able to figure out what numbers were on the list, given that I already know the room number we are in? Person 1: No, you would not. Person 2: Alright, I now know the total product of the numbers. What is the smallest room number they could be in?The "theme" might be a bit thin, but it wasn't any better in the original, and at least this makes it clearer.
Modular Boxes
So, there is a bit of a follow-up to my puzzle last time I had intended to post, but then life got all busy on me, or I am just a slacker or something, but I noticed something funny about the puzzle last time.
When I had worked out that the elements of the 9th row of Pascals triangle (getting 1,9,36,84,126,126,84,36,9,1) and I noticed that they were all multiples of 3 (except for the 1's, of course) I instantly knew that this row must need a minus sign, without having to count and realize that the odd rows get a minus sign and the even rows do not. The reason is that if this particular row did not have a minus sign, then the statement "first box + last box = top box (mod 3)" would depend on how you mapped the boxes to the numbers. If blue=0, red=1, and green=2, then red+red would be green, but if blue=2, red=1, and green=0, then red+red would be blue. Clearly it cannot be the case that the solution to the puzzle depends on how you map the boxes to the numbers, so there must be a minus sign (and -red-red comes out to red in any mapping).
So does this mean something fundamental about the numbers that appear in Pascals triangle? Did I stumble on to some new property that I hadn't seen before? I couldn't quite see what it meant, really.
Talking about it with Ben, he noted that the statement "the answer comes out independent of how you map the colours" it actually a statement about linear functions made up of rows of Pascals triangle (so for example 1,3,3,1 makes 1w+3x+3y+1z). It must be the case that shifting all the variables by a constant shifts the answer by that same constant, and multiplying all the variables by a constant multiplies the answer by that same constant (and any 1-1 mapping of {red, green, blue} to {0,1,2} can be shifted to any other mapping by adding constants or multiplying by constants).
Since the linear functions in question are, well, linear, the multiplying by a constant thing is trivial. As for adding a constant, if we shift (w,x,y,z) to (w+a,x+a,y+a,z+a) then 1w+3x+3y+1z becomes 1w+3x+3y+1z+8a, where 8 is the sum of the elements of that row of Pascals triangle, and naturally -1w-3x-3y-1z becomes -1w-3x-3y-1z-8a. Since 8 mod 3 is -1, we can see that the expression with the minus sign is the one that shifts by exactly a when you shift all of its inputs by a.
This means that a row will shift correctly under this linear transformation if it has a minus sign when the sum of the row is -1 mod 3, and no minus sign if the row sums to 1 mod 3, and where will be a problem if any row sums to 0 mod 3.
Of course, we know the sum of a row of the kth Pascals triangle is 2^k, and that is (-1)^k mod 3, so this is exactly the property we needed, the rows alternate summing to 1 and -1.
I'm not sure anybody else found that as interesting as I did, since it was mostly about stuff that went on in my own head and ended with a fact that anybody who knows about Pascals triangle already knew, but I decided it was worth a post anwyay.
Find The Circle
OK, time to post the solution to the sums of squares problem I put up a little while ago.
I once heard of a game that Feynman used to play with his classmates called "find the circle" in which somebody would state some mathematical fact that has a pi in it and the other players would have to figure out what circle came up in the math behind the fact that resulted in a pi showing up (I can currently find no evidence of this game ever being played, so its possible I was imagining this story, or the relavent character was not Feynman). Essentially, the point is that the only places that pi ever would show up involve a circle, and when it shows up other places you can bet there is a circle hiding somewhere. Personally I don't agree with that philosophy, I think that pi is more fundamental than that, but this puzzle will not be a demonstration of my belief, a circle will show up quite nicely for us.
Alright, let us suppose we have a function, called g(k), which is the number of times that k can be written as the sum of two squares as outlined in the puzzle. Next we will let f(m) be the sum of 1 through m of g(k), then the average number of ways that numbers can be written as the sum of two squares is f(n)/n, that is, we seek to prove that for large N
f(N)/N = πConsider taking some value k, for each way it can be expressed as the sum of two squares, we can write x2+y2=k for some (x,y), and for each pair (x,y) that solves x2+y2=k, we have a way to write k as the sum of two squares. That is, for each point in the plane with integer coordinates on a circle of radius √k, we have a way to express k as the sum of two squares. So we can say that g(k) is the number of integer points on a circle of radius √k. This means that we can say that f(m) is equal to the number of integer points that lie on a circle of radius equal to root some integer less than or equal to m. But every point with integer coordinates lies on a circle of radius equal to the square root of some integer (specifically (x,y) lies on a circle of radius √(x2+y2)) so f(m) is simply equal to the number of integer points that lie inside a circle of radius √m. So, how do we calculate the number of integer points that lie inside a circle of radius R? Suppose for each such point, we shade the 1x1 square that is to its lower left. Then the total area shaded is equal to the number of points, and we can easily see that the shaded area is approximately equal to the area of the circle of radius R. I always hate using the term "approximately" in a non-technical sense though, so lets be technical about it. It is easy to see that the shaded area equal to the circle area up to an error term that is, at most, the area of a strip with width √2 that runs around the circumference of the circle. In reality the error will be much smaller than this, we tend to have missing area in the upper right parts and extra area in the lower left parts and these will typically cancel pretty well, but nevermind that, I want an easy upper bound on the size of the error term. Since the shaded area is known to equal f(m) and the area of a circle of radius √m is πm, we can see that
f(m)=πm+C√mwhere C√m is our error term, C can be positive or negative, and can depend on m, but its absolute value is bounded by a constant (the constant being 2π√2, for those paying attention). So finally we can see that
f(N)/N=π+C/√Nfor large enough N to consider the second term small, the average number of ways the first N numbers can be written as the sum of two squares is π.
Sums Of Squares
New puzzle time? New puzzle time.
I first found this one at Futility Closet:
Consider the number of ways a positive integer can be written as the sum of two integer squares, for example, 8 can be written four ways, m2+n2 as (m,n)=(2,2), (-2,2), (2,-2), (2,2), while 5 can be done eight ways (2,1), (-2,1), (2,-1), (-2,-1), (1,2), (-1,2), (1,-2), (-1,-2), and 7 cannot be written as the sum of two squares at all. Over a very large collection of integers from 1 to N, the average number of ways a number can be written as the sum of two squares approaches π, why should this be?Just in case we are using different browsers, π is supposed to render as pi, it looks a bit funny in firefox. The puzzle is a bit of a weird one, being something of a proof more than anything, but there is a proof that can be understood only using high school math, so I don't think its too tricky. There are probably more convoluted proofs, of course, being that π is involved.
Odd Coins
So, apparently I just stop blogging when I have a semi-academic job, but don't have an office to go with it. Anyway, its about time for the solution to the coin puzzle from last time.
So, I suspect that somebody who works with the Fibonacci numbers alot will not really have much of a problem with this puzzle, there are a reasonable number of relationships the Fibonacci numbers obey that make the puzzle quite straightforward. First of all, I will give my definition of the Fibonacci numbers for the purpose of this puzzle:
f1=1 f2=2 fk=fk-1+fk-2I call this "my definition for the purpose of this puzzle" because nobody would ever normally start the Fibonacci numbers off with 1 and 2, 1 and 1 is most common, and 0 and 1 sometimes, but 1 and 2 is being chosen for this so that there are no repeats in the sequence {fk} for k>0. Next, I will derive an identity that will be needed for the solution:
2fk=fk+fk-1+fk-2 =fk+1+fk-2A short derivation, but an important one. Alright, now suppose the set of Fibonacci numbers is not a greedy set. Then there is a number C such that C can be expressed as a sum of K Fibonacci numbers {fi1,fi2,...fiK} and the greedy algorithm uses at least K+1 such numbers. We will assume that C is chosen to be the smallest such number (if any exist, there must be a smallest one). Naturally C is not one of the fn, so let M be the largest number such that fM<C. I claim that fM is not in the list {fi1,fi2,...fiK}. If it were, then the greedy algorithm would use the coin fM and then optimize C-fM. However, the list {fi1,fi2,...fiK} adds to C and so if it contains fM then C-fM can be expressed using K-1 Fibonacci numbers, but the greedy algorithm would be able to optimize this, as C was the smallest counterexample. Alright, so we have proven that the list {fi1,fi2,...fiK} does not contain fM. It is also obvious that it does not contain two consecutive Fibonacci numbers (if it did, we could make it more efficient). Finally, it can be made to not contain the same number twice, for if it did we could use our earlier identity to replace 2fk with fk+1 and fk-2. I claim that a list of Fibonacci numbers fj with J less than M with no consecutive numbers and no repeats cannot add to larger than fM. This can be proven as follows:
fM=fM-1+fM-2 =fM-1+fM-3+fM-4 =fM-1+fM-3+fM-5+fM-6Continue on this logic, until you get down to f1. We see that our list {fi1,fi2,...fiK} cannot add to larger than fM, but C was larger than fM, so we have a contradiction, proving there is no smallest counterexample. Thats all I got for now, I might post the full solution to the greedy sets of the form {1,a,b} next time, or I might just move on to a new puzzle, we will see.
Greedy Coins
Time for a new puzzle. As seems to be the constant state these days, I am running out of puzzles and as such I am digging up all the weird ones I remember. Actually, I rather enjoyed this one, but it is more mathematical than most of my puzzles. I first learned this one from Bart:
Consider the problem of making change for a certian amount of money, given a set of coins that you can select from. You have a target number x, and you wish to construct x by using elements from a set S (so S could be the set {1,5,10,25} for example). In particular we wish to reach the target number using a few coins as possible, so making 23 with 10+10+1+1+1 is considered more optimal than using 10+5+5+1+1+1. This is known as the change-making problem. There are plenty of good solutions for the change-making problem, but let us consider a special style of solution, which is known as the "greedy algorithm". This algorithm is to always take the largest available coin that is smaller than your target number and the reduce the target number by that amount. As an example of this algorithm, lets try to make 28 is the set {1,5,10}, we first take 10, now we want to reach 18, so we take another 10, now we want to reach 8 so we take 5 and finally to get 3 we use 1 three times, thus the algorithm gives us the solution 10+10+5+1+1+1, which you can convince yourself is optimal for this case. For another example we can consider the set {1,4,5} and try to reach target number 8. The greedy algorithm gives us 5+1+1+1, but we can see that 4+4 is a better solution, so in this case the greedy algorithm does not give us the optimal solution. With some sets of numbers, such as {1,5,10,25} the greedy algorithm will always give the optimal solution, but with others such as {1,4,5} it will not (lets not ask what happens if the number 1 is not in our coin set). With some sets, like reaching 4 with {1,2,3} the greedy algorithm gives an optimal solution, but not the only solution, so 4=1+3 but also 4=2+2. We will call a set of natural numbers "greedy" if the greedy algorithm always gives an optimal solution for the change-making problem. Consider the set of numbers that occur in the Fibonacci sequence, call this set F. The puzzle is prove that F is a greedy set.If you don't know what the Fibonacci sequence is then I am astounded that you are even reading this blog, but anyway, it should be pretty easy to look it up on the internets somewhere. One can ask the much more general question of "classify all greedy sets", but that is actually really hard and if you can do that, I suggest you publish. You can try to solve out the classification of all greedy sets of the form {1,a,b} though, that actually has a somewhat nice answer.
Weird Answer
Alright, time to post the solution to the limit from last time. To start with, let us consider the following function
f(x)=sin(2πx)for our puzzle, we have to worry about x=N!e. Clearly f is periodic in x with period 1, and so for this function only the non-integer part of x matters. That is f(2.7)=f(0.7), f(5749.276)=f(0.276), and f(x+N)=f(x) for integer N. Now consider
limN->∞f(N!r)for N going to infinity along the integers and r any rational number. Since r is rational, r=p/q for p and q integers. Once N is greater than q we will have that N!r will always be an integer, so the limit will necessarily be zero. This proves that
limN->∞f(N!(e+r))=limN->∞f(N!e+N!r) =limN->∞f(N!e)Proving the statement I made last time. Of course, since e is irrational, we must be a bit more careful. To proceed, we must use the following formula for e
e=Σ1/k!Summing k from 0 to infinity. If you don't recall this formula, you can derive it from the taylor expansion for ex and sub in x=1. Anyway, so N!e then looks like
N!e=ΣN!/k! =N!/0!+N!/1!+N!/2!+...N!/N!+N!/(N+1)!+N!/(N+2)!+... =M+1/(N+1)+1/(N+1)(N+2)+...For M being some integer. So, we must have
f(N!e)=f(M+1/(N+1)+1/(N+1)(N+2)+...) =f(1/(N+1)+O(1/N2))The O(1/N2) means terms like 1/N2 or smaller (as N is going to be large). We know that sin(x+O(x2))=x+O(x2) for small x though, so we must have
f(N!e)=2π/(N+1)+O(1/N2)Which means that
limN->∞ N sin(N!2πe) =limN->∞ 2πN/(N+1)+O(1/N2) =2πEnding the problem. Essentially the proof comes down to the fact that N!e gets arbitrarily close to integer values for large N (as we have seen, it gets within 1/N of an integer). Actually, if you try to do this limit on any computer it almost certainly won't work, as the computers approximate value of e will explode terribly when multiplied by N!. I recall that wolfram alpha can't handle this limit (or at least I have never found a way to coax it into getting this limit).
Weird Limit
I guess its new puzzle time. I do have a new puzzle to post, but I haven't fully solved it out yet, and I don't like posting puzzles I don't have full solutions to, since I'm worried it will take longer than I expect. Instead I'm going to post a limit I saw a few years ago that I thought was really neat. Thats right, its time for math. Anyway,
where the limit of N is taken along integer values (which is why I can use factorial instead of gamma or something). Its interesting as the coefficient out front is just going to diverge linearly, and the argument of the sin function is just seemingly random numbers, so it should be random numbers times a huge number, its actually amazing that the limit exists at all.
Anyway, the limit does exist as a nonzero real number, I'll show it next time, but it turns out it converges by the magic of e. Well, not quite just e, if you replaced e by e+r with any rational number r, this limit would still exist (that is a bit of a hint for you).
limN->∞ N sin(N!2πe)
where the limit of N is taken along integer values (which is why I can use factorial instead of gamma or something). Its interesting as the coefficient out front is just going to diverge linearly, and the argument of the sin function is just seemingly random numbers, so it should be random numbers times a huge number, its actually amazing that the limit exists at all.
Anyway, the limit does exist as a nonzero real number, I'll show it next time, but it turns out it converges by the magic of e. Well, not quite just e, if you replaced e by e+r with any rational number r, this limit would still exist (that is a bit of a hint for you).
Circles In A Line
Been a month since I put up the circles puzzle last time, I guess its time to solve it out now.
Its easy to see that we lose nothing by just having all the circles in a line along the x-axis (say) and we will specify a circle by giving the distance between its center and the previous circle, we will call this di. Circle i will also have radius ri, and we know r0=1 from the setup (I'm numbering the circles 0 to 15 now, cause thats how I roll). The goal is to maximize d1+d2+d3+...+d15+r15. Given d1, r1 gets specified, by d12+r12=1 (if this isn't clear to you, draw circles 0 and 1 and do some trig, its pretty simple). We can similarly see that di2+ri2=ri-12. So,
For some sense of completeness, we might as well add on a d16 which equals r15, and r16 is zero. So we have to maximize Σdi while holding Σdi2=1. You probably just know this max is achived when the di are all equal, but lets solve it by Lagrange multipliers, because I haven't done that in years.
The maximum of f(xi), subject to g(xi)=K will occur at dg/dxi=λdf/dxi for each i. So, if f is the sum of x's and g is the sum of x2's, we get xi=λ/2, they are all the same, good.
Anwyay, so for our problem, this means that di=A, and since the sum of their squares is 1, they much each be 1/√16=1/4. Summing di to find the answer, we get 16/4, which is 4 for the maximum distance.
Its pretty easy to see that with N circles the answer will simply be √N, surprisingly fast asymptotically, but there you go.
When I told this problem to Sean, he suggested attempting the greedy algorithm. That is, just place the second circle to solve the two circle problem, and place the third circle to solve the local problem (which is a two circle problem again, but scaled down in size) and so on. Looking at the answer we got, its clear that the greedy algorithm won't work to give the optimal answer, but lets see what it does give.
The circles will again have radii given by ri and the centers will be spaced a distance di from eachother. r0=1 of course, and d1 will be such that d1+r1 is maximized while d12+r12=1. So, we have d1=1/√2=r1. Next d2 will be such that d2+r2 is maximized while d22+r22=1/2. So, we have d2=1/√22=r2. Next d3 will be such that d3+r3 is maximized while d32+r32=1/22. So, we have d3=1/√23=r3.
Clearly we will get di=1/√2i=ri, and the sum of the di will be the sum of 1/√2i. The infinite sum of ai starting at 1 is a/(1-a), so when a=1/√2 we get 1/(√2-1) which is the same as 1+√2, so about 2.41. The greedy method asymptotes to a constant, neat.
Anyway, thats all I got.
Its easy to see that we lose nothing by just having all the circles in a line along the x-axis (say) and we will specify a circle by giving the distance between its center and the previous circle, we will call this di. Circle i will also have radius ri, and we know r0=1 from the setup (I'm numbering the circles 0 to 15 now, cause thats how I roll). The goal is to maximize d1+d2+d3+...+d15+r15. Given d1, r1 gets specified, by d12+r12=1 (if this isn't clear to you, draw circles 0 and 1 and do some trig, its pretty simple). We can similarly see that di2+ri2=ri-12. So,
d12+r12=1And so on, until we have
d12+d22+r22=1
d12+d22+d32+r32=1
Σdi2+r152=1As our restriction.
For some sense of completeness, we might as well add on a d16 which equals r15, and r16 is zero. So we have to maximize Σdi while holding Σdi2=1. You probably just know this max is achived when the di are all equal, but lets solve it by Lagrange multipliers, because I haven't done that in years.
The maximum of f(xi), subject to g(xi)=K will occur at dg/dxi=λdf/dxi for each i. So, if f is the sum of x's and g is the sum of x2's, we get xi=λ/2, they are all the same, good.
Anwyay, so for our problem, this means that di=A, and since the sum of their squares is 1, they much each be 1/√16=1/4. Summing di to find the answer, we get 16/4, which is 4 for the maximum distance.
Its pretty easy to see that with N circles the answer will simply be √N, surprisingly fast asymptotically, but there you go.
When I told this problem to Sean, he suggested attempting the greedy algorithm. That is, just place the second circle to solve the two circle problem, and place the third circle to solve the local problem (which is a two circle problem again, but scaled down in size) and so on. Looking at the answer we got, its clear that the greedy algorithm won't work to give the optimal answer, but lets see what it does give.
The circles will again have radii given by ri and the centers will be spaced a distance di from eachother. r0=1 of course, and d1 will be such that d1+r1 is maximized while d12+r12=1. So, we have d1=1/√2=r1. Next d2 will be such that d2+r2 is maximized while d22+r22=1/2. So, we have d2=1/√22=r2. Next d3 will be such that d3+r3 is maximized while d32+r32=1/22. So, we have d3=1/√23=r3.
Clearly we will get di=1/√2i=ri, and the sum of the di will be the sum of 1/√2i. The infinite sum of ai starting at 1 is a/(1-a), so when a=1/√2 we get 1/(√2-1) which is the same as 1+√2, so about 2.41. The greedy method asymptotes to a constant, neat.
Anyway, thats all I got.
Circles On Circles
New puzzle time? I guess it must be, its certainly not new solution time. Though I think I still have left that cats and dogs game hanging, one day I'll have to revisit that. Anyway, I found this puzzle on the xkcd forums, but its initially from the cofoundry:
There are 16 overlapping circles in a plane with the following proerties:By "overlapping circles" I really mean that circle N can share some interior points with circle N+1, it just helps to say it that way to imagine the setup. If you have forgotten your grade school geometry you may want to look up what a chord of a circle is on wikipedia or something.
Circle 1 has radius 1
The diameter of circle 2 is a chord of circle 1
The diameter of circle 3 is a chord of circle 2
...
The diameter of circle 16 is a chord of circle 15
What is the maximum distance from a point in circle 16 to the center of circle 1?
Going In Circles
Alright, some time ago I promised to do more on the dots on a line puzzle, so I guess I'll do that now.
On the puzzle page over at cut-the-knot, they had a few writeups of possible ways to arrive at the solution. They varied in their degree of rigour, but they certainly were all more elegant than my method. One in particular led me to examine a few other things about the puzzle (that I honestly do not understand the implications of), and I will go over them here.
This solution was put forward by Stuart Anderson, and it beings by assuming that the dots do not necessarily follow a uniform distribution. Suppose x is the length of an interval between adjacent points, and let f(x)dx be the probability that a particular interval has length between x and x+dx. F(x) will be the cumulative probability distribution, so F'(x)=f(x) and F(x) ranges from 0 to 1, as x ranges from 0 to 1.
We will call an interval "small" if it is smaller than both its neighbours, "large" if it is larger than both its neighbours, and "medium" otherwise. Intervals that are small get painted twice, and medium ones get painted once, while large ones are unpainted. Lets try to find out how many of each region we have and how large each type is. Suppose we have an interval with size x, that occurs with chance f(x)dx, and its left hand neighbour will be smaller than it with chance F(x) (F(x) being the cumulative distribution function, it is the integral of f(y) from 0 to x). Similarly, the right hand neighbour will be smaller with chance F(x), so the total chance that we have a large region is
Where we have used f(x)=F'(x). The limits of integration are 0 to 1, since that is what F ranges over. Thus we get 1/3 for the chance an interval is large. A similar calculation shows that you also get 1/3 for small and medium intervals. This means that if an interval is selected at random, it is equally likely to be small, medium, or large, and this is independent of the probability distribution that the points are selected with.
The fact that P(small)=P(large) is somewhat obvious if you consider doing a plot of interval lengths. Small intervals will be a local minimum of the plot, while large intervals will be local maxima. For any two local minima, there must be a local maxima in between and vice-versa, so the number of small intervals must be the same as the number of large intervals (well, within 1 anyway), so in the infinite limit they will have the same probability. It is not clear why medium intervals would be equally likely, but there is probably some underlying reason.
Moving on, the expected length of a large interval is given by
which we can integrate by parts. Let u=x and v=F(x)3-1, so then we have
v was chosen so that the first term would vanish at the endpoints, so that last integral gives us the average size of a large interval.
One can do a similar calculation for small and medium intervals, and the expressions are only slightly uglier, but this is as far as we can go without giving a specific form to the function F(x).
To proceed, assume that we have distributed the N dots on the line, and we scale things up by a factor of N, so there is on average 1 dot per unit length, then one can show that the function F(x) will tend to 1-e-x for large N (I cannot really prove this, it makes sense, but people who wrote the solutions quoted at cut-the-knot took this result as obvious, so I suspect it is some elementary thing that I simply am unfamiliar with (to be honest, its why I found their solutions unconvincing and did my own awful one, I couldn't get past this point)).
Anyway, using that F for the integral, one gets that the average size of a large interval is 11/18. This must be multiplied by N to account for the fact that there are N intervals, but then divided by N because we scaled everything up by a factor of N.
A similar calculation gives that the average size of a medium interval is 5/18 and small intervals are 2/18.
So the ratio of small:medium:large intervals is 2:5:11. the small+medium intervals account for (2+5)/18 of the total length, giving the answer to the original problem. Note that if the small intervals are counted twice, then the total amount painted is (2+2+5)/18, which is exactly 1/2. I have not yet found a way to explain why this answer would be so clean.
When I first found out about the fact that small, medium, and large segments all appear with equal probability, I was inspired to try a slightly different problem. Suppose we take the unit circle and place 3 points on it, that will divide the circle into 3 parts, one small, one large, and one medium. On average, what is the relative sizes of these three parts?
This is simple enough to calculate, let the points be located at 0, x and y where x and y vary from 0 to 1 (1 being the full circle). By the symmetry of the problem, lets assume that x is smaller than y, and lets assume that the interval between 0 and x is the smallest. So y varies from 2x to 1-x and x varies from 0 to 1/3. The average length can be found from the integral
over the regions specified. We also need to divide by the integral of 1 over that same region, to divide by the probability that the region is actually a small one, essentially just normalizing properly.
Naturally, you can do a similar calculation for the largest interval and for the other one. In the end, you get the answers 2/18, 5/18, 11/18, unsurprising given that I chose to bring this whole thing up. So one does not need to work in the infinite case, somehow only using 3 points and 3 intervals gives the correct answer, but I have no idea why.
On the puzzle page over at cut-the-knot, they had a few writeups of possible ways to arrive at the solution. They varied in their degree of rigour, but they certainly were all more elegant than my method. One in particular led me to examine a few other things about the puzzle (that I honestly do not understand the implications of), and I will go over them here.
This solution was put forward by Stuart Anderson, and it beings by assuming that the dots do not necessarily follow a uniform distribution. Suppose x is the length of an interval between adjacent points, and let f(x)dx be the probability that a particular interval has length between x and x+dx. F(x) will be the cumulative probability distribution, so F'(x)=f(x) and F(x) ranges from 0 to 1, as x ranges from 0 to 1.
We will call an interval "small" if it is smaller than both its neighbours, "large" if it is larger than both its neighbours, and "medium" otherwise. Intervals that are small get painted twice, and medium ones get painted once, while large ones are unpainted. Lets try to find out how many of each region we have and how large each type is. Suppose we have an interval with size x, that occurs with chance f(x)dx, and its left hand neighbour will be smaller than it with chance F(x) (F(x) being the cumulative distribution function, it is the integral of f(y) from 0 to x). Similarly, the right hand neighbour will be smaller with chance F(x), so the total chance that we have a large region is
∫F(x) F(x) f(x) dx
=∫F(x)2 dF
Where we have used f(x)=F'(x). The limits of integration are 0 to 1, since that is what F ranges over. Thus we get 1/3 for the chance an interval is large. A similar calculation shows that you also get 1/3 for small and medium intervals. This means that if an interval is selected at random, it is equally likely to be small, medium, or large, and this is independent of the probability distribution that the points are selected with.
The fact that P(small)=P(large) is somewhat obvious if you consider doing a plot of interval lengths. Small intervals will be a local minimum of the plot, while large intervals will be local maxima. For any two local minima, there must be a local maxima in between and vice-versa, so the number of small intervals must be the same as the number of large intervals (well, within 1 anyway), so in the infinite limit they will have the same probability. It is not clear why medium intervals would be equally likely, but there is probably some underlying reason.
Moving on, the expected length of a large interval is given by
∫x F(x) F(x) f(x) dx
which we can integrate by parts. Let u=x and v=F(x)3-1, so then we have
x(F(x)3-1)+∫(1-F(x)3) dx
v was chosen so that the first term would vanish at the endpoints, so that last integral gives us the average size of a large interval.
One can do a similar calculation for small and medium intervals, and the expressions are only slightly uglier, but this is as far as we can go without giving a specific form to the function F(x).
To proceed, assume that we have distributed the N dots on the line, and we scale things up by a factor of N, so there is on average 1 dot per unit length, then one can show that the function F(x) will tend to 1-e-x for large N (I cannot really prove this, it makes sense, but people who wrote the solutions quoted at cut-the-knot took this result as obvious, so I suspect it is some elementary thing that I simply am unfamiliar with (to be honest, its why I found their solutions unconvincing and did my own awful one, I couldn't get past this point)).
Anyway, using that F for the integral, one gets that the average size of a large interval is 11/18. This must be multiplied by N to account for the fact that there are N intervals, but then divided by N because we scaled everything up by a factor of N.
A similar calculation gives that the average size of a medium interval is 5/18 and small intervals are 2/18.
So the ratio of small:medium:large intervals is 2:5:11. the small+medium intervals account for (2+5)/18 of the total length, giving the answer to the original problem. Note that if the small intervals are counted twice, then the total amount painted is (2+2+5)/18, which is exactly 1/2. I have not yet found a way to explain why this answer would be so clean.
When I first found out about the fact that small, medium, and large segments all appear with equal probability, I was inspired to try a slightly different problem. Suppose we take the unit circle and place 3 points on it, that will divide the circle into 3 parts, one small, one large, and one medium. On average, what is the relative sizes of these three parts?
This is simple enough to calculate, let the points be located at 0, x and y where x and y vary from 0 to 1 (1 being the full circle). By the symmetry of the problem, lets assume that x is smaller than y, and lets assume that the interval between 0 and x is the smallest. So y varies from 2x to 1-x and x varies from 0 to 1/3. The average length can be found from the integral
∫∫x dy dx
over the regions specified. We also need to divide by the integral of 1 over that same region, to divide by the probability that the region is actually a small one, essentially just normalizing properly.
Naturally, you can do a similar calculation for the largest interval and for the other one. In the end, you get the answers 2/18, 5/18, 11/18, unsurprising given that I chose to bring this whole thing up. So one does not need to work in the infinite case, somehow only using 3 points and 3 intervals gives the correct answer, but I have no idea why.
Birds On A Wire
Alright, time to post the solution to the dots on a line puzzle from last time. First I suppose I'll link directly the cut-the-knot page with the puzzle. He has a cool little applet thing there you can use to simulate the problem and try to guess the solution yourself, and he also has links to where people have written up derivations, one of which I will regurgitate on here later because I found it to be so interesting.
For today though, I am simply going to post the solution to the problem as Matt and I initially solved it. First, I must solve a very simple problem that gives us a technique that will be needed later. Consider the following problem:
First, let us try to solve this for N=2. We can see that we simply must solve the integral
integrated over [0,1]x[0,1], and min(,) is the minimum function. Clearly min(x,y)=min(y,x) so we can instead integrate over the "lower half triangle" and double our answer. So, instead integrate x in [0,1] and y in [0,x] in
the 2 is because we are only covering half the area we should be covering, and min(x,y) has been replaced by y, because x>y now. The integral is pretty simple to do, and gives the answer 1/3.
Now in the general N case we must consider we have a collection of N points {x[1],x[2],x[3]...,x[N]}, and integrate
As before, we order them x[1]>x[2]>x[3]...>x[N], so the min function always returns x[N], and we must integrate x[1] in [0,1], x[2] in [0,x[1]], x[3] in [0,x[2]] and so on. We must also find the prefactor, which is one over the area of the triangle we are integrating. Integrating the function 1 over the region of integration, we find the prefactor must be N!. So we must integrate
over our triangular region. The final answer comes out to be 1/(N+1), sort of neat, but anyway I just wanted to demonstrate the technique so it is less confusing later.
Back to the problem at hand. We have N points {x[1],x[2],x[3]...,x[N]}, and we will order them as x[1]>x[2]>x[3]...>x[N]. Let us define
so d[i] is the size of the ith region, and this i runs from 1 to N-1.
Next, we will define S[i] to be equal to d[i] if the ith region is shaded, and S[i] will be zero if it is not. The answer we seek is
Integrated over all the x[i] positions, and j summed from 1 to N-1 to add up all the shaded regions.
S[i] will be nonzero (and equal to d[i]) in one of two conditions:
That is, if d[i+1] is greater than d[i] or if d[i-1] is greater than d[i], d[i] will get shaded in.
With calculating probabilities, whenever you have to find the chance that A or B happens, it is often easier to find the chance that neither happened and take one minus that. Similarly here, rather than integrate whenever 1) or 2) happens, it is easier to find the situation of neither of them happening. Let is define q[i] as d[i]-S[i], so q[i] represents the unshaded regions, it is equal to d[i] when S[i]=0 and it is zero when S[i]=d[i]. Clearly then
We can of course move the sum outside of the integral, so we simply must calculate
for an arbitrary j and then we can sum it up and multiply by N!.
The integration has x[1] running from 0 to 1 and x[i] running from 0 to x[i-1]. q[j] is zero in some of this region and nonzero is other parts, let us identify exactly where q[j] is nonzero. It is exactly the negation of conditions 1) and 2) earlier, that is
This actually needs to break into a few cases, the first inequality is trivial if 2x[j+1] < x[j], since x[j+2] is always positive. The second case depends on whether x[j-1] is greater than or less than 3x[j] (because if x[j-1] is more than 3 times x[j] then the second inequality is made trivial by the fact that x[j+1] < x[j]).
So the integration region over dx[j-1] until dx[j+2] breaks up into many smaller pieces that one can cleanly write out with this information, but its fairly lengthy, so I'm not going to bother here. In this region, q[j]=d[j] so you simply integrate x[j]-x[j+1] in this region. This integral is most easily done in Maple (or whatever other math program you like) by first doing the integrals from dx[N] to dx[j+3] (the function is constant there and the integration region is simple) then doing the next four integrals carefully, then finishing it off integrating to x[1].
In the end, you get a somewhat awful function of N and j. You then sum j going from 1 to N-1 and multiply by N!. You will get something somewhat less awful, but a still terrible function of N. Finally, you must take the limit of N going to infinity (this step will be easy enough to do by hand, but by this point you already have Maple open anyway, and your spirit will have been far too crushed to do such a limit) and in then end you get 11/18. This was the unshaded region (the shaded region was 1-(the integral of q[j])) so the shaded region is given by 7/18.
Next time I'll go into a bit of the analysis by the other solutions found at the cut the knot page. One of them I found to be particularly interesting so I wanted to show it in detail, but I wanted to demonstrate my own horrible method first.
Also, I expect the date on this post will be confusing, I started writing it some time ago, but it took me more than a month to get around to finishing it.
For today though, I am simply going to post the solution to the problem as Matt and I initially solved it. First, I must solve a very simple problem that gives us a technique that will be needed later. Consider the following problem:
N numbers between 0 and 1 are selected uniformly at random. On average what is the value of the smallest one?
First, let us try to solve this for N=2. We can see that we simply must solve the integral
∫ min(x,y) dxdy
integrated over [0,1]x[0,1], and min(,) is the minimum function. Clearly min(x,y)=min(y,x) so we can instead integrate over the "lower half triangle" and double our answer. So, instead integrate x in [0,1] and y in [0,x] in
2∫ y dxdy
the 2 is because we are only covering half the area we should be covering, and min(x,y) has been replaced by y, because x>y now. The integral is pretty simple to do, and gives the answer 1/3.
Now in the general N case we must consider we have a collection of N points {x[1],x[2],x[3]...,x[N]}, and integrate
∫ min(x[1],x[2],x[3]...,x[N]) dx[1]dx[2]dx[3]...dx[N]
As before, we order them x[1]>x[2]>x[3]...>x[N], so the min function always returns x[N], and we must integrate x[1] in [0,1], x[2] in [0,x[1]], x[3] in [0,x[2]] and so on. We must also find the prefactor, which is one over the area of the triangle we are integrating. Integrating the function 1 over the region of integration, we find the prefactor must be N!. So we must integrate
N!∫ x[N]dx[1]dx[2]dx[3]...dx[N]
over our triangular region. The final answer comes out to be 1/(N+1), sort of neat, but anyway I just wanted to demonstrate the technique so it is less confusing later.
Back to the problem at hand. We have N points {x[1],x[2],x[3]...,x[N]}, and we will order them as x[1]>x[2]>x[3]...>x[N]. Let us define
d[i]=x[i]-x[i+1]
so d[i] is the size of the ith region, and this i runs from 1 to N-1.
Next, we will define S[i] to be equal to d[i] if the ith region is shaded, and S[i] will be zero if it is not. The answer we seek is
S=N!∫ Σ S[j] dx[i]
Integrated over all the x[i] positions, and j summed from 1 to N-1 to add up all the shaded regions.
S[i] will be nonzero (and equal to d[i]) in one of two conditions:
1) x[i+1]-x[i+2] > x[i]-x[i+1]
2) x[i-1]-x[i] > x[i]-x[i+1]
That is, if d[i+1] is greater than d[i] or if d[i-1] is greater than d[i], d[i] will get shaded in.
With calculating probabilities, whenever you have to find the chance that A or B happens, it is often easier to find the chance that neither happened and take one minus that. Similarly here, rather than integrate whenever 1) or 2) happens, it is easier to find the situation of neither of them happening. Let is define q[i] as d[i]-S[i], so q[i] represents the unshaded regions, it is equal to d[i] when S[i]=0 and it is zero when S[i]=d[i]. Clearly then
S=N!∫ Σ S[j] dx[i]
=1 - N!∫ Σ q[j] dx[i]
We can of course move the sum outside of the integral, so we simply must calculate
∫ q[j] dx[i]
for an arbitrary j and then we can sum it up and multiply by N!.
The integration has x[1] running from 0 to 1 and x[i] running from 0 to x[i-1]. q[j] is zero in some of this region and nonzero is other parts, let us identify exactly where q[j] is nonzero. It is exactly the negation of conditions 1) and 2) earlier, that is
1) x[j+2] > 2x[j+1]-x[j]
2) x[j+1] < x[j-1]-2x[j]
This actually needs to break into a few cases, the first inequality is trivial if 2x[j+1] < x[j], since x[j+2] is always positive. The second case depends on whether x[j-1] is greater than or less than 3x[j] (because if x[j-1] is more than 3 times x[j] then the second inequality is made trivial by the fact that x[j+1] < x[j]).
So the integration region over dx[j-1] until dx[j+2] breaks up into many smaller pieces that one can cleanly write out with this information, but its fairly lengthy, so I'm not going to bother here. In this region, q[j]=d[j] so you simply integrate x[j]-x[j+1] in this region. This integral is most easily done in Maple (or whatever other math program you like) by first doing the integrals from dx[N] to dx[j+3] (the function is constant there and the integration region is simple) then doing the next four integrals carefully, then finishing it off integrating to x[1].
In the end, you get a somewhat awful function of N and j. You then sum j going from 1 to N-1 and multiply by N!. You will get something somewhat less awful, but a still terrible function of N. Finally, you must take the limit of N going to infinity (this step will be easy enough to do by hand, but by this point you already have Maple open anyway, and your spirit will have been far too crushed to do such a limit) and in then end you get 11/18. This was the unshaded region (the shaded region was 1-(the integral of q[j])) so the shaded region is given by 7/18.
Next time I'll go into a bit of the analysis by the other solutions found at the cut the knot page. One of them I found to be particularly interesting so I wanted to show it in detail, but I wanted to demonstrate my own horrible method first.
Also, I expect the date on this post will be confusing, I started writing it some time ago, but it took me more than a month to get around to finishing it.
Dots On A Line
Alright, I think I've finally run out of puzzles if I'm going to post this one. It is a rather crazy one that I solved with Matt many years ago and I absolutely love the answer to it. Sadly there isn't really a clean way to solve the puzzle, you have to do it the hard way, and its really not very illustrative of why the final answer is what it is, but thats just life. I initially found this puzzle at cut the knot:
Terrible, I know. To clarify, suppose we had N=5 and selected the points 1/10, 2/10, 4/10, 7/10 and 8/10. Then from 1/10 we would color to 2/10, from 2/10 we would color back to 1/10 (not that that does anything), from 4/10 we color back to 2/10, from 7/10 we color to 8/10 and from 8/10 we color back to 7/10 (again does nothing). Then the colored region would be [1/10,4/10] ∪ [7/10,8/10] so in total 4/10 of the interval was colored in, in this case.
Consider the unit interval between 0 and 1. Select N points randomly on that interval (random with uniform distribution). From each selected point "color in" the part of the interval between it and the closest neighboring point. In the limit as N goes to infinity, what fraction of the interval is colored in on average?
Terrible, I know. To clarify, suppose we had N=5 and selected the points 1/10, 2/10, 4/10, 7/10 and 8/10. Then from 1/10 we would color to 2/10, from 2/10 we would color back to 1/10 (not that that does anything), from 4/10 we color back to 2/10, from 7/10 we color to 8/10 and from 8/10 we color back to 7/10 (again does nothing). Then the colored region would be [1/10,4/10] ∪ [7/10,8/10] so in total 4/10 of the interval was colored in, in this case.
Cards and Birthdays
Time for an aside from puzzles that I got from "Games People Don't Play", and an aside from puzzles in general. This post is going to be about the birthday paradox and human intuition on probability.
You are probably familiar with the birthday paradox, but I will state it anyway, just to be clear. The paradox (as with most "paradoxes" it isn't really a paradox, but just something unexpected) is the answer to the question:
If you ask this question of an average person, they will probably state something like 100 or so. If they have some basic math behind them, they might guess 365/2, so about 180. The actual answer is around 20 (i'll derive it later). The basic misunderstanding comes from the difference from the question posed and the following question:
Note the difference, in the first question you just needed any two people to share a birthday, in the second question you needed somebody to land on a specific birthday. This results in a big difference since in the second case each person has a 1/365 chance of having your birthday, but in the first one each person has a k/365 chance of landing on somebodys birthday, where k is the number of people in the room before them.
I always say that humans have no good sense of probability, evolution never gave us a need to understand things like the Monty Hall scenario on an intuitive level. We also have a bad habit of noticing patterns where none exist, another byproduct of our evolutionary history. It is fortunate that we have developed the mathematical capabilities to handle probability for us, or science would never have gone anywhere.
The birthday paradox came up in a conversation I was having with my officemate the other day. He found a site that asked the question
Ignoring the fact that this question isn't really well-posed, it is something of an interesting question. The site basically gave an argument involving 52! (the number of ways to arrange the cards in the deck) and concluded the answer was "very small". Actually, I guess most of the post was on deriving 52! rather than the analysis of what to do with that number. My instinct was to agree with this conclusion, but then a part of my brain said "birthday paradox" and I had to wonder. The other part of me saying back "52! is like 1065" was a persuasive counterargument though. It basically depended on what the 20 was to the 365 in the birthday paradox... was it the logarithm? the root? just plain old linear with a coefficient? seems it is time to do the calculation.
Suppose we have a list of N outcomes of some experiment, all equally likely (N=365 for the birthday paradox, or N=52! for this card problem) and we check the experiment k times. What are the odds that we see the same result twice? Alternately, how large does k have to be for the probability we have seen the same result twice to be greater than P?
For the card situation lets assume that k is about 30000, this is an approximation of checking once a day for 80 years. So for approximation purposes, N>>k>>1. Now, what is the probability that none of our experiments ever get the same result? the chance that the first result is new is 1 (or N/N), the chance the second result is new is (N-1)/N, the chance the third one is new is (N-2)/N and so on up to the chance that the kth one is new is (N-k+1)/N. So the probability that we never see the same one twice is given by
We can use Stirling's approximation on this (since Stirling's approximation for n! is embarrassingly good by the time n is 10) to get
This is basically in a form that is ready to solve for the birthday paradox. Setting N=365 you find that for k=20, p=0.589 (remember p is the chance that none of them share a birthday) for k=21 p=0.556, for k=22 p=0.524 for k=23 p=0.492. So we see that at 23 people it is more than 50% that two of them share a birthday.
In the case of N=52! we need a few more approximations. I initially tried to use the fact that (1+x)m=1+mx for small x (since k/N is certainly small) but there is a problem with that. Writing out the next term it is actually (1+x)m=1+mx+m(m-1)x2/2, so if m is as big as x is small (specifically m2x2 is not negligible compared to mx) then this is not going to be valid. For our problem, x=k/N and m=k-N-1/2, so m2x2 is like k2 which is not small at all.
We can approximate the term (1-k/N)k-1/2 as 1-k(k-1/2)/N as long as the next term is small. The terms look like 1, k2/N and k4/N2, so the third term is small compared to the second as long as k2 is small compared to N. This is true for our case, but I'll come back to that later.
Given the approximation (1-k/N)k-1/2 = 1-k2/N, we have
We need to figure out what to do with (1-k/N)-N, which is a number very slightly smaller than 1 to a very large negative power, so its a bit unpredictable. If you remember your first year calculus course, you will see quickly what to do, the limit as m goes to infinity of (1+x/m)m is ex (this is sometimes a definition of the exponential function). So we may approximate (1-k/N)-N as ek, giving us
Thus, the probability that you see the same event twice is approximately k2/N. For k=30000 and N=52! this is about 10-59, so we can confidently say it won't happen. Turns out the human intuition is correct in this case, the birthday paradox won't overcome crazy scenarios like 52!.
Asking the other question of "how large does k have to be to achieve some fixed P" like the birthday paradox's 50%, the answer is a bit funny. You find that to achieve a 50% chance of seeing the same result twice you get k=√(N/2), so it would appear that the birthday paradox goes as the square root on N, rather than the logarithm or something else. However, this is technically mistaken, since we needed k2 to be much smaller than N in our approximations, this answer is invalid. It is correct to say that the birthday paradox asymptotes to something similar to √N, since if it is much weaker than that (like logarithm or cube root or something) our approximations become good again and you get the answer of square root.
You are probably familiar with the birthday paradox, but I will state it anyway, just to be clear. The paradox (as with most "paradoxes" it isn't really a paradox, but just something unexpected) is the answer to the question:
How many people do you need to have in a room before there is a greater than 50% chance that two of them have the same birthday?
If you ask this question of an average person, they will probably state something like 100 or so. If they have some basic math behind them, they might guess 365/2, so about 180. The actual answer is around 20 (i'll derive it later). The basic misunderstanding comes from the difference from the question posed and the following question:
How many people do you need to have in a room before there is a greater than 50% chance that one of them shares your birthday?
Note the difference, in the first question you just needed any two people to share a birthday, in the second question you needed somebody to land on a specific birthday. This results in a big difference since in the second case each person has a 1/365 chance of having your birthday, but in the first one each person has a k/365 chance of landing on somebodys birthday, where k is the number of people in the room before them.
I always say that humans have no good sense of probability, evolution never gave us a need to understand things like the Monty Hall scenario on an intuitive level. We also have a bad habit of noticing patterns where none exist, another byproduct of our evolutionary history. It is fortunate that we have developed the mathematical capabilities to handle probability for us, or science would never have gone anywhere.
The birthday paradox came up in a conversation I was having with my officemate the other day. He found a site that asked the question
What are the odds that you will ever see a shuffled deck of cards in the same order twice in your life?
Ignoring the fact that this question isn't really well-posed, it is something of an interesting question. The site basically gave an argument involving 52! (the number of ways to arrange the cards in the deck) and concluded the answer was "very small". Actually, I guess most of the post was on deriving 52! rather than the analysis of what to do with that number. My instinct was to agree with this conclusion, but then a part of my brain said "birthday paradox" and I had to wonder. The other part of me saying back "52! is like 1065" was a persuasive counterargument though. It basically depended on what the 20 was to the 365 in the birthday paradox... was it the logarithm? the root? just plain old linear with a coefficient? seems it is time to do the calculation.
Suppose we have a list of N outcomes of some experiment, all equally likely (N=365 for the birthday paradox, or N=52! for this card problem) and we check the experiment k times. What are the odds that we see the same result twice? Alternately, how large does k have to be for the probability we have seen the same result twice to be greater than P?
For the card situation lets assume that k is about 30000, this is an approximation of checking once a day for 80 years. So for approximation purposes, N>>k>>1. Now, what is the probability that none of our experiments ever get the same result? the chance that the first result is new is 1 (or N/N), the chance the second result is new is (N-1)/N, the chance the third one is new is (N-2)/N and so on up to the chance that the kth one is new is (N-k+1)/N. So the probability that we never see the same one twice is given by
p=N!/((N-k)!Nk)
We can use Stirling's approximation on this (since Stirling's approximation for n! is embarrassingly good by the time n is 10) to get
p=NNe-N√(2π N)/((N-k)N-ke-N+k√(2π (N-k))Nk)
=(1-k/N)k-N-1/2e-k
This is basically in a form that is ready to solve for the birthday paradox. Setting N=365 you find that for k=20, p=0.589 (remember p is the chance that none of them share a birthday) for k=21 p=0.556, for k=22 p=0.524 for k=23 p=0.492. So we see that at 23 people it is more than 50% that two of them share a birthday.
In the case of N=52! we need a few more approximations. I initially tried to use the fact that (1+x)m=1+mx for small x (since k/N is certainly small) but there is a problem with that. Writing out the next term it is actually (1+x)m=1+mx+m(m-1)x2/2, so if m is as big as x is small (specifically m2x2 is not negligible compared to mx) then this is not going to be valid. For our problem, x=k/N and m=k-N-1/2, so m2x2 is like k2 which is not small at all.
We can approximate the term (1-k/N)k-1/2 as 1-k(k-1/2)/N as long as the next term is small. The terms look like 1, k2/N and k4/N2, so the third term is small compared to the second as long as k2 is small compared to N. This is true for our case, but I'll come back to that later.
Given the approximation (1-k/N)k-1/2 = 1-k2/N, we have
p=(1-k/N)-Ne-k(1-k2/N)
We need to figure out what to do with (1-k/N)-N, which is a number very slightly smaller than 1 to a very large negative power, so its a bit unpredictable. If you remember your first year calculus course, you will see quickly what to do, the limit as m goes to infinity of (1+x/m)m is ex (this is sometimes a definition of the exponential function). So we may approximate (1-k/N)-N as ek, giving us
p=1-k2/N
Thus, the probability that you see the same event twice is approximately k2/N. For k=30000 and N=52! this is about 10-59, so we can confidently say it won't happen. Turns out the human intuition is correct in this case, the birthday paradox won't overcome crazy scenarios like 52!.
Asking the other question of "how large does k have to be to achieve some fixed P" like the birthday paradox's 50%, the answer is a bit funny. You find that to achieve a 50% chance of seeing the same result twice you get k=√(N/2), so it would appear that the birthday paradox goes as the square root on N, rather than the logarithm or something else. However, this is technically mistaken, since we needed k2 to be much smaller than N in our approximations, this answer is invalid. It is correct to say that the birthday paradox asymptotes to something similar to √N, since if it is much weaker than that (like logarithm or cube root or something) our approximations become good again and you get the answer of square root.
Two Spheres In One
I suppose in recent posts involving the Axiom of Choice, I promised that I would give a proof of the Banach-Tarski paradox here. Not that anybody actually cares to read it, but the point of this blog is for me to feel smart while I rant about math, so I will do that.
First of all, we need to do a bit of group theory, because really all of the important math is just group theory. First, consider rotations of the three dimensional unit ball. These rotations form a non-commuting group, as you should know. Specifically, let A be a rotation of the sphere around the x-axis by 1 radian, and let B be a rotation of the sphere around the y-axis by 1 radian. A and B do not commute, and An and Bn are never equal to the identity (since there are 2π radians in the full rotation and 2kπ cannot ever be rational for rational k). It is also important to know that no string of A's and B's and their inverses (for example AB3A-2BA2) will ever be equal to the identity, unless the inverses cancel exactly (so A-2BB-1AB-1BA is the identity trivially, but ABA-1B-1 will not be).
Alright, now let us consider S to be the set of all strings involving A, A-1, B, B-1 with no term right next to its own inverse (so if there were to be any of those, cancel them). The empty string is also in S, to be the identity element. The strings in S can be arbitrarily long, though none of them are actually infinitely long. S clearly forms a group (the free group on two elements, to be specific).
Next, let us decompose S into 5 sets. S(A) will be elements of S staring with A, S(B) will be elements of S starting with B, S(A-1) and S(B-1) defined similarly, and S(e) has the last element, the empty string. Clearly S is the union of these 5 disjoint sets. Next, let us denote multiplication of an element x by a set P as the set you get when you multiply x by each element in P (so A times {A-1, BA, A, B-1} = {e, ABA, A2, AB-1} with e as the empty string).
Now, one can see that A times S(A-1) gives you every element of S, except the ones that start with A (as S(A-1) never has an element that starts A-1A, but it will have plenty that start A-1B , for example). Even the empty string is in A S(A-1). So we can say that S is the union of the disjoint sets S(A) and A S(A-1). Similarly, S is the union of the disjoint sets S(B) and B S(B-1).
Something a bit weird has happened here, since now we see S = S(A) ∪ S(B) ∪ S(A-1) ∪ S(B-1) ∪ S(e) = S(A) ∪ A S(A-1) = S(B) ∪ B S(B-1). Technically, this isn't a problem, as all of those sets (except S(e)) are infinitely large anyway, so there isn't a problem with S being one-to-one with some of its own subsets. Anyway, enough group theory, back to the sphere.
Now, consider a point on the surface of the sphere. Consider all the places you can reach from that point by using elements of S. There is an element that is A away, an element that is B away, an element that is ABA-3B2A away, and so on. These elements cannot cover the entire sphere (there are only countably many elements of S, and uncountably many places on the sphere to reach). We will consider an equivalence class on the sphere (as we always do when we are about to use the axiom of choice), two points on (or in) the sphere will be equivalent if you can move one into the other just by using rotations in S. Now use the Axiom of Choice to select one element from each equivalence class and put them into a set V. So for each point on the unit ball (the solid sphere, that is), there is exactly one element of V that can reach that point with exactly one of the rotations in S, and no two elements of V can reach eachother using rotations in S.
We will break the unit ball U up into 5 pieces. Places in U that can be reached from an element of V and a rotation in S(A) will be called U(A). Places in B that can be reached from an element of V and a rotation in S(A-1) will be called U(A-1). Similarly we define U(B), and U(B-1). U(e) is just V itself. So U is the union of the 5 disjoint sets U(A), U(B), U(A-1), U(B-1), and U(e).
Now is where the "magic" happens. Since we know that A-1S(A) is S(A) ∪ S(B) ∪ S(B-1), then A-1 applied to U(A) gives us U(A) ∪ U(B) ∪ U(B-1) ∪ U(e). Similarly, B-1 applied to U(B) gives us U(B) ∪ U(A) ∪ U(A-1) ∪ U(e). Thus, U(B) and U(B-1) can construct the entire unit ball, and U(A) and U(A-1) can also give us the entire unit ball.
I suppose I have dropped off U(e), as well as the issue of the fixed points under rotations A and B (specifically, the x-axis and the y-axis). I'm not going to handle those properly, but the main point has already been made anyway.
It may seem very strange that you can rotate U(A) and get U(A) unioned with other sets, but this actually can happen without the Axiom of Choice. Consider the unit circle on the 2-plane. Starting with the point (1,0) on the x-axis, consider the set of points that you hit by rotating that point counter-clockwise 1 radian at a time. So you get a countably infinite set of points, as that list never crosses itself, but does not cover the whole circle (it never hits the point at -1 radian, or the point at π radians, for example). Now rotate that set clockwise by 1 radian. The point at 1 radian moves to the point at 0, the point at 6 radians moves to the point at 5 radians, and the initial point at zero radians moves to the point at -1 radians. This new set covers all the points in the old set, and has one extra point also, very strange (actually, this is how you can handle the set U(e), you basically "rotate it out of existence" by combining it with U(A) or something). Cardinality and measure are not an issue here, as the set is countable with measure zero both before and after the rotation.
Anyway, thats really it for the proof. You can also extend the proof to take any finite sized object, cut it into finitely many pieces, and reassemble them into any other finite object (the standard example is to arrange a pea into the sun). Note that this does require three dimensions or more, as you need two non-commuting rotations.
First of all, we need to do a bit of group theory, because really all of the important math is just group theory. First, consider rotations of the three dimensional unit ball. These rotations form a non-commuting group, as you should know. Specifically, let A be a rotation of the sphere around the x-axis by 1 radian, and let B be a rotation of the sphere around the y-axis by 1 radian. A and B do not commute, and An and Bn are never equal to the identity (since there are 2π radians in the full rotation and 2kπ cannot ever be rational for rational k). It is also important to know that no string of A's and B's and their inverses (for example AB3A-2BA2) will ever be equal to the identity, unless the inverses cancel exactly (so A-2BB-1AB-1BA is the identity trivially, but ABA-1B-1 will not be).
Alright, now let us consider S to be the set of all strings involving A, A-1, B, B-1 with no term right next to its own inverse (so if there were to be any of those, cancel them). The empty string is also in S, to be the identity element. The strings in S can be arbitrarily long, though none of them are actually infinitely long. S clearly forms a group (the free group on two elements, to be specific).
Next, let us decompose S into 5 sets. S(A) will be elements of S staring with A, S(B) will be elements of S starting with B, S(A-1) and S(B-1) defined similarly, and S(e) has the last element, the empty string. Clearly S is the union of these 5 disjoint sets. Next, let us denote multiplication of an element x by a set P as the set you get when you multiply x by each element in P (so A times {A-1, BA, A, B-1} = {e, ABA, A2, AB-1} with e as the empty string).
Now, one can see that A times S(A-1) gives you every element of S, except the ones that start with A (as S(A-1) never has an element that starts A-1A, but it will have plenty that start A-1B , for example). Even the empty string is in A S(A-1). So we can say that S is the union of the disjoint sets S(A) and A S(A-1). Similarly, S is the union of the disjoint sets S(B) and B S(B-1).
Something a bit weird has happened here, since now we see S = S(A) ∪ S(B) ∪ S(A-1) ∪ S(B-1) ∪ S(e) = S(A) ∪ A S(A-1) = S(B) ∪ B S(B-1). Technically, this isn't a problem, as all of those sets (except S(e)) are infinitely large anyway, so there isn't a problem with S being one-to-one with some of its own subsets. Anyway, enough group theory, back to the sphere.
Now, consider a point on the surface of the sphere. Consider all the places you can reach from that point by using elements of S. There is an element that is A away, an element that is B away, an element that is ABA-3B2A away, and so on. These elements cannot cover the entire sphere (there are only countably many elements of S, and uncountably many places on the sphere to reach). We will consider an equivalence class on the sphere (as we always do when we are about to use the axiom of choice), two points on (or in) the sphere will be equivalent if you can move one into the other just by using rotations in S. Now use the Axiom of Choice to select one element from each equivalence class and put them into a set V. So for each point on the unit ball (the solid sphere, that is), there is exactly one element of V that can reach that point with exactly one of the rotations in S, and no two elements of V can reach eachother using rotations in S.
We will break the unit ball U up into 5 pieces. Places in U that can be reached from an element of V and a rotation in S(A) will be called U(A). Places in B that can be reached from an element of V and a rotation in S(A-1) will be called U(A-1). Similarly we define U(B), and U(B-1). U(e) is just V itself. So U is the union of the 5 disjoint sets U(A), U(B), U(A-1), U(B-1), and U(e).
Now is where the "magic" happens. Since we know that A-1S(A) is S(A) ∪ S(B) ∪ S(B-1), then A-1 applied to U(A) gives us U(A) ∪ U(B) ∪ U(B-1) ∪ U(e). Similarly, B-1 applied to U(B) gives us U(B) ∪ U(A) ∪ U(A-1) ∪ U(e). Thus, U(B) and U(B-1) can construct the entire unit ball, and U(A) and U(A-1) can also give us the entire unit ball.
I suppose I have dropped off U(e), as well as the issue of the fixed points under rotations A and B (specifically, the x-axis and the y-axis). I'm not going to handle those properly, but the main point has already been made anyway.
It may seem very strange that you can rotate U(A) and get U(A) unioned with other sets, but this actually can happen without the Axiom of Choice. Consider the unit circle on the 2-plane. Starting with the point (1,0) on the x-axis, consider the set of points that you hit by rotating that point counter-clockwise 1 radian at a time. So you get a countably infinite set of points, as that list never crosses itself, but does not cover the whole circle (it never hits the point at -1 radian, or the point at π radians, for example). Now rotate that set clockwise by 1 radian. The point at 1 radian moves to the point at 0, the point at 6 radians moves to the point at 5 radians, and the initial point at zero radians moves to the point at -1 radians. This new set covers all the points in the old set, and has one extra point also, very strange (actually, this is how you can handle the set U(e), you basically "rotate it out of existence" by combining it with U(A) or something). Cardinality and measure are not an issue here, as the set is countable with measure zero both before and after the rotation.
Anyway, thats really it for the proof. You can also extend the proof to take any finite sized object, cut it into finitely many pieces, and reassemble them into any other finite object (the standard example is to arrange a pea into the sun). Note that this does require three dimensions or more, as you need two non-commuting rotations.
Infinitely Powerful Logicians
Time to post the solution to my last problem involving the Axiom of Choice. First off, the mere existence of a solution to this problem should terrify you. The reason is that if only finitely many people are wrong, that means that there is a last person that is wrong. So, if you were to look at the guesses of the logicians, you would find that they have some right and some wrong for a while, but then suddenly there is a last person who is wrong and everybody after that is just magically right, in spite of the fact that those people had no special information. Somehow, they were able to use the infinite hats in front of them to deduce their own hat colour, even though it was independent.
It is also worth saying that in most problems like this, where everybody must guess simultaneously, you try to arrange the peoples guesses so that when something goes wrong, it goes maximally wrong. This is needed because each person on their own has a fixed probability of being wrong, so you simply try to make those fixed probabilities non-independent so that you minimize the chance that things go wrong.
In this problem, each person has a 50% chance of being wrong at the time they make their guess. This is a bit of a problem, as that means that on average half of the people will be wrong and there is very little one can do about it. Fortunately, the Axiom of Choice destroys usual notions of probability. It does this by creating sets of non-defined length. Simply put, length can be defined in terms of the probability that you were to pick an element of the set. Specifically, if you have a subset S of [0,1], and you were to pick an element of [0,1] at random, the probability that you would get an element of S would be L(S), the sets length. If the Axiom of Choice allows for sets with no length, it also allows for sets that we have no well defined probability of picking an element of.
Alright, time to start constructing the solution. Consider the sequence of hats that the logicians are wearing to be an infinite binary sequence, starting from the back of the line (x1, x2, x3...). Use that binary sequence to construct a real number, y, between zero and one, represented in binary as y=0.x1x2x3...
Next, construct an equivalence class on the reals between zero and one. We will consider two real numbers, a and b, to be equivalent if, when expressed in binary, a and b differ in only finitely many decimal places. Now we use the axiom of choice to select one element from each equivalence class and call the set V. So, for all z between zero and one, there is exactly one element of V that differs from z in only finitely many decimal places. Also, no two elements of V differ from eachother in finitely many decimal places. Have the logicians agree on the set V and memorize it.
Now, each logician is to look at the hats in front of them, and they know "most" of the binary sequence of the actual number they are in (calling that y). That is to say, logician number 6 can consider y=0.x1x2x3x4x5x6x7x8x9.... The first 6 digits are unknown to him, but all the rest are known. Every single logician knows all but finitely many of the digits in the binary expansion of y. As a result, every logician is aware of what equivalence class y is in, and they all have agreed on an element in V (call it k) that differs from y in only finitely many places. Thus, if everybody guesses assuming that y actually is k, then only finitely many of them will be wrong.
Naturally, this requires that the logicians be capable of an infinite amount of work, they must find a choice function, then they must memorize all the elements in the set V (or just memorize the choice function, its the same). Next they must examine all of the (infinite) hats in front of them to figure out what equivalence class they are in to select an element of V.
But, if they can do all of that, they can accomplish the rather miraculous task of solving this problem.
It is also worth saying that they can solve this problem even if the hats are not restricted to being white or black. As long as they know the set of colours that the hats can come from, they can do the exact same thing. Instead of considering binary sequences, they simply consider trinary sequences, or hexadecimal, or whatever it takes to get as many digits are there are hat colours. If that doesn't make you think the Axiom of Choice is crazy, I don't know what will.
It is also worth saying that in most problems like this, where everybody must guess simultaneously, you try to arrange the peoples guesses so that when something goes wrong, it goes maximally wrong. This is needed because each person on their own has a fixed probability of being wrong, so you simply try to make those fixed probabilities non-independent so that you minimize the chance that things go wrong.
In this problem, each person has a 50% chance of being wrong at the time they make their guess. This is a bit of a problem, as that means that on average half of the people will be wrong and there is very little one can do about it. Fortunately, the Axiom of Choice destroys usual notions of probability. It does this by creating sets of non-defined length. Simply put, length can be defined in terms of the probability that you were to pick an element of the set. Specifically, if you have a subset S of [0,1], and you were to pick an element of [0,1] at random, the probability that you would get an element of S would be L(S), the sets length. If the Axiom of Choice allows for sets with no length, it also allows for sets that we have no well defined probability of picking an element of.
Alright, time to start constructing the solution. Consider the sequence of hats that the logicians are wearing to be an infinite binary sequence, starting from the back of the line (x1, x2, x3...). Use that binary sequence to construct a real number, y, between zero and one, represented in binary as y=0.x1x2x3...
Next, construct an equivalence class on the reals between zero and one. We will consider two real numbers, a and b, to be equivalent if, when expressed in binary, a and b differ in only finitely many decimal places. Now we use the axiom of choice to select one element from each equivalence class and call the set V. So, for all z between zero and one, there is exactly one element of V that differs from z in only finitely many decimal places. Also, no two elements of V differ from eachother in finitely many decimal places. Have the logicians agree on the set V and memorize it.
Now, each logician is to look at the hats in front of them, and they know "most" of the binary sequence of the actual number they are in (calling that y). That is to say, logician number 6 can consider y=0.x1x2x3x4x5x6x7x8x9.... The first 6 digits are unknown to him, but all the rest are known. Every single logician knows all but finitely many of the digits in the binary expansion of y. As a result, every logician is aware of what equivalence class y is in, and they all have agreed on an element in V (call it k) that differs from y in only finitely many places. Thus, if everybody guesses assuming that y actually is k, then only finitely many of them will be wrong.
Naturally, this requires that the logicians be capable of an infinite amount of work, they must find a choice function, then they must memorize all the elements in the set V (or just memorize the choice function, its the same). Next they must examine all of the (infinite) hats in front of them to figure out what equivalence class they are in to select an element of V.
But, if they can do all of that, they can accomplish the rather miraculous task of solving this problem.
It is also worth saying that they can solve this problem even if the hats are not restricted to being white or black. As long as they know the set of colours that the hats can come from, they can do the exact same thing. Instead of considering binary sequences, they simply consider trinary sequences, or hexadecimal, or whatever it takes to get as many digits are there are hat colours. If that doesn't make you think the Axiom of Choice is crazy, I don't know what will.
The Axiom Of Choice
So, when I started this blog, the intention was to do mostly logic puzzles with the occasional math rant. I suppose I have done a few mathematical rants, but they have always been about logic puzzles themselves, as opposed to just random rants about stupid things that exist in set theory. For those who just want a logic puzzle, you can skip to the end of this rant and read the one I am putting up this week, but I'm going to warn you, you aren't going to be happy with it. Anyway, back to stupid things in set theory.
By far, the stupidest thing that exists in set theory is the Axiom of Choice. Anybody who reads this blog is already familiar with it, but I might as well give my formal statement of it:
Specifically, f is a function that chooses exactly one element from each set X in S, and f(X) tells you specifically which element the function has chosen.
This can sound innocent enough, all it says is that if you have a bunch of sets, it is possible to choose one element from each of those sets. The problem can come if the collection is infinitely big, its not clear that there would be a "rule" to tell you exactly how to select exactly one element from each of those sets.
For example, consider that we are only using the natural numbers, {0,1,2,3,...}. Then if we are told that S contains only nonempty subsets of the naturals, it is easy to find a choice function, simply always choose the smallest element of X (as it turns out, the Axiom of Choice is trivially true in a universe that only has the natural numbers). However, now let us suppose that we are using the real numbers, S might be the set of all nonempty subsets of real numbers, the function that would allow us to select exactly one element from each of these sets would be difficult to construct indeed. The Axiom of Choice is the postulate that there is such a function that would allow us to do just that, even though it gives no hint as to what such a function would look like.
How about some sort of middle ground, let us consider the integers, {....-3,-2,-1,0,1,2,3,.....}. If S contains nonempty subsets of the integers, you can still come up with a choice function without the Axiom of Choice. Specifically one can just use "If X contains any nonnegative integers, pick the smallest nonnegative one. If X contains only negative integers just use the largest negative integer." This rule will always pick out an element, so the Axiom of Choice is also not needed for the integers.
This is actually as if we had rearranged the order of the integers to be {0,1,2,3,....-1,-2,-3,....}, lining up all the positive integers in correct order, and then saying that -1 is greater than all the positive ones and then moving 'up' with the negative integers. Now under this new ordering of the integers, the rule is simply to "pick the smallest one". One could imagine that if there was some way to line up the reals such that every subset had a smallest element that the Axiom of Choice would then be unnecessary.
This leads us to a pretty general statement about the Axiom of Choice. Specifically, we ("we" being basically every set theorist on the planet) will consider orderings on sets, a concept of "greater than". First, an ordering will be called a "partial order" if whenever a>b and b>c then a>c follows. This is a reasonable demand to make on something you would want to call a concept of "greater than". Next, a partial ordering will be called a "total order" if for all a and b in the set, exactly one of these is true: a>b, b>a, a=b. Note that a partial ordering did not demand this, partial orderings can have elements where two elements are incomparable. Most orderings that one deals with in math are total orderings (like the usual one on the reals). Finally a total ordering is called a "well order" if for any subset there is a smallest element. The only well ordering that one deals with normally is that on the naturals, but one can see that you can give the integers a well ordering as well.
We can see that if you can find a well ordering for a set, you get a choice function right away and the Axiom of Choice is not needed. The "Well-ordering theorem" is the idea that every set can be well ordered (and needs that Axiom of Choice to prove). We have seen that if the Well-ordering theorem were to be true on its own, the Axiom of Choice would come for free, so you can see that the Axiom of Choice will be true if and only if the well-ordering theorem were true.
Alright, that is all fun and good (and probably most of you stopped reading ages ago), but what is really the problem with the Axiom of Choice? I mean, it seems intuitive enough, and probably helps prove some things (like the Well-ordering theorem), what could go wrong?
One of the basic problems shows up with the Banach-Tarski paradox. You can go look it up if you like, and I'll give a proper proof of it in the next few weeks, but the paradox is that it is possible to take a solid sphere, divide the sphere up into a number of disjoint pieces and, using only translation and rotation of the pieces, reassemble them into two copies of the original sphere, each the size of the original sphere. It seems like it might be a trick using an infinite number of pieces or something, but you can actually do it using just 5 pieces.
One might be concerned about conservation of volume in the Banach-Tarski paradox, how you could cut up a sphere of fixed volume and make something with twice as much volume using just translation and rotation. The trick is that the pieces do not have any well defined volume, and so conservation goes out the window. Actually, it is convenient to show how to use the Axiom of Choice to construct an object with no well-defined volume.
We will constrain ourselves to the one dimensional real line here, and we will have a concept of length. The length of a set S will be denoted L(S). We will denote adding a number to a set to mean that we construct a new set by adding that number to each element of the set, se {1,2,4}+5 is the set {6,7,9}. It is clear that we would want our length function to be translation invariant, so that L(S+x)=L(S) for any real number x. Next, if we take the union of two disjoint sets we want the lengths to add, so that L(S ∪ P)=L(S)+L(P) if S and P are disjoint (this also means that if P is a subset of Q then L(P) ≤ L(Q)). Finally, we want the length of intervals to be what we expect them to be, that being L([a,b])=b-a for b>a. Note that there can be nonempty sets with zero length, such as a set with only single point elements.
Alright, this is enough properties of length to prove that (with the Axiom of Choice) there exists a set that cannot be evaluated with this function. Let us consider an equivalence relation on the real numbers, two real numbers will be said to be equivalent if they differ by a rational number (this means that for each number, the set of numbers equivalent to it is a pattern that looks like the rationals). The set V will be constructed by choosing one element from each equivalence class that is also between 0 and 1. So, every real number differs from exactly one element of this set by a rational number, and does not differ from any other elements of this set by a rational number.
Next, list all the rational numbers between -1 and 1 and assign then each to a natural number, so that xn represents the list of all rationals between -1 and 1. It is clear that for every real number y between 0 and 1 there is an n such that y+xn is an element of V, so that y is an element of V-xn. V-xn will also spill out past (0,1) and hit some reals between -1 and 2, but will not get all of them. We also know that V+xn is disjoint from every V+xm for n and m different, as V had only one number from each equivalence class.
Now, we can consider E to be the union of the disjoint sets V+xn. It is clear that (0,1) is a subset of E and E is a subset of (-1,2). Thus 1 ≤ L(E) ≤ 3, but we also know that L(V+xn)=L(V). So If L(V) is zero, then E is the disjoint union of sets of length zero, and it has length zero, but if L(V) is nonzero, then E is the disjoint union of infinitely many sets with nonzero length and has infinite length.
Thus, we cannot have a function L that consistently assigns length to every set that exists in a world with the Axiom of Choice. This sort of thing will come up again later when I show the proof of the Banach-Tarski paradox and have to deal with the issue of volume conservation.
For now, its time for a logic puzzle (using the word "logic" loosely here), I first learned this one on the forums at xkcd:
By far, the stupidest thing that exists in set theory is the Axiom of Choice. Anybody who reads this blog is already familiar with it, but I might as well give my formal statement of it:
Given a collection of nonempty sets S, there exists a function f such that for all sets X in S, f(X) is an element of X.
Specifically, f is a function that chooses exactly one element from each set X in S, and f(X) tells you specifically which element the function has chosen.
This can sound innocent enough, all it says is that if you have a bunch of sets, it is possible to choose one element from each of those sets. The problem can come if the collection is infinitely big, its not clear that there would be a "rule" to tell you exactly how to select exactly one element from each of those sets.
For example, consider that we are only using the natural numbers, {0,1,2,3,...}. Then if we are told that S contains only nonempty subsets of the naturals, it is easy to find a choice function, simply always choose the smallest element of X (as it turns out, the Axiom of Choice is trivially true in a universe that only has the natural numbers). However, now let us suppose that we are using the real numbers, S might be the set of all nonempty subsets of real numbers, the function that would allow us to select exactly one element from each of these sets would be difficult to construct indeed. The Axiom of Choice is the postulate that there is such a function that would allow us to do just that, even though it gives no hint as to what such a function would look like.
How about some sort of middle ground, let us consider the integers, {....-3,-2,-1,0,1,2,3,.....}. If S contains nonempty subsets of the integers, you can still come up with a choice function without the Axiom of Choice. Specifically one can just use "If X contains any nonnegative integers, pick the smallest nonnegative one. If X contains only negative integers just use the largest negative integer." This rule will always pick out an element, so the Axiom of Choice is also not needed for the integers.
This is actually as if we had rearranged the order of the integers to be {0,1,2,3,....-1,-2,-3,....}, lining up all the positive integers in correct order, and then saying that -1 is greater than all the positive ones and then moving 'up' with the negative integers. Now under this new ordering of the integers, the rule is simply to "pick the smallest one". One could imagine that if there was some way to line up the reals such that every subset had a smallest element that the Axiom of Choice would then be unnecessary.
This leads us to a pretty general statement about the Axiom of Choice. Specifically, we ("we" being basically every set theorist on the planet) will consider orderings on sets, a concept of "greater than". First, an ordering will be called a "partial order" if whenever a>b and b>c then a>c follows. This is a reasonable demand to make on something you would want to call a concept of "greater than". Next, a partial ordering will be called a "total order" if for all a and b in the set, exactly one of these is true: a>b, b>a, a=b. Note that a partial ordering did not demand this, partial orderings can have elements where two elements are incomparable. Most orderings that one deals with in math are total orderings (like the usual one on the reals). Finally a total ordering is called a "well order" if for any subset there is a smallest element. The only well ordering that one deals with normally is that on the naturals, but one can see that you can give the integers a well ordering as well.
We can see that if you can find a well ordering for a set, you get a choice function right away and the Axiom of Choice is not needed. The "Well-ordering theorem" is the idea that every set can be well ordered (and needs that Axiom of Choice to prove). We have seen that if the Well-ordering theorem were to be true on its own, the Axiom of Choice would come for free, so you can see that the Axiom of Choice will be true if and only if the well-ordering theorem were true.
Alright, that is all fun and good (and probably most of you stopped reading ages ago), but what is really the problem with the Axiom of Choice? I mean, it seems intuitive enough, and probably helps prove some things (like the Well-ordering theorem), what could go wrong?
One of the basic problems shows up with the Banach-Tarski paradox. You can go look it up if you like, and I'll give a proper proof of it in the next few weeks, but the paradox is that it is possible to take a solid sphere, divide the sphere up into a number of disjoint pieces and, using only translation and rotation of the pieces, reassemble them into two copies of the original sphere, each the size of the original sphere. It seems like it might be a trick using an infinite number of pieces or something, but you can actually do it using just 5 pieces.
One might be concerned about conservation of volume in the Banach-Tarski paradox, how you could cut up a sphere of fixed volume and make something with twice as much volume using just translation and rotation. The trick is that the pieces do not have any well defined volume, and so conservation goes out the window. Actually, it is convenient to show how to use the Axiom of Choice to construct an object with no well-defined volume.
We will constrain ourselves to the one dimensional real line here, and we will have a concept of length. The length of a set S will be denoted L(S). We will denote adding a number to a set to mean that we construct a new set by adding that number to each element of the set, se {1,2,4}+5 is the set {6,7,9}. It is clear that we would want our length function to be translation invariant, so that L(S+x)=L(S) for any real number x. Next, if we take the union of two disjoint sets we want the lengths to add, so that L(S ∪ P)=L(S)+L(P) if S and P are disjoint (this also means that if P is a subset of Q then L(P) ≤ L(Q)). Finally, we want the length of intervals to be what we expect them to be, that being L([a,b])=b-a for b>a. Note that there can be nonempty sets with zero length, such as a set with only single point elements.
Alright, this is enough properties of length to prove that (with the Axiom of Choice) there exists a set that cannot be evaluated with this function. Let us consider an equivalence relation on the real numbers, two real numbers will be said to be equivalent if they differ by a rational number (this means that for each number, the set of numbers equivalent to it is a pattern that looks like the rationals). The set V will be constructed by choosing one element from each equivalence class that is also between 0 and 1. So, every real number differs from exactly one element of this set by a rational number, and does not differ from any other elements of this set by a rational number.
Next, list all the rational numbers between -1 and 1 and assign then each to a natural number, so that xn represents the list of all rationals between -1 and 1. It is clear that for every real number y between 0 and 1 there is an n such that y+xn is an element of V, so that y is an element of V-xn. V-xn will also spill out past (0,1) and hit some reals between -1 and 2, but will not get all of them. We also know that V+xn is disjoint from every V+xm for n and m different, as V had only one number from each equivalence class.
Now, we can consider E to be the union of the disjoint sets V+xn. It is clear that (0,1) is a subset of E and E is a subset of (-1,2). Thus 1 ≤ L(E) ≤ 3, but we also know that L(V+xn)=L(V). So If L(V) is zero, then E is the disjoint union of sets of length zero, and it has length zero, but if L(V) is nonzero, then E is the disjoint union of infinitely many sets with nonzero length and has infinite length.
Thus, we cannot have a function L that consistently assigns length to every set that exists in a world with the Axiom of Choice. This sort of thing will come up again later when I show the proof of the Banach-Tarski paradox and have to deal with the issue of volume conservation.
For now, its time for a logic puzzle (using the word "logic" loosely here), I first learned this one on the forums at xkcd:
You have a countably infinite number of logicians standing in a semi-infinite line. Each of them is wearing a hat which is either white or black. They can all see the (infinite number of) hats in front of them, none of the (finitely many) hats behind them and not their own hat and they all know their own position in the line. They must each simultaneously write down a guess about their own hat colour. They win the game if only finitely many of them are wrong, they lose if an infinite number of them guess wrong. Before the hats are assigned they may strategize. Using the Axiom of Choice, prove the existence of a strategy that guarantees their victory.
Numbers Are Crazy
Probably enough time has passed since my silly math problem. If you have spent some time working on it, you will see that you can basically create every number around 21 easily, but getting to 21 is a bit harder.
To start, we might as well try to make 21 by constructing 7x3, thats basically all 21 is, getting there by any sort of addition is going to be pretty tricky. We already have a 7, so how can we make a 3 from {1,5,6}? Well, basically we can't. We do have a 6 though, so if one considers 21 to be 7x6/2, we just need to use the 5 and the 1 to make a 2 (also clearly impossible). The real trick though is to use grade school division trick that a/(b/c)=ac/b, so 21 is also 6/(2/7). We now need to use {1,5,7} to make 2/7, and that one is pretty easy to do. Of course, the solution is:
The neat blind spot is that people tend to dismiss division right out when they are given this puzzle. There is no division that you can do with these numbers that will not exit the integers, and people tend to assume that once you leave the integers you won't get back.
The double division is also the solution for the "{3,3,8,8} makes 24" puzzle, so I won't bother saying the solution specifically, its pretty simple now.
To start, we might as well try to make 21 by constructing 7x3, thats basically all 21 is, getting there by any sort of addition is going to be pretty tricky. We already have a 7, so how can we make a 3 from {1,5,6}? Well, basically we can't. We do have a 6 though, so if one considers 21 to be 7x6/2, we just need to use the 5 and the 1 to make a 2 (also clearly impossible). The real trick though is to use grade school division trick that a/(b/c)=ac/b, so 21 is also 6/(2/7). We now need to use {1,5,7} to make 2/7, and that one is pretty easy to do. Of course, the solution is:
6 ÷ (1 - (5 ÷ 7))
The neat blind spot is that people tend to dismiss division right out when they are given this puzzle. There is no division that you can do with these numbers that will not exit the integers, and people tend to assume that once you leave the integers you won't get back.
The double division is also the solution for the "{3,3,8,8} makes 24" puzzle, so I won't bother saying the solution specifically, its pretty simple now.
Silly Math
Alright, I've once again run out of standard "find the optimal strategy" type problems, its time for a seemingly simple math problem. I can't recall when I first learned this one, I've known it since at least grade 9:
To be clear, there are no stupid tricks in this problem, like sliding the 1 and 5 together to make 15. The solution is exactly of the form _*_*_*_, where _ is replaced by the numbers from {1,5,6,7} each used once, and * is replaced by {+,-,x,÷} (and can use repeats). You also have as many brackets as you need to control order of operations.
I always find this problem rather interesting because typically this sort of problem is either trivial or impossible, but this one is neither. There is a funny blind spot people tend to have with this.
Also, if you are in the mood, try using 3,3,8,8 to make 24 with the same rules. This one will be much easier after you have solved the first one.
Using the numbers 1, 5, 6, and 7, each once and only once, and +, -, x, and ÷ as much as you like, construct a formula for the number 21. You may also use as many brackets as you like.
To be clear, there are no stupid tricks in this problem, like sliding the 1 and 5 together to make 15. The solution is exactly of the form _*_*_*_, where _ is replaced by the numbers from {1,5,6,7} each used once, and * is replaced by {+,-,x,÷} (and can use repeats). You also have as many brackets as you need to control order of operations.
I always find this problem rather interesting because typically this sort of problem is either trivial or impossible, but this one is neither. There is a funny blind spot people tend to have with this.
Also, if you are in the mood, try using 3,3,8,8 to make 24 with the same rules. This one will be much easier after you have solved the first one.
Subscribe to:
Posts (Atom)
