Time to post the solution to the marble problem from last time. First of all, lets just try some naive strategies. When I introduced the problem, I had suggested the idea of just moving up the floors one at a time until the marble broke. Since we have two marbles, we can try to do better by moving up two floors at a time. We try floors 2,4,6,8,10,... and when the marble breaks on floor k, we simply use the other marble to try floor k-1 and confirm which was the critical floor. This strategy is much less wasteful that the last one (at least it makes use of the second marble), and the worst case scenario is if the critical floor, N, is 99 or 100, in which case we need to try all the even floors (50 of them) plus floor 99 for a total of 51 tries.
Alright, if two floors at a time improved our position, lets try three. Now we will test floors 3,6,9,12,... and when the marble breaks on floor k, we try k-1 and k-2 to confirm. I suppose if we get to floor 99 and the marble doesn't break, we don't actually need to try floor 100, but whatever. The worst case scenario is if we go all the way to 99 and must do 97 and 98. In this case we did 3,6,9,12,...99 for 33 floors and 97 and 98 for a total of 35 tries.
So taking larger steps seems to be better, we could try something silly like 25 floors at a time and then your worst case is 27 (easy to confirm). It is pretty clear that you will get the optimal strategy of this form if you just do 10 at a time (the square root of 100), and the worst case is 19.
Now the next thing to notice is that if you were to make a bigger step at the beginning, you don't make your life any worse. In particular, if you start with floor 15 and then go 25,35,45,..95, then go back, the worst case won't be N=100 anymore (that would take only 11 tries), the worst case will be N=94 or 95 for a total of 18 floors (its one better than the last case because you basically skipped a set of 10).
This idea of skipping a bunch of floors at the beginning will only work so far, of course. If you try to move all the way up to 20, then if it breaks right away you must try all 20 initial floors. So we see that if the actual worst case scenario is that it takes M tries, then you cannot start on a floor higher than M (because if the critical floor N is M-1 you are in trouble). Next, you can move up another M-1 floors at most, because if you move up M more and N is 2M-1 then you will need M+1 total tries to find it. Clearly we must move up by M-1 floors to floor 2M-1. Next we can move up by M-2 floors at most. You can see what is happening here.
If the total number of floors is the Kth triangle number, then you can solve the problem most efficiently in K steps by moving up K floors then K-1 then K-2 and so on. The 13th triangle number is 91, so we cannot do more than 91 floors in 13 steps. Thus we can just treat our 100 floor building as a 105 floor building (the 14th triangle number) and use that solution.
Breaking Marbles
Time for a new puzzle, I'm not sure where I first learned this one, it was somewhere randomly on the internets:
To put this problem into "math", there is an integer X between 1 and 100. You may guess an integer and I will tell you if X is " ≥ " or " < " your guess. If I ever say " ≥ " twice, you cannot guess again and must tell me what X is. You are to minimize the worst case for the number of guesses.
A clear naive strategy is just to go up the floors, one at a time, and when the marble breaks you know exactly what floor it happened on. Of course, the worst case here will need 100 drops and you didn't even try to make use of the fact that you have two marbles (actually, that solution is optimal if you only have one marble).
Consider there is a building with 100 floors. You have a pair of identical marbles which you are going to drop from the windows of this building. There is a height at which the marbles are broken if they are dropped from that height. The marbles will break if they are dropped from that height or more, and take no damage if they are dropped from any lesser height. The objective is to determine what floor is that height using as few drops as possible. You may assume that a broken marble is useless, and that you are to minimize the worst case scenario.
To put this problem into "math", there is an integer X between 1 and 100. You may guess an integer and I will tell you if X is " ≥ " or " < " your guess. If I ever say " ≥ " twice, you cannot guess again and must tell me what X is. You are to minimize the worst case for the number of guesses.
A clear naive strategy is just to go up the floors, one at a time, and when the marble breaks you know exactly what floor it happened on. Of course, the worst case here will need 100 drops and you didn't even try to make use of the fact that you have two marbles (actually, that solution is optimal if you only have one marble).
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.
Subscribe to:
Posts (Atom)
